I'm asked to give a combinatorial proof of the following, $\binom{\binom n2}{2}$ = 3$\binom{n}{4}$ + n$\binom{n-1}{2}$.
I know $\binom{n}{k}$ = $\frac{n!}{k!(n-k)!}$ and $(\binom{n}{k}) = \binom{n+k-1}{k}$ but I'm at a loss as to what to do with the $\binom{\binom n2}{2}$
Can someone point me in the right direction as to how to proceed with writing a combinatorial proof for this identity?
Answer
LHS can be interpreted as counting the ways in which you can create two different pairs of two different elements, taken from a set of $n$ toys; while the pairs must be different, they need not be disjoint: they might have a toy in common.
RHS counts the same amount of pairs in a different way: you can create two kinds of such couple of pairs: disjoint ones $(a,b)(c,d)$ and overlapping ones $(a,b)(a,c)$. Remember that every pair must be different and the two couples must be different. The first kind of pairs can be chosen in the following way: first chose $4$ toys in $\binom{n}{4}$ ways, then chose one of the $3$ ways to partition the $4$ into two pairs (to see that there are $3$ ways, focus on one of the four: it must be paired with one of the three remaining ones, and that determines the partition). The second kind of pairs can be chosen by first choosing the toy $a$ that will be common to both pairs in $n$ ways, then chose $2$ toys from the remaining $n-1$ to be $\{b,c\}$; the order does not matter here, so the final choice can be made in $\binom{n-1}{2}$ ways.
No comments:
Post a Comment