HOME

TheInfoList



OR:

In
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, 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 c ...
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


Proving the symmetry of the binomial coefficients

The symmetry of the binomial coefficients states that : = . 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 .


A bijective proof

The key idea of the 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. More abstractly and generally, the two quantities asserted to be equal count the subsets of size and , respectively, of any -element set . Let be the set of all -element subsets of , the set has size \tbinom. Let be the set of all subsets of , the set B has size \tbinom. There is a simple bijection between the two sets and : it associates every -element subset (that is, a member of ) with its complement, which contains precisely the remaining elements of , and hence is a member of . More formally, this can be written using functional notation as, defined by for any -element subset of and the complement taken in . To show that f is a bijection, first assume that , that is to say, . Take the complements of each side (in ), using the fact that the complement of a complement of a set is the original set, to obtain . This shows that is one-to-one. Now take any -element subset of in , say . Its complement in , , is a -element subset, and so, an element of . Since , is also onto and thus a bijection. The result now follows since the existence of a bijection between these finite sets shows that they have the same size, that is, \tbinom = \tbinom.


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 continuou ...
such as
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
,
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, and
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
. The most classical examples of bijective proofs in combinatorics include: *
Prüfer sequence In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on ''n'' vertices has length ''n'' − 2, and can be ...
, 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 number of spanning tre ...
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 group ...
. *
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 ...
of
Young diagram In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups ...
s, 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.


See also

* Binomial theorem * Schröder–Bernstein theorem *
Double counting (proof technique) In combinatorics, double counting, also called counting in two ways, is a combinatorial proof technique for showing that two expressions are equal by demonstrating that they are two ways of counting the size of one set. In this technique, which c ...
* Combinatorial principles * Combinatorial proof * Categorification


References


Further reading

* Loehr, Nicholas A. (2011).
Bijective Combinatorics

CRC Press
, .


External links

*
"Division by three"
' – by Doyle and Conway. *
"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. {{DEFAULTSORT:Bijective Proof Enumerative combinatorics Articles containing proofs Mathematical proofs