An interesting bijection
I came across the following identity recently: . This can be proved in various ways. Here, I will describe a “combinatorial proof”.
First of all, we note the following: is the number of pairs of subsets , such that . Moreover, is the number of possibilities to choose items out of set containing items. This means, there must be a bijection from the pairs of subsets (as described before) and the subsets of cardinality of a set containing elements.
To construct such a solution, we first note the following: , a very basic identity of binomial coefficients. This means . However, this corresponds to the number of possible pairs of sets with . For convenience we can simply say .
Now we desribe the process of choosing elements from the -element set . The obvious way is to choose simply elements. This results in possibilities.
The other way to choose elements would be as follows: We partition our set into two sets (namely and . Then, in the first step we pick elements from the set ( random between 0 and ). Since we are allowed to take elements in total, we pick elements from the set . This means, we picked elements in total. In the first step, we can pick or or or … or elements. Thus, in total we have possibilities.
So, if we want to construct a bijection, we simply take all elements coming from and put them into and all elements coming from and generate the complement set to obtain for the pair .