Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$

For $n \geq 4$, show that $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$.

LHS: So we have a set of $\binom{n}{2}$ elements, and we are choosing a $2$ element subset.

RHS: We are choosing a $3$ element subset and a $4$ element subset (each from a set of $n$ elements). But we multiply by $3$ by the multiplication principle for some reason.

-
–  sdcvvc Jul 4 '13 at 23:01

1 Answer

LHS: The $\binom{n}{2}$ is the number of pairs you can form of n distinct elements, so the LHS counts the number of ways to choose two distinct pairs.

RHS: Notice that you can choose two pairs that have a common element (but only one). If the two pairs are disjoint, then you need to choose four elements and then ask how you pair them. If the pairs have a common element, then you need to choose only three elements and then choose which is the common element.

-
Distinct elements and distinct pairs. (You know this, but it should be clarified.) –  Qiaochu Yuan Dec 25 '10 at 19:36
Fixed it, thanks –  Prometheus Dec 25 '10 at 19:59