Combinatorial Proof for Composite/Nested Binomial Coefficient

Question

I'm working on a problem right now for where we're asked to give a combinatorial proof for the following where $n \geq 4$: $${{n \choose 2} \choose 2} = 3{n \choose 4} + 3{n \choose 3}$$

LHS: Number of subsets of size 2 from $n$, and then we count all the ways to make subsets of 2 from those subsets.

RHS: Number of subsets we can make of size 4 from $n$ multiplied by 3 added to the number of subsets we can make of size 4 from $n$ multiplied by 3. I originally tried to relate it using three different groups with $n$ elements, but I suspect my logic was flawed in that I may have been double counting on the RHS. Any help would be greatly appreciated.

Answer 1

If you choose $4$ distinct elements of a set, there are $3$ different ways you can arrange them into two subsets of $2$ elements each -- you can pair the first element with any of the other three elements, leaving the remaining two elements to pair with each other.

If you choose $3$ distinct elements of a set, there are likewise $3$ different ways you can arrange them (with duplication) into two subsets of $2$ elements each -- you can choose each of the $3$ elements as the element to be duplicated and pair one "twin" with each of the other two elements.

There are no other ways to select elements from a set that allows you to exhaust the selected elements and arrange them into distinct subsets of $2$ elements each, so this exhausts the ways to select two subsets of $2$ elements each.

Answer 2

Left hand side, we have the total counts of two different ways of choosing 2 elements out of n. Since these two ways are different, they cannot overlap completely.

If there's no overlap, it's the same as choosing 4 elements, and then for one of the item, there is 3 other options to pair them, giving $3{n\choose 4}$.

If there's an overlap, then there is 3 ways to choose the overlap, giving $3{n\choose 3}$.

Answer 3

Both sides count the number of pairs of edges in the complete graph $K_n$. The LHS is clear. For the RHS, consider whether the edges share a common vertex (the second term) or not (the first term).