combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

, bijective proof is a

proof Proof most often refers to: * Proof (truth), argument or sufficient evidence for the truth of a proposition * Alcohol proof, a measure of an alcoholic drink's strength Proof may also refer to: Mathematics and formal logic * Formal proof, a co ...

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 In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivale ...

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

Proving the symmetry of the binomial coefficients

The symmetry of the binomial coefficients states that :

= .

This means that there are exactly as many

combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are ...

s 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.

Other examples

Problems that admit bijective proofs are not limited to binomial coefficient identities. As the complexity of the problem increases, a bijective proof can become very sophisticated. This technique is particularly useful in areas of

discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

such as

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, and

number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

. The most classical examples of bijective proofs in combinatorics include: * Prüfer sequence, giving a proof of

Cayley's formula In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^. The formula equivalently counts the spanning trees of a ...

for the number of labeled trees. * Robinson-Schensted algorithm, giving a proof of Burnside's formula for the

symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric grou ...

. *

Conjugation Conjugation or conjugate may refer to: Linguistics *Grammatical conjugation, the modification of a verb from its basic form *Emotive conjugation or Russell's conjugation, the use of loaded language Mathematics *Complex conjugation, the change o ...

of Young diagrams, giving a proof of a classical result on the number of certain

integer partition In number theory and combinatorics, a partition of a non-negative integer , also called an integer partition, is a way of writing as a summation, sum of positive integers. Two sums that differ only in the order of their summands are considered ...

s. * Bijective proofs of the pentagonal number theorem. * Bijective proofs of the formula for the

Catalan number The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...

References

External links

*
"Division by three"
' – by Doyle and

Conway Conway may refer to: Places United States * Conway, Arkansas * Conway County, Arkansas * Lake Conway, Arkansas * Conway, Florida * Conway, Iowa * Conway, Kansas * Conway, Louisiana * Conway, Massachusetts * Conway, Michigan * Conway Townshi ...

. *
"A direct bijective proof of the hook-length formula"
' – by Novelli, Pak and Stoyanovsky. *
"Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees"
' – by Gilles Schaeffer. *
"Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials"
' – by Doron Zeilberger. *
"Partition Bijections, a Survey"
' – by Igor Pak.
Garsia-Milne Involution Principle
– from

MathWorld ''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science ...

. {{DEFAULTSORT:Bijective Proof Enumerative combinatorics Articles containing proofs Mathematical proofs

Basic examples

Proving the symmetry of the binomial coefficients

Other examples

See also

References

Further reading

External links