Combinatorial proof
From Wikipedia, the free encyclopedia
The term combinatorial proof is often used in either of two senses:
- A proof by double counting. A combinatorial identity, is proved by counting some carefully chosen object in two different ways to obtain different expressions in the statement. Since those expressions count the same object, they must be equal to each other and thus the statement is established.
- A bijective proof. Two sets are shown to have the same number of members by exhibiting a bijection, i.e. a one-to-one correspondence, between them.
[edit] Examples
[edit] Double counting
A subcommittee of k members is chosen from a committee of n members, and then one of the k members of the subcommittee is chosen to be the chair. The number of ways to do this is
Alternatively, we first choose the chair from among all n members of the original committee and then choose the k − 1 other subcommittee members from among the n − 1 other members of the original committee. The number of ways to do this is
Therefore, we conclude that
A similar technique proves Vandermonde's identity.
[edit] Bijective proof
Suppose we wish to show that the number of size-k subsets of a size-n set is the same as the number of size-(n − k) subsets of a size-n set, i.e., that
This can be accomplished by exhibiting a bijection between the set of all size-k subsets and the set of all size-(n − k) subsets. One such bijection—probably the simplest—is the correspondence between each size-k subset and its complement relative to the larger size-n set.
