Bijective proof

From Wikipedia, the free encyclopedia

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

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

Contents 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:

Proof. We count the number of ways choosing k elements from an n-set. By definition, the expression on the left hand side of the equation 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 that this number must also equal the right hand side of the equation.

[edit] Pascal's triangle recurrence relation:

for all 1 ≤ k ≤ n − 1.

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 ≤ 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

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

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

ways to choose k elements depending on whether e is included in each selection, as in the right hand side expression.

[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:

• Prüfer sequence, giving a proof of Cayley's formula for the number of labeled trees.
• Robinson-Schensted algorithm, giving a proof of Burnside's formula for the symmetric group.
• Conjugation of Young diagrams, giving a proof of a classical result on the number of certain integer partitions.
• Bijective proofs of the pentagonal number theorem.
• Bijective proofs of the formula for the Catalan numbers.

[edit] See also

• Cantor–Bernstein–Schroeder theorem
• Double counting (proof technique)
• Combinatorial principles
• Combinatorial proof
• Binomial theorem

[edit] External links

• "Division by three" – by Doyle and Conway.
• "A direct bijective proof of the hook-length formula" – by Novelli, Pak and Stoyanovsky.
• "Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees" – by Gilles Schaeffer.
• "Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials" – by Doron Zeilberger.
• "Partition Bijections, a Survey" – by Igor Pak.
• Garsia-Milne Involution Principle – from MathWorld.