8
$\begingroup$

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?
$\endgroup$
4
  • 2
    $\begingroup$ Looks purdy.${{{}}}$ $\endgroup$ – Git Gud Jun 26 '13 at 21:20
  • 1
    $\begingroup$ 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... $\endgroup$ – Qiaochu Yuan Jun 26 '13 at 21:57
  • $\begingroup$ ...corresponding identities also have combinatorial proofs (exercise!). $\endgroup$ – Qiaochu Yuan Jun 26 '13 at 21:57
  • $\begingroup$ see also math.stackexchange.com/questions/15509 $\endgroup$ – sdcvvc Jul 4 '13 at 23:00
8
$\begingroup$

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.

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

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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 $\endgroup$ – Rick Decker Jun 26 '13 at 21:33
  • $\begingroup$ You mean "an unordered pair of unordered pairs." "Two" could mean "ordered pair." $\endgroup$ – Qiaochu Yuan Jun 26 '13 at 21:55
  • 2
    $\begingroup$ @Qiaochu: I think that one would almost have to be deliberately trying to misunderstand in order to come up with that reading. $\endgroup$ – Brian M. Scott Jun 27 '13 at 1:30
2
$\begingroup$

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.

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

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.