Файл:Cayley's formula 2-4.svgThe complete list of all trees on 2,3,4 labeled vertices: <math>2^{2-2}=1</math> tree with 2 vertices, <math>3^{3-2}=3</math> trees with 3 vertices and <math>4^{4-2}=16</math> trees with 4 vertices.
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 Шаблон:Section link.
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 Шаблон:Math.
Each labelled rooted forest can be turned into a labelled tree with one extra vertex, by adding a vertex with label Шаблон:Math 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 Шаблон:Math. 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 Tn,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 Шаблон:Math.[5]
