Editing Double counting (proof technique) (section)

===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}}}}