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:
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (1533–1592)