Editing Double counting (proof technique) (section)

==Examples==

===Multiplication (of natural numbers) commutes===
This is a simple example of double counting, often used when teaching multiplication to young children. In this context, multiplication of [[natural number]]s is introduced as repeated addition, and is then shown to be [[Commutative_property|commutative]] by counting,  in two different ways, a number of items arranged in a rectangular grid.  Suppose the grid has <math>n</math> rows and <math>m</math> columns.  We first count the items by summing <math>n</math> rows of <math>m</math> items each, then a second time by summing <math>m</math> columns of <math>n</math> items each, thus showing that, for these particular values of <math>n</math> and <math>m</math>, <math>n \times m = m \times n</math>.

===Forming committees===
One example of the double counting method counts the number of ways in which a committee can be formed from <math>n</math> people, allowing any number of the people (even zero of them) to be part of the committee. That is, one counts the number of [[subset]]s that an <math>n</math>-element set may have. One method for forming a committee is to ask each person to choose whether or not to join it. Each person has two choices – yes or no – and these choices are independent of those of the other people. Therefore there are <math>2\times 2\times \cdots 2 = 2^n</math> possibilities. Alternatively, one may observe that the size of the committee must be some number between 0 and <math>n</math>. For each possible size <math>k</math>, the number of ways in which a committee of <math>k</math> people can be formed from <math>n</math> people is the [[binomial coefficient]]
<math display=block>{n \choose k}.</math>
Therefore the total number of possible committees is the sum of binomial coefficients over <math>k=0,1,2,\dots,n</math>. Equating the two expressions gives the [[Identity (mathematics)|identity]]
<math display=block>\sum_{k=0}^n {n \choose k} = 2^n,</math>
a special case of the [[binomial theorem]]. A similar double counting method can be used to prove the more general identity<ref>{{harvnb|Garbano|Malerba|Lewinter|2003}}; {{harvnb|Klavžar|2006}}).</ref>
<math display=block>\sum_{k=d}^n {n\choose k}{k\choose d} = 2^{n-d}{n\choose d}</math>

===Handshaking lemma===
{{main|Handshaking lemma}}
Another theorem that is commonly proven with a double counting argument states that every [[undirected graph]] contains an even number of [[Vertex (graph theory)|vertices]] of odd [[Degree (graph theory)|degree]]. That is, the number of vertices that have an odd number of incident [[Graph (discrete mathematics)|edges]] must be even. In more colloquial terms, in a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands; for this reason, the result is known as the [[handshaking lemma]]. 

To prove this by double counting, let <math>d(v)</math> be the degree of vertex <math>v</math>. The number of vertex-edge incidences in the graph may be counted in two different ways: by summing the degrees of the vertices, or by counting two incidences for every edge. Therefore
<math display=block>\sum_v d(v) = 2e</math>
where <math>e</math> is the number of edges. The sum of the degrees of the vertices is therefore an [[even number]], which could not happen if an odd number of the vertices had odd degree. This fact, with this proof, appears in the 1736 paper of [[Leonhard Euler]] on the [[Seven Bridges of Königsberg]] that first began the study of [[graph theory]].

===Counting trees===
[[File:Cayley's formula 2-4.svg|thumb|240px|[[Cayley's formula]] implies that there is {{nowrap|1 {{=}} 2<sup>2 − 2</sup>}} tree on two vertices, {{nowrap|3 {{=}} 3<sup>3 − 2</sup>}} trees on three vertices, and {{nowrap|16 {{=}} 4<sup>4 − 2</sup>}} trees on four vertices.]]
[[File:Graph.tree. Cayley's formula.png|thumb|Adding a directed edge to a rooted forest]]
What is the number <math>T_n</math> of different [[tree (graph theory)|trees]] that can be formed from a set of <math>n</math> distinct vertices? [[Cayley's formula]] gives the answer <math>T_n=n^{n-2}</math>. {{harvtxt|Aigner|Ziegler|1998}} list four proofs of this fact; they write of the fourth, a double counting proof due to Jim Pitman, that it is "the most beautiful of them all."{{sfn|Aigner|Ziegler|1998}}

Pitman's proof counts in two different ways the number of different sequences of directed edges that can be added to an [[empty graph]] on <math>n</math> vertices to form from it a [[rooted tree]]. The directed edges point away from the root. One way to form such a sequence is to start with one of the <math>T_n</math> possible unrooted trees, choose one of its <math>n</math> vertices as root, and choose one of the <math>(n-1)!</math> possible sequences in which to add its <math>n-1</math> (directed) edges. Therefore, the total number of sequences that can be formed in this way is <math>T_n n(n-1)! = T_n n!</math>.{{sfn|Aigner|Ziegler|1998}}

Another way to count these edge sequences is to consider adding the edges one by one to an empty graph, and to count the number of choices available at each step. If one has added a collection of <math>n-k</math> edges already, so that the graph formed by these edges is a rooted [[Tree_(graph_theory)#Forest|forest]] with <math>k</math> trees, there are <math>n(k-1)</math> choices for the next edge to add: its starting vertex can be any one of the <math>n</math> vertices of the graph, and its ending vertex can be any one of the <math>k-1</math> roots other than the root of the tree containing the starting vertex. Therefore, if one multiplies together the number of choices from the first step, the second step, etc., the total number of choices is
<math display=block>\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.</math>
Equating these two formulas for the number of edge sequences results in Cayley's formula:
<math display=block>\displaystyle T_n n!=n^{n-2}n!</math>
and
<math display=block>\displaystyle T_n=n^{n-2}.</math>
As Aigner and Ziegler describe, the formula and the proof can be generalized to count the number of rooted forests with <math>k</math> trees, for any {{nowrap|<math>k</math>.{{sfn|Aigner|Ziegler|1998}}}}