Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Provide a combinatorial argument for the given equation $${^{n+1}C_4}= {{^{^{^nC_2}}C_2}\over 3} \text{, for } n\ge 4$$
HINT: Consider a group of $n+1$ terms of which one is considered special. Argue that both sides of the above identity represent the number of subsets of size $4$.
I get how the LHS is the number of size $4$ subsets of a set of $n+1$ terms. How does the RHS follow suit?
For $n\geq 3$, ${^{^{^nC_2}}C_2}=\binom{\binom{n}{2}}{2}$ is the number of ways to choose two distinct subsets of two elements, say $A$ and $B$, from the $n$-set given by whole set of $n+1$ elements without the special one (let's denote it by $s$).
We have two cases.
1) If $|A\cap B|=0$ then $X=A\cup B$ is a subset of $4$ elements. The same subset $X=\{a,b,c,d\}$ can be obtained in $3$ different ways: $$\{a,b\}\cup\{c,d\},\quad \{a,c\}\cup\{b,d\} ,\quad \{a,d\}\cup\{b,c\}.$$
2) If $|A\cap B|=1$ then $X=A\cup B\cup \{s\}$ is a subset of $4$ elements. The same subset $X=\{a,b,c,s\}$ can be obtained in $3$ different ways: $$\{a,b\}\cup\{b,c\}\cup \{s\},\quad \{a,c\}\cup\{b,c\}\cup \{s\},\quad \{a,b\}\cup\{a,c\}\cup \{s\}.$$
Hint: The right hand side is obtained by choosing $4$ elements out of an $(n+1)$-element set by considering all the possible subsets of size $2$ and picking two of them (in such a way that they are disjoint). The division by $3$ comes from the fact that different choices could give the same final result. I leave the details to you.
For the RHS, first, collect subsets of $2$ elements (abbrev. 2-set) from the set without the special element (with cardinality $n$). That would be $^nC_2$ elements.
Secondly, collect the number of subsets of cardinality $2$ from the above-mentioned 2-set. Then we do an algorithm with it: First union the two elements that were chosen together, and there would be two cases: 1. The chosen two elements (of the 2-set) are disjoint. This would be fine. 2. They are not, then the union of them must be with cardinality $3$. In this occasion, simply union the special element with it. With order (of union) preserves, we convert these into 4-tuples. Here we have overall $^{^nC_2}C_2$ elements of 4-tuple.
Thirdly, easy to see that, the cardinality of the above is exactly three times the number of subsets of cardinality $4$, since if a subset is with card. $4$ and without the special element, you can partition it into non-equal subsets of card. $2$ by three ways, and if it contains, set-minus the special element and by choosing the joint element, you could also express it in three ways by elements of the above mentioned set of card. $^{^nC_2}C_2$.
And we are done.
(P. S. I might not have organized my words well, hope you can understand it.)
