Bijective proof
≈ 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.