A new proof of Cayley's formula for counting labeled trees

DOI10.1016/0097-3165(95)90022-5MaRDI QIDQ1894017zbMATH OpenOpenAlexFDO

Authors Peter W. Shor

Publication date 21 August 1995

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(95)90022-5

zbMATH Keywords

Cayley's formulaenumerationlabeled trees

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Trees (05C05) Enumeration in graph theory (05C30)

Review text

The author gives another proof of Cayley's formula \(n^{n- 2}\) for the number of rooted trees with \(n\) labelled nodes. The argument is by induction and involves classifying the trees according to the number of edges \(uv\) contained such that if \(u\) is the node closer to the root then the label of \(u\) exceeds the label of some node in the subtree rooted at \(v\).

Recommendations

• A short proof of Cayley's tree formula
• scientific article; zbMATH DE number 3906515
• A new simple proof of Cayley's formula and its relationship with the Kirkwood-Salzburg equations
• On Cayley's formula for counting forests
• Counting forests

Cites work

• scientific article; zbMATH DE number 3351606 (Why is no real title available?)
• On Cayley's Formula for Counting Trees
• The inversion enumerator for labeled trees

Cited in

(37)

• Coalescent random forests
• Forest volume decompositions and Abel-Cayley-Hurwitz multinomial expansions
• \(q\)-log-convexity from linear transformations and polynomials with only real zeros
• A bijective proof of the Shor recurrence
• A context-free grammar for the Ramanujan-Shor polynomials
• Kruskal with embedded c-semirings to solve MST problems with partially-ordered costs
• A remark on the enumeration of rooted labeled trees
• A new sufficient condition for a tree \(T\) to have the \((2,1)\)-total number \(\Delta +1\)
• A generalization of the Ramanujan polynomials and plane trees
• A formula for the number of labelled trees
• Total positivity of some polynomial matrices that enumerate labeled trees and forests. I: Forests of rooted labeled trees
• A new proof of Cayley's formula for labeled spanning trees
• Cayley theorem on trees enumeration
• C-semiring Frameworks for Minimum Spanning Tree Problems
• scientific article; zbMATH DE number 3906515 (Why is no real title available?)
• scientific article; zbMATH DE number 4070934 (Why is no real title available?)
• scientific article; zbMATH DE number 1504579 (Why is no real title available?)
• A short proof of Cayley's tree formula
• A REFINEMENT FOR ORDERED LABELED TREES
• Bijections behind the Ramanujan polynomials
• A counting formula for labeled, rooted forests
• The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses
• A new simple proof of Cayley's formula and its relationship with the Kirkwood-Salzburg equations
• A Telescopic Proof of Cayley’s Formula
• Recognition and enumeration of the quasi-full rooted trees
• Some equidistributed statistics and applications to hook length formulas
• Stable multivariate Narayana polynomials and labeled plane trees
• Maximizing phylogenetic diversity under ecological constraints: a parameterized complexity study
• A grammatical calculus for the Ramanujan polynomials
• Cayley trees and increasing 1, 2-trees: let's twist!
• Orbifold Euler characteristics of \({\overline{{{\mathcal{M}}}}}_{g,n} \)
• Derivatives of the tree function
• Counting forests
• Runs in labelled trees and mappings
• Trees, forests, and total positivity. I: \(q\)-trees and \(q\)-forests matrices
• Arboretum for a generalisation of Ramanujan polynomials
• On Cayley's formula for counting forests

This page was built for publication: A new proof of Cayley's formula for counting labeled trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894017)