Bijective proof

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In combinatorics, bijective proof is a proof technique that finds a bijective function f : AB between two finite sets A and B, or a size-preserving bijective function between two combinatorial classes, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of counting its elements. Then establishing a bijection from A to some B solves the problem in the case when B is more easily countable. Another useful feature of the technique is that the nature of the bijection itself often provides powerful insights into each or both of the sets.

Basic examples[edit]

Proving the symmetry of the binomial coefficients[edit]

The symmetry of the binomial coefficients states that

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

This means there are exactly as many combinations of k in a set of n as there are combinations of n − k in a set of n.

The bijective proof[edit]

More abstractly and generally, we note that the two quantities asserted to be equal count the subsets of size k and n − k, respectively, of any n-element set S. There is a simple bijection between the two families Fk and Fn − k of subsets of S: it associates every k-element subset with its complement, which contains precisely the remaining n − k elements of S. Since Fk and Fn − k have the same number of elements, the corresponding binomial coefficients must be equal.

Pascal's triangle recurrence relation[edit]

 {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{ for }1 \le k \le n - 1.

The bijective proof[edit]

Proof. We count the number of ways to choose k elements from an n-set. Again, by definition, the left hand side of the equation is the number of ways to choose k from n. Since 1 ≤ kn − 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 right hand side expression. \Box

Other examples[edit]

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:

See also[edit]

External links[edit]

References[edit]