Bijective proof

Encyclopedia : B : BI : BIJ : Bijective proof

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|].

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) = 2ⁿ 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

[\sum_^n = 2^n.]

Bijective proof

Example

See also