Give combinatorial a proof that $\binom{n}{2}^2=\binom{n}{2}+6\binom{n}{3}+6\binom{n}{4}$

Question

Give combinatorial a proof that $$\binom{n}{2}^2=\binom{n}{2}+6\binom{n}{3}+6\binom{n}{4}$$

I firstly thought it like classical commission questions consisting of $n$ men and $n$ women etc. However , i did not work. After that , i thought about manipulating the question such that $$\binom{n}{2}^2=\binom{n}{2}+6\binom{n}{3}+6\binom{n}{4}$$ $$\binom{n}{2}\binom{n}{n-2}=\binom{n}{2}+6\binom{n+1}{4}$$ However , i cannot still find anything. Can you help me ?

NOTE: Although @Phicar's answer get credit from you , i could not comprehend it :( So , i am open to other proofs.

NOTE 2: Do not write "HINTS" , if you want to write somethings , please be clear and elaborately

Answer 1

The other answer by Phicar is splendid, but I thought I should relate it more concretely to your attempt, picking two (unordered, but distinguishable) pairs from a group

consisting of $n$ men and $n$ women

Instead, try to pick two (not necessarily disjoint) pairs from a single group of $n$ people. The left-hand side is the direct approach, while the right-hand side splits into cases based on how many people were actually chosen.

Answer 2

Hint: Try the most natural thing: You are choosing ordered pairs of groups of 2 people out of $n$ people, this is the left hand side. You can either have the same group, that is, the pair share both people (in how many ways?) or you choosed two groups that share exactly one person (so you are choosing $3$ people, actually) or your pair has no one in common (so you are choosing 4 people).

Edit: You are asking for not a hint..well consider $\binom{[n]}{k}=\{A\subseteq [n]=\{1,2,\cdots ,n\}:|A|=k\},$ what you want is to find a bijection in between $\binom{[n]}{2}\times \binom{[n]}{2}$ and $\binom{[n]}{2}\bigcup \binom{[n]}{3}\times \binom{[3]}{1}\times\binom{[2]}{1} \bigcup \binom{[n]}{4}\times\binom{[4]}{2}$, where those are disjoint unions. For that, consider the following function $$\varphi (A,B)=\begin{cases}A & \text{if }A=B\\ (A\cup B,A\cap B,A\setminus B) & \text{ if }|A\cap B|=1\\ (A\cup B,A) & \text{Otherwise, so}|A\cap B|=0\end{cases},$$ Just show that this is actually a bijection.

Answer 3

It might help to explain the origin of the two sixes since they come from different origins.

The green part below consists of choosing one of three to be doubled, multiplied by the ways of choosing which of the other two goes where. The blue part is the number of ways we can split four into two pairs. $$\binom{n}{2}^2=\color{purple}{\binom{n}{2}}+\color{green}{\binom{3}{1}\binom{2}{1}\binom{n}{3}}+\color{blue}{\binom{4}{2}\binom{n}{4}}$$ This is not a combinatoric proof, but just to confirm the answer: $$ \frac12n(n-1)+6\frac16n(n-1)(n-2)+6\frac1{24}n(n-1)(n-2)(n-3)\\ =\frac14n(n-1)\left\{2+4(n-2)+(n-2)(n-3)\right\}\\ =\frac14n(n-1)\left\{n(n-1)\right\}\\ =\binom{n}{2}^2 $$