# An interesting bijection

Posted on 2014 03 21 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)$$.