# Prove the following identity combinatorially

Prove the following identity combinatorially

$$\left(\begin{array}{c} \left(\begin{array}{c} n \\ 2 \end{array}\right) \\ 2 \end{array}\right) = 3 \left(\begin{array}{c} n \\ 4 \end{array}\right) + 3 \left(\begin{array}{c} n \\ 3 \end{array}\right)$$

-

We want to choose $2$ two-element subsets of an $n$ element set. Clearly there are $\binom{\binom{n}{2}}{2}$ ways to do this.
Let us count another way. Our pairs of doubletons are of two types (i) no overlap or (ii) an overlap of $1$ point.
To produce a pair of doubletons of type (i), choose $4$ objects. They can be split into two doubletons in $3$ ways.
To produce a pair of doubletons of type (ii), choose $3$ objects. There are $3$ ways to decide which of them will be in both doubletons.