### An interesting bijection

I came across the following identity recently: $\sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n}$. This can be proved in various ways. Here, I will describe a “combinatorial proof”.

First of all, we note the following: $\binom{n}{i}^2$ is the number of pairs of subsets $(S, T)$, such that $S,T\subseteq \{1,2,3,\dots,n \}, |S| = |T| = i$. Moreover, $\binom{2n}{n}$ is the number of possibilities to choose $n$ items out of set containing $2n$ items. This means, there must be a bijection from the pairs of subsets $(S,T)$ (as described before) and the subsets of cardinality $n$ of a set containing $2n$ elements.

To construct such a solution, we first note the following: $\binom{n}{i} = \binom{n}{n-i}$, a very basic identity of binomial coefficients. This means $\binom{n}{i}^2 = \binom{n}{i} \binom{n}{n-i}$. However, this corresponds to the number of possible pairs of sets $(S', T')$ with $S', T'\subseteq \{1,2,3,\dots,n \}, |S'|=i, |T'|=n-i$. For convenience we can simply say $T'=\{1,2,3,\dots n\}\setminus T$.

Now we desribe the process of choosing $n$ elements from the $2n$-element set $\{ 1,2,3,\dots ,n, \overline{1}, \overline{2}, \overline{3},\dots,\overline{n} \}$. The obvious way is to choose simply $n$ elements. This results in $\binom{2n}{n}$ possibilities.

The other way to choose $n$ elements would be as follows: We partition our set into two sets (namely $A= \{1,2,3,\dots,n\}$ and $\overline{A} = \{\overline{1},\overline{2},\overline{3},\dots,\overline{n}\}$. Then, in the first step we pick $i$ elements from the set $A$ ($i$ random between 0 and $n$). Since we are allowed to take $n$ elements in total, we pick $n-i$ elements from the set $A'$. This means, we picked $n$ elements in total. In the first step, we can pick $i=0$ or $i=1$ or $i=2$ or … or $i=n$ elements. Thus, in total we have $\sum_{i=0}^n \binom{n}{i}\binom{n}{n-i}=\sum_{i=0}^n\binom{n}{i}^2$ possibilities.

So, if we want to construct a bijection, we simply take all elements coming from $A$ and put them into $S$ and all elements coming from $\overline{A}$ and generate the complement set to obtain $T$ for the pair $(S, T)$.