\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Ira M. Gessel and Seunghyun Seo}
%
%
\medskip
\noindent
%
%
{\bf A Refinement of Cayley's Formula for Trees}
%
%
\vskip 5mm
\noindent
%
%
%
%
A {\it 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.
\bye