Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 8 down vote accepted

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.

share|cite|improve this answer
    
Everyone is welcome to edit my English for a better explaination! :) – Maffred Jan 29 at 5:25

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.

share|cite|improve this answer

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$

share|cite|improve this answer
6  
This is not a combinatorial proof! – Maffred Jan 29 at 5:27
    
No you just explained it so i have done algebraic proof – Archis Welankar Jan 29 at 5:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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