Bijective proof
From Free net encyclopedia
In combinatorics, bijective proof, is a proof technique that finds a bijective function
- <math>f:A \rightarrow B</math>
between two sets <math>A</math> and <math>B</math> and thus proves that both sets have the same number of elements: <math>|A| = |B|</math>.
Example
For instance, consider the number of ways in which a committee can be formed from a total of n people:
Set B: Each committee K can be represented as a binary sequence of length n. A 1 at i-th place means that the i-th person belongs to the committee and 0 at the i-th place means that the i-th person does not belong to the committee. Therefore there are a total of 2 × 2 × ... × 2 (n times) = 2n possibilities.
Set A: The same committee K can be viewed as a subset of an n-set. The size of the committee must be some number between 0 and n. The number of ways in which a committee of r people can be formed from a total of n people is C(n,r) (this is a well known result; see binomial coefficient). Therefore the total number of ways is C(n,r) summed over r = 0, 1, 2, ... n (by the rule of sum).
Bijective function: In this case the bijection f is the correspondence between a subset of an n-set and its characteristic vector.
Equating the two expressions gives
- <math>\sum_{r=0}^n {C(n,r)} = 2^n.</math>