Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: A Refinement of Cayley’s Formula for Trees. | A Refinement of Cayley s Formula for Trees Ira M. Gessel Department of Mathematics Brandeis University Waltham MA 02454-9110 gessel@ Seunghyun Seo Department of Mathematics Seoul National University Seoul 151-742 Korea shyunseo@ Submitted Jun 30 2005 Accepted Jan 29 2006 Published Feb 8 2006 Mathematics Subject Classification 05A15 Dedicated to Richard Stanley on the occasion of his 60th birthday 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 n 1 Pn a b c c Ị Ị ia n - i b c i 1 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 7 . n V T T t 1 I n 1 inEn Ợ hv 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 Pn a b c in terms of parking functions. Partially supported by NSF Grant DMS-0200596 THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2 2006 R27 1 1. Introduction Cayley 2 showed that there are nn 2 unrooted trees on n vertices. Equivalently there are n 1 n 1 forests of rooted labeled trees on n vertices. In this paper we study the homogeneous polynomials n 1 Pn a b c cJJ ia n i b c . i 1 which reduce to n 1 n 1 for a b c 1. We rehne Cayley s formula by showing that Pn a b c counts rooted forests by the number of trees and the number of proper vertices which are vertices that are less than all of their descendants other than themselves. Moreover other evaluations of Pn a b c have similar interpretations for other types of trees and forests k-ary trees forests of ordered trees and forests of k-colored ordered trees .
