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)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)