Bijective proof

From Wikipedia, the free encyclopedia

In combinatorics, bijective proof, is a proof technique that finds a bijective function

$f:A \rightarrow B$

between two sets $A$ and $B$ and thus proves that both sets have the same number of elements: $| A | = | B |$ .

1 Basic examples
- 1.1 Symmetry of the binomial coefficients:
- 1.2 Pascal's triangle recurrence relation:
2 Other examples
3 See also
4 External links

[edit] Basic examples

[edit] Symmetry of the binomial coefficients:

${n \choose k} = {n \choose n-k}$

Proof. We count the number of ways choosing k elements from an n-set. By definition, the l.h.s. is the number of ways choosing k from n. But each time we choose any k elements, we must also leave behind n − k elements, which is the same as choosing n − k elements (to leave behind). So this number must also equal to the r.h.s. $\Box$

[edit] Pascal's triangle recurrence relation:

${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$ for all 1 ≤ k ≤ n − 1.

Proof. We count the number of ways choosing k elements from an n-set. Again, by definition, the l.h.s. is the number of ways choosing k from n. Since 1 ≤ k ≤ n − 1, we can pick a fixed element e from the n-set so that the remaining subset is not empty. For each k-set, if e is chosen, there are

${n-1 \choose k-1}$

ways to choose the remaining k − 1 elements among the remaining n − 1 choices; otherwise, there are

${n-1 \choose k}$

ways to choose the remaining k elements among the remaining n − 1 choices. Thus, there are

${n-1 \choose k-1} + {n-1 \choose k}$

ways to choose k elements depending on whether e is included in each selection, as in the r.h.s. $\Box$

[edit] Other examples

Problems that admit combinatorial proofs are not limited to binomial coefficient identities. As the complexity of the problem increases, a combinatorial proof can become very sophisticated. This technique is particularly useful in areas of discrete mathematics such as combinatorics, graph theory, and number theory.

The most classical examples of bijective proofs in combinatorics include: