# A peculiar binomial coefficient identity

While inventing exercises for a discrete math text I'm writing I came up with this $$\binom{\binom{n}{2}}{2}=3\binom{n+1}{4}$$ It's an easy result to prove, but it got me wondering

1. Is this pure coincidence, or is it a special case of some more general result of which I'm unaware?
2. No matter what the answer to (1) is, is there a combinatorial proof?
• Looks purdy.${{{}}}$ – Git Gud Jun 26 '13 at 21:20
• Every polynomial $f(x)$ which takes integer values at the integers is an integer linear combination of the polynomials ${x \choose k}$, so in some sense this identity is not very surprising. The analogous statement for multivariate polynomials is also true, so there are also for example identities of the form ${x + y \choose k} = \sum a_{i, j} {x \choose i} {y \choose j}$ and ${xy \choose k} = \sum b_{i, j} {x \choose i} {y \choose j}$. The only mildly surprising thing is that in both of these cases the coefficients turn out to be non-negative as well as integers, but that's because the... – Qiaochu Yuan Jun 26 '13 at 21:57
• ...corresponding identities also have combinatorial proofs (exercise!). – Qiaochu Yuan Jun 26 '13 at 21:57
• – sdcvvc Jul 4 '13 at 23:00

This is actually a well known identity. There are combinatorial ways to prove it.

Consider $n$ objects. Consider all ${n \choose 2}$ pairs. Consider all pairs of these pairs. We get the LHS.

Consider $n$ objects and 1 distinguished object. Consider all sets of 4 objects from these.
If the 4 objects do not include the distinguished object, they correspond to 3 possible pairs of pairs, whose 4 elements are distinct. I.E. $(A,B), (C,D)$ and $(A, C), (B, D)$ and $(A, D), (B,C)$.
If the 4 objects include the distinguished object, they correspond to 3 possible pairs of pairs, which have a common element, and whose union is the 3 objects. I.E. $(A, B) , (A, C)$ and $(B,A), (B,C)$ and $(C,A), (C,B)$.
This gives us the RHS.

I'm not sure if they are generalizations, though you can experiment with choosing triples and counting carefully.

• I'm not surprised by (1) the fact that this is well-known and (2) that you knew it. Nice job, +1 – Rick Decker Jun 26 '13 at 21:28

The lefthand side is of course the number of ways to choose two unordered pairs, possibly with a one-element overlap, from the set $[n]=\{1,\dots,n\}$. Alternatively, we may choose a $4$-element subset $A$ of $\{0,1,\dots,n\}$ and a $k\in[3]$. Let $A=\{a_1,a_2,a_3,a_4\}$ with $a_1<a_2<a_3<a_4$. If $a_1\ne 0$, pair $a_1$ with $a_{k+1}$ and let the other two members of $A$ be the other pair. If $a_1=0$, form two pairs from $\{a_2,a_3,a_4\}$ by letting $a_k$ be the common member.

• My goodness. Two replies within 9 minutes. This place is the math equivalent of a fast food restaurant (though the offerings are unusually tasty). +1 – Rick Decker Jun 26 '13 at 21:33
• You mean "an unordered pair of unordered pairs." "Two" could mean "ordered pair." – Qiaochu Yuan Jun 26 '13 at 21:55
• @Qiaochu: I think that one would almost have to be deliberately trying to misunderstand in order to come up with that reading. – Brian M. Scott Jun 27 '13 at 1:30

You can count all of the pairs of pairs with $4$ distinct elements and all of the pairs of pairs with $3$ distinct elements and then add them together.

For the first sum get $\binom{n}{4}\binom{4}{2}\frac{1}{2}=3\binom{n}{4}$. We divide by two because once we choose the first pair out of the $4$ elements we implicitly chose the other pair; we are double counting otherwise.

For the second sum we get $3\binom{n}{3}$ since we must choose $3$ elements and then one of them to be duplicated.

In total we have $$3 \left[ \binom{n}{4} + \binom{n}{3}\right] = 3\binom{n+1}{4}$$.

So that's $2/3$ combinatorial at least.

• Nice and succinct. +1 – Rick Decker Jun 27 '13 at 1:02