A refinement of Cayley's formula for trees (Q813443): Difference between revisions
From MaRDI portal
Set profile property. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: math/0507497 / rank | |||
Normal rank |
Latest revision as of 18:00, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A refinement of Cayley's formula for trees |
scientific article |
Statements
A refinement of Cayley's formula for trees (English)
0 references
9 February 2006
0 references
Summary: A proper vertex of a rooted tree with totally ordered vertices is a vertex that is the smallest of all its descendants. We count several kinds of labeled rooted trees and forests by the number of proper vertices. Our results are all expressed in terms of the polynomials \[ P_n(a,b,c)= c\prod_{i=1}^{n-1}(ia+(n-i)b +c), \] which reduce to \((n+1)^{n-1}\) for \(a=b=c=1\). Our study of proper vertices was motivated by Postnikov's hook length formula \[ (n+1)^{n-1}=\frac {n!}{2^n} \sum _T \prod_v\left(1+\frac 1{h(v)}\right), \] where the sum is over all unlabeled binary trees \(T\) on \(n\) vertices, the product is over all vertices \(v\) of \(T\), and \(h(v)\) is the number of descendants of \(v\) (including \(v\)). Our results give analogues of Postnikov's formula for other types of trees, and we also find an interpretation of the polynomials \(P_n(a,b,c)\) in terms of parking functions.
0 references
descendants
0 references
labeled rooted trees and forests
0 references