An interesting bijection

Posted on September 11, 2011 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)\).