6
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Everyone is welcome to edit my English for a better explaination! :) $\endgroup$ – Maffred Jan 29 '16 at 5:25
6
$\begingroup$

Consider a graph $G=(V,E)$ such that $|V|=n$ and $|E|={n \choose 2}$ (i.e. any two vertices are connected). Than the LHS of your identity is the number of unordered pairs of edges. Any such pair is either determined by four vertices or by three. In the first case we first choose 4 vertices and then connect them in any of 3 ways which gives us altogether $3{n \choose 4}$ combinations. In the second case we first select the vertex which belongs to both edges and later we select the other two vertices from remaining $n-1$ vertices which gives us $n{n-1 \choose 2}$ possibilities. Summing it up we get the RHS.

$\endgroup$
1
$\begingroup$

Rhs using simple combinatorics formula simplifies to $\frac{(n)(n-1)^2(n-2)}{8}$ now lhs ${n\choose 2}=\frac{(n)(n-1)}{2}$ so we can write lhs as $\frac{(n^2-n)!}{(2!).(\frac{n^2-n-4}{2})}$ now treat $n^2-n=y$ so it becomes $\frac{(n^2-n)(n^2-n-2)}{8}=\frac{(n)(n-1)^2(n-2)}{8}=Rhs$

$\endgroup$
  • 6
    $\begingroup$ This is not a combinatorial proof! $\endgroup$ – Maffred Jan 29 '16 at 5:27
  • $\begingroup$ No you just explained it so i have done algebraic proof $\endgroup$ – Archis Welankar Jan 29 '16 at 5:28

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.