mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, Cayley's formula is a result in

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

named after Arthur Cayley. It states that for every

positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

n

, the number of trees on

n

labeled vertices is

n^

. The formula equivalently counts the spanning trees of a complete graph with labeled vertices .

Proof

Many proofs of Cayley's tree formula are known. 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 In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...

of a

matrix Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...

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

History

The formula was first discovered by Carl Wilhelm Borchardt in 1860, and proved via a

. In a short 1889 note, Cayley extended the formula in several directions, by taking into account the degrees of the vertices. 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 . Each labelled rooted forest can be turned into a labelled tree with one extra vertex, by adding a vertex with label 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 . A

bijection In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...

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 with ''k'' connected components, such that vertices 1, 2, ..., ''k'' all belong to different connected components. Then .

References

{{reflist Trees (graph theory)