A Refinement of Cayley's Formula for Trees

Abstract

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}={n!\over 2^n}\sum _T \prod_{v}\left(1+{1\over 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.