Bijective proof

Bijective proof

In combinatorics, bijective proof is a proof technique that finds a bijective function "f" : "A" → "B" between two sets "A" and "B", thus proving that they have the same number of elements, |"A"| = |"B"|. 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. Then establishing a bijection from "A" to some more easily countable "B" solves the problem. 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.

Basic examples

Proving the symmetry of the binomial coefficients

The symmetry of the binomial coefficients states that

: {n choose k} = {n choose n-k}.

This means there are exactly as many combinations of "k" in a set of "n" as there are combinations of "n" − "k" in a set of "n".


= Concrete case: "n" = 6, "k" = 2 =

For example, if "n" = 6 and "k" = 2, then "n" − "k" = 6 − 2 = 4, so the identity says there are just as many size-2 subsets of a size-6 set as there are size-4 subsets of a size-6 set, i.e.

: {6 choose 2} = {6 choose 4}.

Here is the bijection, i.e. the one-to-one correspondence between the list of all size-2 subsets and the list of all size-4 subsets of the size-6 set whose members are the six letters "A", "B", "C", "D", "E", "F":

: egin{array}{rrcl}1 & AB & longleftrightarrow & CDEF \2 & AC & longleftrightarrow & BDEF \3 & AD & longleftrightarrow & BCEF \4 & AE & longleftrightarrow & BCDF \5 & AF & longleftrightarrow & BCDE \6 & BC & longleftrightarrow & ADEF \7 & BD & longleftrightarrow & ACEF \8 & BE & longleftrightarrow & ACDF \9 & BF & longleftrightarrow & ACDE \10 & CD & longleftrightarrow & ABEF \11 & CE & longleftrightarrow & ABDF \12 & CF & longleftrightarrow & ABDE \13 & DE & longleftrightarrow & ABCF \14 & DF & longleftrightarrow & ABCE \15 & EF & longleftrightarrow & ABCDend{array}

Each size-2 subset corresponds to its complement—the set of all four letters not included in the size-2 subset. Since there are exactly 15 size-2 subsets, there must be exactly 15 size-4 subsets. In mathematical notation,

: ext{since }{6 choose 2} = 15, ext{ we must also have } {6 choose 4} = 15.

Similarly, the number of size-6 subsets in a size-20 set must be the same as the number of size-14 subsets in a size-20 set, since 20 − 6 = 14.

The bijective proof

More abstractly and generally, we note that the two quantities asserted to be equal count the subsets of size "k" and "n" − "k", respectively, of any "n"-element set "S". There is a simple bijection between the two families "F""k" and "F""n" − "k" of subsets of "S": it associates every "k"-element subset with its complement, which contains precisely the remaining "n" − "k" elements of "S". Since "F""k" and "F""n" − "k" have the same number of elements, the corresponding binomial coefficients must be equal.

Pascal's triangle recurrence relation

: {n choose k} = {n-1 choose k-1} + {n-1 choose k} ext{ for }1 le k le n - 1.


= Concrete case: "n" = 10, "k" = 3 =

Rows 9 and 10 of Pascal's triangle begin as follows:

: egin{array}{ccccccccccccccccccccc} & 1 & & 9 & & 36 & & 84 & & 126 & dots \1 & & 10 & & 45 & & 120 & & 210 & & dotsend{array}

Each number after the initial "1" in row 10 is the sum of the two numbers above it in row 9:

: egin{align}1 + 9 & = 10 \9 + 36 & = 45 \36 + 84 & = 120 \84 + 126 & = 210end{align}

and so on. The case 36 + 84 = 120 involves cases 2 and 3 in row 9 and case 3 in row 10 (the rows start with case 0):

: {9 choose 2} = 36, : {9 choose 3} = 84, : {10 choose 3} = 120 = 36 + 84.

Combinatorially, this says:

: The number of ways to choose 2 out of 9:: plus: the number of ways to choose 3 out of 9:: equals: the number of ways to choose 3 out of 10.

Here are the 36 ways to choose 2 out of 9 and the 84 ways to choose 3 out of 9:

