Discrete math combinatorial proof

139 Views Asked by At

Prove that for every positive integer n,

$$\sum_{k=0}^{n}\binom{n}{k}^2=\sum_{l=0}^{n}\sum_{r=0}^{\frac{n-l}{2}}\binom{n}{l}\binom{n-l}{r}\binom{n-l-r}{r}$$

I know that $\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n}$ but I can't seem to find a way to connect it to the right side. Any help would be appreciated, I've been trying to figure this out for days.

1

There are 1 best solutions below

6
On

HINT: The lefthand side is the number of pairs $\langle A,B\rangle$ such that $A$ and $B$ are subsets of $[n]=\{1,\ldots,n\}$, and $|A|=|B|$. You can classify these pairs according to the number of elements that they have in common. Suppose that $C=A\cap B$; then $A\setminus C$ and $B\setminus C$ must be disjoint subsets of $[n]$. Think of setting $\ell=|C|$ and $r=|A\setminus C|=|A\setminus B|$.