Show by combinatorial proof that for $n \geq 4$, $3 {n \choose 4} + 3{n\choose 3} = {{n \choose 2} \choose 2}$

Question

I understand that ${{n \choose 2} \choose 2}$ is counting the number of unordered pairs of unordered pairs of $n$ elements. But I just can't seem to wrap my head around the LHS. of the identity from a counting point of view. Is there a way to simplify that side to make it have more intuitive sense?

Answer 1

Suppose we want to organise a 2 v 2 match among $n$ players. How many different matches do we have?

First method: there are $\binom n 4$ different ways of choosing $4$ different players. For any $4$ chosen players, there are $3$ different ways to organise them into two teams. Thus the total number of possible matches is $3\binom n 4$.

Second method: there are $\binom n 2$ different teams of $2$ players, hence $\binom{\binom n 2} 2$ different ways to choose two different teams. But we have to subtract cases where two teams share a common player: these are exactly choosing $3$ different players and let any of them be the "common player", hence $3\binom n 3$ cases.

Thus we get $3\binom n 4=\binom{\binom n 2} 2 - 3\binom n 3$.