Editing Combinatorial proof (section)

==The difference between bijective and double counting proofs==
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.

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&nbsp;''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.

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>.

Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a [[Double counting (proof technique)#Counting trees|double counting proof due to Jim Pitman]]. 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.