A refinement of Cayley's formula for trees

Details A refinement of Cayley's formula for trees A refinement of Cayley's formula for trees

2005-07-24

arxiv.org/abs/math/0507497v1

Mathematics

Combinatorics

20 pages

Scientific paper

A proper vertex of a rooted tree with totally ordered vertices is a vertex that is less than all its proper 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(a+(n-1)b+c)(2a+(n-2)b+c)...((n-1)a+b+c) which reduce to (n+1)^{n-1} for a=b=c=1. Our study of proper vertices was motivated by A. Postnikov's hook length formula for binary trees (arXiv:math.CO/0507163), which was also proved by W. Y. C. Chen and L. L. M. Yang (arXiv:math.CO/0507163) and generalized by R. R. X. Du and F. Liu (arXiv:math.CO/0501147). Our approach gives a new proof of Du and Liu's results and gives new hook length formulas. We also find an interpretation of the polynomials P_n(a,b,c) in terms of parking functions: we count parking functions according to the number of cars that park in their preferred parking spaces.

Affiliated with

Also associated with

No associations

Rating

A refinement of Cayley's formula for trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A refinement of Cayley's formula for trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A refinement of Cayley's formula for trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-444885