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 .

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.

### Generalizations

The following generalizes Cayley's formula to labelled forests:
Let *T*_{n,k} be the number of labelled forests on *n* vertices,
such that vertices 1, 2, ..., *k* all belong to different trees.
Then *T*_{n,k} = *k* *n*^{n − k − 1}.^{[4]}

## 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.**^**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.