https://en.formulasearchengine.com/index.php?title=Combinatorial_proof&feed=atom&action=historyCombinatorial proof - Revision history2020-10-28T03:30:22ZRevision history for this page on the wikiMediaWiki 1.36.0-alphahttps://en.formulasearchengine.com/index.php?title=Combinatorial_proof&diff=6439&oldid=preven>Will Orrick: hide explicit wikilink2013-09-15T16:50:16Z<p>hide explicit wikilink</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:50, 15 September 2013</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>In [[mathematics]], the term '''''combinatorial proof''''' is often used to mean either of two types of [[mathematical <del class="diffchange diffchange-inline">proof|</del>proof]] <del class="diffchange diffchange-inline">of an </del>[[<del class="diffchange diffchange-inline">identity </del>(<del class="diffchange diffchange-inline">mathematics</del>)|<del class="diffchange diffchange-inline">identity</del>]] <del class="diffchange diffchange-inline">in </del>[[<del class="diffchange diffchange-inline">enumerative </del>combinatorics]] <del class="diffchange diffchange-inline">that either states that two sets of combinatorial configurations, depending on one or more parameters, have </del>the <del class="diffchange diffchange-inline">same </del>number of elements <del class="diffchange diffchange-inline">(for all values </del>of the <del class="diffchange diffchange-inline">parameters)</del>, <del class="diffchange diffchange-inline">or gives a formula for </del>the <del class="diffchange diffchange-inline">number of one such set of configurations in terms of the parameters:</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>In [[mathematics]], the term '''''combinatorial proof''''' is often used to mean either of two types of [[mathematical proof]]<ins class="diffchange diffchange-inline">:</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* A proof by </ins>[[<ins class="diffchange diffchange-inline">double counting </ins>(<ins class="diffchange diffchange-inline">proof technique</ins>)|<ins class="diffchange diffchange-inline">double counting</ins>]]<ins class="diffchange diffchange-inline">. A </ins>[[combinatorics<ins class="diffchange diffchange-inline">|combinatorial]] [[identity (mathematics)|identity</ins>]] <ins class="diffchange diffchange-inline">is proven by counting </ins>the number of elements of <ins class="diffchange diffchange-inline">some carefully chosen set in two different ways to obtain the different expressions in </ins>the <ins class="diffchange diffchange-inline">identity. Since those expressions count the same objects</ins>, <ins class="diffchange diffchange-inline">they must be equal to each other and thus </ins>the <ins class="diffchange diffchange-inline">identity is established.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* A [[bijective proof]]<del class="diffchange diffchange-inline">, which exhibits </del>a [[bijection]], i.e. a one-to-one correspondence, between <del class="diffchange diffchange-inline">the two sets, or (in the case of a formula) between the given set and a set obviously counted by the formula</del>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* A [[bijective proof]]<ins class="diffchange diffchange-inline">. Two sets are shown to have the same number of members by exhibiting </ins>a [[bijection]], i.e. a one-to-one correspondence, between <ins class="diffchange diffchange-inline">them</ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* A proof by [[double counting (proof technique)|double counting]]. Some combinatorial set ''S'', often different from the ones in question, is counted in two different ways, and from the equality of the numbers so found the desired identity is deduced. The two ways of counting ''S'' must each be by establishing a bijection of ''S'' with a set obviously counted by the number found.</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The term "combinatorial proof" may also be used more broadly to refer to any kind of [[elementary proof]] in combinatorics. However, as {{harvtxt|Glass|2003}} writes in his review of {{harvtxt|Benjamin|Quinn|2003}} (a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The term "combinatorial proof" may also be used more broadly to refer to any kind of [[elementary proof]] in combinatorics. However, as {{harvtxt|Glass|2003}} writes in his review of {{harvtxt|Benjamin|Quinn|2003}} (a book about combinatorial proofs), these two simple techniques are enough to prove many <del class="diffchange diffchange-inline">of the important </del>theorems in combinatorics and number theory.</div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Example==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Example==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>An archetypal double counting proof is for the well known formula for the number <math>\tbinom nk</math> of ''k''-[[combination]]s (i.e., subsets of size ''k'') of an ''n''-element set:</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>An archetypal double counting proof is for the well known formula for the number <math>\tbinom nk</math> of ''k''-[[combination]]s (i.e., subsets of size ''k'') of an ''n''-element set:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:<math>\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}.</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:<math>\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}.</math></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Here a direct bijective proof is not possible<del class="diffchange diffchange-inline">, </del>because the right-hand side of the identity <del class="diffchange diffchange-inline">being </del>a fraction, there is no set ''obviously'' counted by it (it even takes some thought to see that the denominator always evenly divides the numerator). However its numerator counts the [[Cartesian product]] of ''k'' finite sets of sizes ''n'', {{nowrap|''n'' − 1}}, ..., {{nowrap|''n'' − ''k'' + 1}}, while its denominator counts the [[permutations]] of a ''k''-element set (the set most obviously <del class="diffchange diffchange-inline">counted </del>counted by the denominator would be another Cartesian product ''k'' finite sets; if desired one could map permutations to that set by an explicit bijection). Now take ''S'' to be the set of sequences <del class="diffchange diffchange-inline">without repetition </del>of elements selected from our ''n''-element set. On one hand there is an easy bijection of ''S'' with the Cartesian product corresponding to the numerator <math>n(n-1)\cdots(n-k+1)</math>, and on the other hand there is a bijection from the set of pairs of a ''k''-combination <del class="diffchange diffchange-inline">''C'' </del>and a permutation ''σ'' of ''k'' to ''S'', by taking the elements of ''C'' in increasing order, and then permuting this sequence by&nbsp;''σ'' to obtain an element of&nbsp;''S''. The two ways of counting give the equation</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Here a direct bijective proof is not possible<ins class="diffchange diffchange-inline">: </ins>because the right-hand side of the identity <ins class="diffchange diffchange-inline">is </ins>a fraction, there is no set ''obviously'' counted by it (it even takes some thought to see that the denominator always evenly divides the numerator). However its numerator counts the [[Cartesian product]] of ''k'' finite sets of sizes ''n'', {{nowrap|''n'' − 1}}, ..., {{nowrap|''n'' − ''k'' + 1}}, while its denominator counts the [[permutations]] of a ''k''-element set (the set most obviously counted by the denominator would be another Cartesian product ''k'' finite sets; if desired one could map permutations to that set by an explicit bijection). Now take ''S'' to be the set of sequences of <ins class="diffchange diffchange-inline">''k'' </ins>elements selected from our ''n''-element set <ins class="diffchange diffchange-inline">without repetition</ins>. On one hand<ins class="diffchange diffchange-inline">, </ins>there is an easy bijection of ''S'' with the Cartesian product corresponding to the numerator <math>n(n-1)\cdots(n-k+1)</math>, and on the other hand there is a bijection from the set <ins class="diffchange diffchange-inline">''C'' </ins>of pairs of a ''k''-combination and a permutation ''σ'' of ''k'' to ''S'', by taking the elements of ''C'' in increasing order, and then permuting this sequence by&nbsp;''σ'' to obtain an element of&nbsp;''S''. The two ways of counting give the equation</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:<math>n(n-1)\cdots(n-k+1)=\binom nk k!,</math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:<math>n(n-1)\cdots(n-k+1)=\binom nk k!,</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>and after division by ''k''! this leads to the stated formula for <math>\tbinom nk</math>. In general, if the counting formula involves a division, a similar double counting argument (if it exists) gives the most straightforward combinatorial proof of the identity, but double counting arguments are not limited to situations where the formula is of this form.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>and after division by ''k''! this leads to the stated formula for <math>\tbinom nk</math>. In general, if the counting formula involves a division, a similar double counting argument (if it exists) gives the most straightforward combinatorial proof of the identity, but double counting arguments are not limited to situations where the formula is of this form.</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l27" >Line 27:</td>
<td colspan="2" class="diff-lineno">Line 26:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>An alternative bijective proof, given by Aigner and Ziegler and credited by them to [[André Joyal]], involves a bijection between, on the one hand, ''n''-node trees with two designated nodes (that may be the same as each other), and on the other hand, ''n''-node [[directed graph|directed]] [[pseudoforest]]s. If there are ''T<sub>n</sub>'' ''n''-node trees, then there are ''n''<sup>2</sup>''T<sub>n</sub>'' trees with two designated nodes. And a pseudoforest may be determined by specifying, for each of its nodes, the endpoint of the edge extending outwards from that node; there are ''n'' possible choices for the endpoint of a single edge (allowing self-loops) and therefore ''n<sup>n</sup>'' possible pseudoforests. By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that ''T<sub>n</sub>''&nbsp;=&nbsp;''n''<sup>''n''&nbsp;&minus;&nbsp;2</sup>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>An alternative bijective proof, given by Aigner and Ziegler and credited by them to [[André Joyal]], involves a bijection between, on the one hand, ''n''-node trees with two designated nodes (that may be the same as each other), and on the other hand, ''n''-node [[directed graph|directed]] [[pseudoforest]]s. If there are ''T<sub>n</sub>'' ''n''-node trees, then there are ''n''<sup>2</sup>''T<sub>n</sub>'' trees with two designated nodes. And a pseudoforest may be determined by specifying, for each of its nodes, the endpoint of the edge extending outwards from that node; there are ''n'' possible choices for the endpoint of a single edge (allowing self-loops) and therefore ''n<sup>n</sup>'' possible pseudoforests. By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that ''T<sub>n</sub>''&nbsp;=&nbsp;''n''<sup>''n''&nbsp;&minus;&nbsp;2</sup>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a <del class="diffchange diffchange-inline">double counting proof due to Jim Pitman, presented in more detail in </del>[[Double counting (proof technique)#Counting trees]]. In this proof, Pitman considers the sequences of directed edges that may be added to an ''n''-node [[empty graph]] to form from it a single rooted tree, and counts the number of such sequences in two different ways. By showing how to derive a sequence of this type by choosing a tree, a root for the tree, and an ordering for the edges in the tree, he shows that there are ''T<sub>n</sub>n''! possible sequences of this type. And by counting the number of ways in which a partial sequence can be extended by a single edge, he shows that there are ''n''<sup>''n''&nbsp;&minus;&nbsp;2</sup>''n''! possible sequences. Equating these two different formulas for the size of the same set of edge sequences and cancelling the common factor of ''n''! leads to Cayley's formula.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a [[Double counting (proof technique)#Counting trees<ins class="diffchange diffchange-inline">|double counting proof due to Jim Pitman</ins>]]. In this proof, Pitman considers the sequences of directed edges that may be added to an ''n''-node [[empty graph]] to form from it a single rooted tree, and counts the number of such sequences in two different ways. By showing how to derive a sequence of this type by choosing a tree, a root for the tree, and an ordering for the edges in the tree, he shows that there are ''T<sub>n</sub>n''! possible sequences of this type. And by counting the number of ways in which a partial sequence can be extended by a single edge, he shows that there are ''n''<sup>''n''&nbsp;&minus;&nbsp;2</sup>''n''! possible sequences. Equating these two different formulas for the size of the same set of edge sequences and cancelling the common factor of ''n''! leads to Cayley's formula.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Related concepts==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Related concepts==</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l58" >Line 58:</td>
<td colspan="2" class="diff-lineno">Line 57:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> | publisher = [[Mathematical Association of America]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> | publisher = [[Mathematical Association of America]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> | year = 2003</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> | year = 2003</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> | url = http://www.maa.org/reviews/<del class="diffchange diffchange-inline">reallycount.html</del>}}.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> | url = http://www.maa.org/<ins class="diffchange diffchange-inline">publications/maa-</ins>reviews/<ins class="diffchange diffchange-inline">proofs-that-really-count</ins>}}.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*{{citation|title=Enumerative Combinatorics, Volume I|first=Richard P.|last=Stanley|authorlink=Richard P. Stanley|series=Cambridge Studies in Advanced Mathematics|volume=49|publisher=Cambridge University Press|year=1997|isbn=0-521-55309-1|pages=11–12}}.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>*{{citation|title=Enumerative Combinatorics, Volume I|first=Richard P.|last=Stanley|authorlink=Richard P. Stanley|series=Cambridge Studies in Advanced Mathematics|volume=49|publisher=Cambridge University Press|year=1997|isbn=0-521-55309-1|pages=11–12}}.</div></td></tr>
</table>en>Will Orrickhttps://en.formulasearchengine.com/index.php?title=Combinatorial_proof&diff=233994&oldid=preven>Helpful Pixie Bot: ISBNs (Build KH)2012-05-12T03:52:28Z<p>ISBNs (Build KH)</p>
<p><b>New page</b></p><div>In [[mathematics]], the term '''''combinatorial proof''''' is often used to mean either of two types of [[mathematical proof|proof]] of an [[identity (mathematics)|identity]] in [[enumerative combinatorics]] that either states that two sets of combinatorial configurations, depending on one or more parameters, have the same number of elements (for all values of the parameters), or gives a formula for the number of one such set of configurations in terms of the parameters:<br />
<br />
* A [[bijective proof]], which exhibits a [[bijection]], i.e. a one-to-one correspondence, between the two sets, or (in the case of a formula) between the given set and a set obviously counted by the formula.<br />
<br />
* A proof by [[double counting (proof technique)|double counting]]. Some combinatorial set ''S'', often different from the ones in question, is counted in two different ways, and from the equality of the numbers so found the desired identity is deduced. The two ways of counting ''S'' must each be by establishing a bijection of ''S'' with a set obviously counted by the number found.<br />
<br />
The term "combinatorial proof" may also be used more broadly to refer to any kind of [[elementary proof]] in combinatorics. However, as {{harvtxt|Glass|2003}} writes in his review of {{harvtxt|Benjamin|Quinn|2003}} (a book about combinatorial proofs), these two simple techniques are enough to prove many of the important theorems in combinatorics and number theory.<br />
<br />
==Example==<br />
An archetypal double counting proof is for the well known formula for the number <math>\tbinom nk</math> of ''k''-[[combination]]s (i.e., subsets of size ''k'') of an ''n''-element set:<br />
:<math>\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}.</math><br />
Here a direct bijective proof is not possible, because the right-hand side of the identity being a fraction, there is no set ''obviously'' counted by it (it even takes some thought to see that the denominator always evenly divides the numerator). However its numerator counts the [[Cartesian product]] of ''k'' finite sets of sizes ''n'', {{nowrap|''n'' − 1}}, ..., {{nowrap|''n'' − ''k'' + 1}}, while its denominator counts the [[permutations]] of a ''k''-element set (the set most obviously counted counted by the denominator would be another Cartesian product ''k'' finite sets; if desired one could map permutations to that set by an explicit bijection). Now take ''S'' to be the set of sequences without repetition of elements selected from our ''n''-element set. On one hand there is an easy bijection of ''S'' with the Cartesian product corresponding to the numerator <math>n(n-1)\cdots(n-k+1)</math>, and on the other hand there is a bijection from the set of pairs of a ''k''-combination ''C'' and a permutation ''σ'' of ''k'' to ''S'', by taking the elements of ''C'' in increasing order, and then permuting this sequence by&nbsp;''σ'' to obtain an element of&nbsp;''S''. The two ways of counting give the equation<br />
:<math>n(n-1)\cdots(n-k+1)=\binom nk k!,</math><br />
and after division by ''k''! this leads to the stated formula for <math>\tbinom nk</math>. In general, if the counting formula involves a division, a similar double counting argument (if it exists) gives the most straightforward combinatorial proof of the identity, but double counting arguments are not limited to situations where the formula is of this form.<br />
<br />
== The benefit of a combinatorial proof == <!-- Binomial coefficient links here --><br />
<br />
{{harvtxt|Stanley|1997}} gives an example of a [[combinatorial enumeration]] problem (counting the number of sequences of ''k'' subsets ''S''<sub>1</sub>, ''S''<sub>2</sub>, ... ''S''<sub>''k''</sub>, that can be formed from a set of ''n'' items such that the subsets have an empty common intersection) with two different proofs for its solution. The first proof, which is not combinatorial, uses [[mathematical induction]] and [[generating function]]s to find that the number of sequences of this type is (2<sup>''k''</sup>&nbsp;&minus;1)<sup>''n''</sup>. The second proof is based on the observation that there are 2<sup>''k''</sup>&nbsp;&minus;1 [[proper subset]]s of the set {1, 2, ..., ''k''}, and (2<sup>''k''</sup>&nbsp;&minus;1)<sup>''n''</sup> functions from the set {1, 2, ..., ''n''} to the family of proper subsets of {1, 2, ..., ''k''}. The sequences to be counted can be placed in one-to-one correspondence with these functions, where the function formed from a given sequence of subsets maps each element ''i'' to the set {''j''&nbsp;|&nbsp;''i''&nbsp;&isin;&nbsp;''S''<sub>''j''</sub>}.<br />
<br />
Stanley writes, “Not only is the above combinatorial proof much shorter than our previous proof, but also it makes the reason for the simple answer completely transparent. It is often the case, as occurred here, that the first proof to come to mind turns out to be laborious and inelegant, but that the final answer suggests a simple combinatorial proof.” Due both to their frequent greater elegance than non-combinatorial proofs and the greater insight they provide into the structures they describe, Stanley formulates a general principle that combinatorial proofs are to be preferred over other proofs, and lists as exercises many problems of finding combinatorial proofs for mathematical facts known to be true through other means.<br />
<br />
==The difference between bijective and double counting proofs==<br />
Stanley does not clearly distinguish between bijective and double counting proofs, and gives examples of both kinds, but the difference between the two types of combinatorial proof can be seen in an example provided by {{harvtxt|Aigner|Ziegler|1998}}, of proofs for [[Cayley's formula]] stating that there are ''n''<sup>''n''&nbsp;&minus;&nbsp;2</sup> different [[tree (graph theory)|trees]] that can be formed from a given set of ''n'' nodes. Aigner and Ziegler list four proofs of this theorem, the first of which is bijective and the last of which is a double counting argument. They also mention but do not describe the details of a fifth bijective proof.<br />
<br />
The most natural way to find a bijective proof of this formula would be to find a bijection between ''n''-node trees and some collection of objects that has ''n''<sup>''n''&nbsp;&minus;&nbsp;2</sup> members, such as the sequences of ''n''&nbsp;&minus;&nbsp;2 values each in the range from 1 to ''n''. Such a bijection can be obtained using the [[Prüfer sequence]] of each tree. Any tree can be uniquely encoded into a Prüfer sequence, and any Prüfer sequence can be uniquely decoded into a tree; these two results together provide a bijective proof of Cayley's formula.<br />
<br />
An alternative bijective proof, given by Aigner and Ziegler and credited by them to [[André Joyal]], involves a bijection between, on the one hand, ''n''-node trees with two designated nodes (that may be the same as each other), and on the other hand, ''n''-node [[directed graph|directed]] [[pseudoforest]]s. If there are ''T<sub>n</sub>'' ''n''-node trees, then there are ''n''<sup>2</sup>''T<sub>n</sub>'' trees with two designated nodes. And a pseudoforest may be determined by specifying, for each of its nodes, the endpoint of the edge extending outwards from that node; there are ''n'' possible choices for the endpoint of a single edge (allowing self-loops) and therefore ''n<sup>n</sup>'' possible pseudoforests. By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that ''T<sub>n</sub>''&nbsp;=&nbsp;''n''<sup>''n''&nbsp;&minus;&nbsp;2</sup>.<br />
<br />
Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a double counting proof due to Jim Pitman, presented in more detail in [[Double counting (proof technique)#Counting trees]]. In this proof, Pitman considers the sequences of directed edges that may be added to an ''n''-node [[empty graph]] to form from it a single rooted tree, and counts the number of such sequences in two different ways. By showing how to derive a sequence of this type by choosing a tree, a root for the tree, and an ordering for the edges in the tree, he shows that there are ''T<sub>n</sub>n''! possible sequences of this type. And by counting the number of ways in which a partial sequence can be extended by a single edge, he shows that there are ''n''<sup>''n''&nbsp;&minus;&nbsp;2</sup>''n''! possible sequences. Equating these two different formulas for the size of the same set of edge sequences and cancelling the common factor of ''n''! leads to Cayley's formula.<br />
<br />
==Related concepts==<br />
*The principles of double counting and bijection used in combinatorial proofs can be seen as examples of a larger family of [[combinatorial principles]], which include also other ideas such as the [[pigeonhole principle]].<br />
*Proving an identity combinatorially can be viewed as adding more structure to the identity by replacing numbers by sets; similarly, [[categorification]] is the replacement of sets by categories.<br />
<br />
==References==<br />
*{{citation<br />
| last1 = Aigner | first1 = Martin<br />
| last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler<br />
| pages = 141–146<br />
| publisher = [[Springer-Verlag]]<br />
| title = [[Proofs from THE BOOK]]<br />
| year = 1998<br />
| isbn = 3-540-40460-0}}.<br />
<br />
*{{citation<br />
| title = Proofs that Really Count: The Art of Combinatorial Proof<br />
| first1 = Arthur T. | last1 = Benjamin<br />
| first2 = Jennifer J. | last2 = Quinn<br />
| publisher = [[Mathematical Association of America]]<br />
| series = Dolciani Mathematical Expositions<br />
| volume = 27<br />
| year = 2003<br />
| isbn = 978-0-88385-333-7}}.<br />
<br />
*{{citation<br />
| first = Darren | last = Glass<br />
| title = Read This: Proofs that Really Count<br />
| publisher = [[Mathematical Association of America]]<br />
| year = 2003<br />
| url = http://www.maa.org/reviews/reallycount.html}}.<br />
<br />
*{{citation|title=Enumerative Combinatorics, Volume I|first=Richard P.|last=Stanley|authorlink=Richard P. Stanley|series=Cambridge Studies in Advanced Mathematics|volume=49|publisher=Cambridge University Press|year=1997|isbn=0-521-55309-1|pages=11–12}}.<br />
<br />
[[Category:Enumerative combinatorics]]<br />
[[Category:Mathematical proofs]]</div>en>Helpful Pixie Bot