Bijective proof

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count.

Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.

In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count.

Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.

Basic examples

{n \choose k} = {n \choose n-k}. This means that there are exactly as many combinations of things in a set of size as there are combinations of things in a set of size  . The key idea of the bijective proof may be understood from a simple example: selecting children to be rewarded with ice cream cones, out of a group of children, has exactly the same effect as choosing instead the children to be denied ice cream cones.

See also

Binomial theorem Schröder–Bernstein theorem Double counting (proof technique) Combinatorial principles Combinatorial proof Categorification

Further reading

Loehr, Nicholas A. (2011). Bijective Combinatorics. CRC Press. , .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369588067 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.