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.
Read more about this topic: Bijective Proof
Famous quotes containing the word examples:
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)