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