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 Tnn! 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 nn − 2n! 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. Related concepts 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. 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. References . . . . Enumerative combinatorics Mathematical proofs