4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ the title makes no sense $\endgroup$ – miracle173 Oct 13 '17 at 12:13
2
$\begingroup$

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\}.$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.