Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Cayley's formula
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Number of spanning trees of a complete graph}} {{distinguish|Cayley's theorem}} [[Image:Cayley's formula 2-4.svg|thumb|The 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.]] In [[mathematics]], '''Cayley's formula''' is a result in [[graph theory]] named after [[Arthur Cayley]]. It states that for every [[positive integer]] <math>n</math>, the number of [[Tree (graph theory)|trees]] on <math>n</math> labeled [[vertex (graph theory)|vertices]] is <math>n^{n-2}</math>. The formula equivalently counts the [[spanning tree]]s of a [[complete graph]] with labeled vertices {{OEIS|id=A000272}}. ==Proof== Many proofs of Cayley's tree formula are known.<ref>{{Cite book | last1 = Aigner | first1 = Martin | author1-link = Martin Aigner | last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler | pages = 141–146 | publisher = [[Springer-Verlag]] | title = Proofs from THE BOOK | year = 1998| title-link = Proofs from THE BOOK }}</ref> 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 (mathematics)|matrix]]. [[Prüfer sequence]]s 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 [[pseudoforest]]s. A proof by [[double counting (proof technique)|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 [[Null graph|empty graph]] on n vertices to form from it a rooted tree; see {{section link|Double counting (proof technique)|Counting trees}}. == History == The formula was first discovered by [[Carl Wilhelm Borchardt]] in 1860, and proved via a [[determinant]].<ref>{{cite journal |last=Borchardt | first = C. W. | authorlink = Carl Wilhelm Borchardt |year=1860 |title=Über eine Interpolationsformel für eine Art symmetrischer Functionen und über deren Anwendung |url=https://archive.org/details/abhandlungenderk1860deut/page/n245/mode/2up?view=theater |journal=Mathematische Abhandlungen der Königlichen Akademie der Wissenschaften zu Berlin |pages=1–20}}</ref> In a short 1889 note, Cayley extended the formula in several directions, by taking into account the degrees of the vertices.<ref>{{cite journal |first=A.|last=Cayley|authorlink=Arthur Cayley |url=https://books.google.com/books?id=M7c4AAAAIAAJ&pg=PA26 |title=A theorem on trees |journal=Quarterly Journal of Pure and Applied Mathematics |volume=23 |year=1889 |pages=376–378}}</ref> 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 [[Forest (graph theory)|forests]] on ''n'' vertices, namely {{math|(''n'' + 1)<sup>''n'' − 1</sup>}}. Each labelled rooted forest can be turned into a labelled tree with one extra vertex, by adding a vertex with label {{math|''n'' + 1}} and connecting it to all roots of the trees in the forest. There is a close connection with rooted forests and [[parking function|parking functions]], since the number of parking functions on ''n'' cars is also {{math|(''n'' + 1)<sup>''n'' − 1</sup>}}. A [[bijection]] between rooted forests and parking functions was given by [[Marcel-Paul Schützenberger|M. P. Schützenberger]] in 1968.<ref>{{cite journal|last=Schützenberger|first=M. P.|authorlink=Marcel-Paul Schützenberger|journal=Journal of Combinatorial Theory |mr=0218257|pages=219–221|title=On an enumeration problem|volume=4|year=1968|issue=3 |doi=10.1016/S0021-9800(68)80003-1 }}</ref> === Generalizations === The following generalizes Cayley's formula to labelled forests: Let ''T''<sub>''n'',''k''</sub> 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|''T''<sub>''n'',''k''</sub> {{=}} ''k'' ''n''<sup>''n'' − ''k'' − 1</sup>}}.<ref>{{cite journal|last1=Takács|first1=Lajos|title=On Cayley's formula for counting forests|journal=Journal of Combinatorial Theory, Series A|date=March 1990|volume=53|issue=2|pages=321–323|doi=10.1016/0097-3165(90)90064-4|doi-access=free}}</ref> ==References== {{reflist}} [[Category:Trees (graph theory)]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Distinguish
(
edit
)
Template:Math
(
edit
)
Template:OEIS
(
edit
)
Template:Reflist
(
edit
)
Template:Section link
(
edit
)
Template:Short description
(
edit
)