Bijective proof

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In combinatorics, bijective proof is a proof technique that finds a bijective function (that is, a one-to-one and onto function) f : A → B between two finite sets A and B, or a size-preserving bijective function between two combinatorial classes, thus proving that they have the same number of elements, |A| = |B|. Bijective proof_sentence_0

One place the technique is useful is where we wish to know the size of A, but can find no direct way of counting its elements. Bijective proof_sentence_1

By establishing a bijection from A to some B solves the problem if B is more easily countable. Bijective proof_sentence_2

Another useful feature of the technique is that the nature of the bijection itself often provides powerful insights into each or both of the sets. Bijective proof_sentence_3

Basic examples Bijective proof_section_0

Proving the symmetry of the binomial coefficients Bijective proof_section_1

The symmetry of the binomial coefficients states that Bijective proof_sentence_4

This means that there are exactly as many combinations of k things in a set of size n as there are combinations of n − k things in a set of size n. Bijective proof_sentence_5

A bijective proof Bijective proof_section_2

The key idea of the proof may be understood from a simple example: selecting out of a group of n children which k to reward with ice cream cones has exactly the same effect as choosing instead the n − k children to be denied them. Bijective proof_sentence_6

Other examples Bijective proof_section_3

Problems that admit bijective proofs are not limited to binomial coefficient identities. Bijective proof_sentence_7

As the complexity of the problem increases, a bijective proof can become very sophisticated. Bijective proof_sentence_8

This technique is particularly useful in areas of discrete mathematics such as combinatorics, graph theory, and number theory. Bijective proof_sentence_9

The most classical examples of bijective proofs in combinatorics include: Bijective proof_sentence_10

Bijective proof_unordered_list_0

See also Bijective proof_section_4

Bijective proof_unordered_list_1


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Bijective proof.