: egin{array}{cccc}overbrace{underbrace{egin{array}{lll}AB & CD & FG \AC & CE & FH \AD & CF & FI \AE & CG & GH \AF & CH & GI \AG & CI & HI \AH & DE \AI & DF \BC & DG \BD & DH \BE & DI \BF & EF \BG & EG \BH & EH \BI & EIend{array_{36 ext{ ways}^ ext{36 ways} & {} {}&overbrace{underbrace{egin{array}{lllll}ABC & AEF & BDE & CDE & DEF \ABD & AEG & BDF & CDF & DEG \ABE & AEH & BDG & CDG & DEH \ABF & AEI & BDH & CDH & DEI \ABG & AFG & BDI & CDI & DFG \ABH & AFH & BEF & CEF & DFH \ABI & AFI & BEG & CEG & DFI \ACD & AGH & BEH & CEH & DGH \ACE & AGI & BEI & CEI & DGI \ACF & AHI & BFG & CFG & DHI \ACG & BCD & BFH & CFH & EFG \ACH & BCE & BFI & CFI & EFH \ACI & BCF & BGH & CGH & EFI \ADE & BCG & BGI & CGI & EGH \ADF & BCH & BHI & CHI & EGI \ADG & BCI & & & EHI \ADH & & & & FGH \ADI & & & & FGI \ & & & & FHI \ & & & & GHIend{array_{84 ext{ ways}^ ext{84 ways}end{array}

This is a list of 36 + 84 = 120 items. The claim is that this corresponds in one-to-one fashion with the list of all 120 ways to choose 3 out of 10. The nine items were the first nine letters, "A"–"I" of the alphabet. Let the tenth item be the tenth letter, "J". Where does "J" go in the list of 120 items above? Since we want to make the list of all ways to choose 3 out of 10, and the first 36 items on the list choose only 2 out of 9, we simply append "J" to those items:

: overbrace{underbrace{egin{array}{lll}ABJ & CDJ & FGJ \ACJ & CEJ & FHJ \ADJ & CFJ & FIJ \vdots & vdots & vdots \vdots & vdots & vdots \BIJ & EIJend{array_{36 ext{ ways}^ ext{36 ways}

Thus the number of ways to choose 2 out of 9 plus the number of ways to choose 3 out of 9 is proved to be equal to the number of ways to choose 3 out of 10.

In the same way, the number of ways to choose 14 out of 40 plus the number of ways 15 out of 40 can be shown to be equal to the number of ways to choose 15 out of 41:

: {40 choose 14} + {40 choose 15} = {41 choose 15},

and so on.

The bijective proof

"Proof".We count the number of ways to choose "k" elements from an "n"-set.Again, by definition, the left hand side of the equation is the number of ways to choose "k" from "n".Since 1 ≤ "k" ≤ "n" − 1, we can pick a fixed element "e" from the "n"-set so that the remaining subset is not empty.For each "k"-set, if "e" is chosen, there are

: {n-1 choose k-1}

ways to choose the remaining "k" − 1 elements among the remaining "n" − 1 choices; otherwise, there are

: {n-1 choose k}

ways to choose the remaining "k" elements among the remaining "n" − 1 choices. Thus, there are

:{n-1 choose k-1} + {n-1 choose k}

ways to choose "k" elements depending on whether "e" is included in each selection, as in the right hand side expression. Box

Other examples

Problems that admit combinatorial proofs are not limited to binomial coefficient identities. As the complexity of the problem increases, a combinatorial proof can become very sophisticated. This technique is particularly useful in areas of discrete mathematics such as combinatorics, graph theory, and number theory.

The most classical examples of bijective proofs in combinatorics include:
* Prüfer sequence, giving a proof of Cayley's formula for the number of labeled trees.
* Robinson-Schensted algorithm, giving a proof of Burnside's formula for the symmetric group.
* Conjugation of Young diagrams, 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

* Cantor–Bernstein–Schroeder theorem
* Double counting (proof technique)
* Combinatorial principles
* Combinatorial proof
* Binomial theorem

External links

*" [http://www.math.dartmouth.edu/~doyle/docs/three/three.pdf "Division by three"] " – by Doyle and Conway.
*" [http://www.emis.ams.org/journals/DMTCS/volumes/abstracts/pdfpapers/dm010104.pdf "A direct bijective proof of the hook-length formula"] " – by Novelli, Pak and Stoyanovsky.
*" [http://www.emis.ams.org/journals/EJC/Volume_4/PDF/v4i1r20.pdf "Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees"] " – by Gilles Schaeffer.
*" [http://www.math.temple.edu/~zeilberg/mamarim/mamarimPDF/ohara.pdf "Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials"] " – by Doron Zeilberger.
*" [http://www.math.umn.edu/~pak/psurvey.pdf "Partition Bijections, a Survey"] " – by Igor Pak.
* [http://mathworld.wolfram.com/Garsia-MilneInvolutionPrinciple.html Garsia-Milne Involution Principle] – from MathWorld.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Combinatorial proof — In mathematics, the term combinatorial proof is often used to mean either of two types of proof of an identity in enumerative combinatorics that either states that two sets of combinatorial configurations, depending on one or more parameters,… …   Wikipedia

  • 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… …   Wikipedia

  • Bijection — A bijective function, f:X→Y, where set X is {1, 2, 3, 4} and set Y is {A, B, C, D}. For example, f(1) = D. A bijection (or bijective function or one to one correspondence) is a function giving an exact pairing of the elements of two… …   Wikipedia

  • Combinatorial principles — In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion exclusion principle are often used for enumerative purposes.… …   Wikipedia

  • Catalan number — For names of numbers in Catalan, see List of numbers in various languages#Occitano Romance. In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively… …   Wikipedia

  • Outline of discrete mathematics — The following outline is presented as an overview of and topical guide to discrete mathematics: Discrete mathematics – study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have… …   Wikipedia

  • Invariant subspace problem — In the field of mathematics known as functional analysis, one of the most prominent open problems is the invariant subspace problem, sometimes optimistically known as the invariant subspace conjecture. It is the question whether the following… …   Wikipedia

  • Cassini and Catalan identities — Cassini s identity and Catalan s identity are mathematical identities for the Fibonacci numbers. The former is a special case of the latter, and states that for the n th Fibonacci number,:F {n 1}F {n+1} F n^2 = ( 1)^n.,Catalan s identity… …   Wikipedia

  • Pascal's rule — In mathematics, Pascal s rule is a combinatorial identity about binomial coefficients. It states that for any natural number n we have:{n 1choose k} + {n 1choose k 1} = {nchoose k} where 1 leq k < n and {nchoose k} is a binomial… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”