Dark Mode

Recent questions tagged combinatorics-iitb

0 votes

0 answers

1

Probability and random variable
Consider the sets $A_1, A_2, A_3 \dots A_m$ each a subset of size $k$ of $\{1,2,3, \dots , n\}$. If in a 2-colouring of $\{1,2,3, \dots , n\}$ no set $A_i$ is monochromatic, then show that $ m < 2^{k-1}$.

dd asked in Set Theory & Algebra Apr 27, 2018

by dd

365 views

0 votes

1 answer

2

Set theory
Consider the sets $A_1, A_2, A_3 \dots A_m$. Prove that the number of distinct sets of the form $A_i \oplus A_j$ is at least $m$.

dd asked in Set Theory & Algebra Apr 27, 2018

by dd

400 views

0 votes

0 answers

3

Set theory and Induction
Consider the set of all subsets of a set S. A chain is a collection of subsets $P_1 \subset P_2 \subset P_3 \subset P_4 \dots \subset P_k$. A symmetric chain is one which starts at a set of size $i$ and ends at a set of size $n - i$. Prove that the poset has a decomposition into symmetric chains.

dd asked in Set Theory & Algebra Apr 27, 2018

by dd

275 views

6 votes

4 answers

4

Counting
Show that, in a grid, the number of paths from $(0,0)$ to $(n,n)$ which does not cross ( it could touch ) the line $x = y$ is \begin{align*} \frac{1}{1+n}\binom{2\cdot n}{n} = \binom{2\cdot n}{n} - \binom{2\cdot n}{n-1} \end{align*} After that, show the number of balanced paranthesis strings of length $2n$ is same as the above result.

dd asked in Set Theory & Algebra Apr 27, 2018

by dd

2.5k views

0 votes

0 answers

5

Probability and set theory
Consider sets $A_1,A_2,A_3 \text{ to } A_m \text{ where }A_i \subseteq [n] \text{ and } [n] = \{1,2,3, \dots n \}$ such that there are no three distinct sets in the collection with the property $A_i \subset A_j \subset A_k.$ For even $n$, prove that \begin{align*} m ... bound on $m$ : \begin{align*} m \leq \binom{n}{\frac{n}{2}} + \binom{n}{\frac{n}{2} - 1} \end{align*}

dd asked in Set Theory & Algebra Apr 27, 2018

by dd

291 views

0 votes

1 answer

6

Induction
Prove that the number of edges in a graph with exactly one triangle is at most \begin{align*} \frac{\left( n - 1 \right )^2}{4} + 2 \end{align*}

dd asked in Graph Theory Apr 27, 2018

by dd

444 views

0 votes

0 answers

7

Probability
Prove for a positive integer valued random variable, $X$ , and for positive integers $a < b$ \begin{align*} &P(X \geq b) \leq \left [ \left ( \frac{E(X)}{b} \right ) - P(a \leq X < b)\cdot \left ( \frac{a}{b} \right ) \right ] \\ \end{align*}

dd asked in Probability Apr 27, 2018

by dd

217 views

1 vote

1 answer

8

Set system and linear algebra
We have $m$ sets $A_1,A_2,A_3 \text{ to } A_m$. All $A_i \subseteq [n]$ where $ [n] = \{1,2,3, \dots n \}.$ Given that $|A_i| = \text{odd number}$ and $|A_i \cap A_j| = \text{even number }\forall i \neq j$. Show that $m \leq n$.

dd asked in Set Theory & Algebra Apr 16, 2018

by dd

869 views

To see more, click for the full list of questions or popular tags.

Recent questions tagged combinatorics-iitb