For faster navigation, this Iframe is preloading the Wikiwand page for Cayley's formula.

Cayley's formula

The complete list of all trees on 2,3,4 labeled vertices: tree with 2 vertices, trees with 3 vertices and trees with 4 vertices.

In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer , the number of trees on 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.[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 Tn,k = k nnk − 1.[5]

References

  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.
{{bottomLinkPreText}} {{bottomLinkText}}
Cayley's formula
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?