A new proof of Cayley's formula for counting labeled trees
type: Item
instance of: scholarly article
title: A new proof of Cayley's formula for counting labeled trees
zbMATH Open document ID: 0826.05036
DOI: 10.1016/0097-3165(95)90022-5
author: Peter W. Shor
published in: Journal of Combinatorial Theory. Series A
publication date: 1995-08-21T00:00:00Z
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\).
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05A19
zbMATH DE Number: 774651
zbMATH Keywords: labeled trees
zbMATH Keywords: enumeration
zbMATH Keywords: Cayley's formula
reviewed by: J. W. Moon
MaRDI profile type: Publication
full work available at URL: 0097-3165(95)90022-5
OpenAlex ID: W1987139164
cites work: On Cayley's Formula for Counting Trees
cites work: The inversion enumerator for labeled trees
cites work: Q5626688
description: scientific article; zbMATH DE number 774651