How to get ${n \choose 0}^2+{n \choose 1}^2+{n \choose 2}^2+\cdots+{n \choose n}^2 = {x \choose y}$

Solution 1:

Let $E=\{a_1,\ldots a_n,b_1,\ldots,b_n\}$ a set with $2n$ elements. There's $2n\choose n$ subsets of $E$ with $n$ elements: $k$ elements from $\{a_1,\ldots,a_n\}$ and $n-k$ elements from $\{b_1,\ldots,b_n\}$ for some $k=0,\ldots,n$ hence we have $${2n\choose n}=\sum_{k=0}^n{n\choose k}{n\choose n-k}=\sum_{k=0}^n{n\choose k}^2$$

Solution 2:

Hint: compare the coefficient of $x^n$ on both sides of $(1+x)^{2n} = ((1+x)^n))^2$.

Solution 3:

Hint: Write it as $${n \choose 0} {n \choose n} + {n \choose 1} {n \choose n-1} + \dots + {n \choose n} {n \choose 0},$$ and use the obvious combinatorial bijection.