An interesting bijection

by phimuemue

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).