Cayley's formula

In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer $n$ , the number of trees on $n$ labeled vertices is $n^{n-2}$ .

The complete list of all trees on 2,3,4 labeled vertices:

2^{2-2}=1

tree with 2 vertices,

3^{3-2}=3

trees with 3 vertices and

4^{4-2}=16

trees with 4 vertices.

The formula equivalently counts the number of spanning trees of a complete graph with labeled vertices (sequence A000272 in the OEIS).

Proof

Many proofs of Cayley's tree formula are known.[1] One classical proof of the formula uses Kirchhoff's matrix tree theorem, a formula for the number of spanning trees in an arbitrary graph involving the determinant of a matrix. Prüfer sequences yield a bijective proof of Cayley's formula. Another bijective proof, by André Joyal, finds a one-to-one transformation between n-node trees with two distinguished nodes and maximal directed pseudoforests. A proof by double counting due to Jim Pitman counts in two different ways the number of different sequences of directed edges that can be added to an empty graph on n vertices to form from it a rooted tree; see Double counting (proof technique)#Counting trees.

History

The formula was first discovered by Carl Wilhelm Borchardt in 1860, and proved via a determinant.[2] In a short 1889 note, Cayley extended the formula in several directions, by taking into account the degrees of the vertices.[3] Although he referred to Borchardt's original paper, the name "Cayley's formula" became standard in the field.

Other properties

Cayley's formula immediately gives the number of labelled rooted forests on n vertices, namely $(n + 1) n - 1$ . Each labelled rooted forest can be turned into a labelled tree with one extra vertex, by adding a vertex with label $n + 1$ and connecting it to all roots of the trees in the forest.

There is a close connection with rooted forests and parking functions, since the number of parking functions on n cars is also $(n + 1) n - 1$ . A bijection between rooted forests and parking functions was given by M. P. Schützenberger in 1968.[4]

Generalizations

The following generalizes Cayley's formula to labelled forests: Let T_n,k be the number of labelled forests on n vertices with k connected components, such that vertices 1, 2, ..., k all belong to different connected components. Then $T n, k = k n n - k - 1$ .[5]

References

Aigner, Martin; Ziegler, Günter M. (1998). Proofs from THE BOOK. Springer-Verlag. pp. 141–146.
Borchardt, C. W. (1860). "Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung". Math. Abh. der Akademie der Wissenschaften zu Berlin: 1–20.
Cayley, A. (1889). "A theorem on trees". Quart. J. Pure Appl. Math. 23: 376–378.
Schützenberger, M. P. (1968). "On an enumeration problem". Journal of Combinatorial Theory. 4: 219–221. MR 0218257.
Takács, Lajos (March 1990). "On Cayley's formula for counting forests". Journal of Combinatorial Theory, Series A. 53 (2): 321–323. doi:10.1016/0097-3165(90)90064-4.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Aigner, Martin; Ziegler, Günter M. (1998). Proofs from THE BOOK. Springer-Verlag. pp. 141–146.

[2] Borchardt, C. W. (1860). "Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung". Math. Abh. der Akademie der Wissenschaften zu Berlin: 1–20.

[3] Cayley, A. (1889). "A theorem on trees". Quart. J. Pure Appl. Math. 23: 376–378.

[4] Schützenberger, M. P. (1968). "On an enumeration problem". Journal of Combinatorial Theory. 4: 219–221. MR 0218257.

[5] Takács, Lajos (March 1990). "On Cayley's formula for counting forests". Journal of Combinatorial Theory, Series A. 53 (2): 321–323. doi:10.1016/0097-3165(90)90064-4.