Hook Length Polynomials for Plane Forests of
a Certain Type

Fu Liu

Department of Mathematics, University of California, Davis,
One Shields Avenue, Davis, CA 95616, USA

fuliu@math.ucdavis.edu

Annals of Combinatorics 13 (3) pp.315-322 September, 2009

Abstract:

The original motivation for the study of hook length polynomials was to find a
combinatorial proof for a hook length formula for binary trees given by Postnikov, as well
as a proof for a hook length polynomial formula conjectured by Lascoux. In this paper, we
define the hook length polynomial for plane forests of a given degree sequence type and
show that it can be factored into a product of linear forms. Some other enumerative results
on forests are also given.
References:

1. Chen, W.Y.C.: A general bijective algorithm for trees. Proc. Natl. Acad. Sci. 87, 9635- 9639 (1990)

2. Chen, W.Y.C., Yang, L.L.M.: On the hook length formula for binary trees. European J. Combin. 29, 1563-1565 (2008)

3. Du, R.R.X., Liu, F.: (k; m)-Catalan numbers and hook length polynomails for plane trees. European J. Combin. 28, 1312-1321 (2007)

4. Erd´elyi, A., Etherington, I.M.H.: Some problems of non-associative combinations (2). Edinburgh Math. Notes 32, 7-12 (1940)

5. Gessel, I.M., Seo, S.: A renement of Cayley's formula for trees. Electron. J. Combin. 11, #R27 (2006)

6. Harary, H., Prins, G., Tutte, W.: The number of plane trees. Indag. Math. 26, 319-329 (1964)

7. Postnikov, A.: Permutohedra, associahedra, and beyond, Retrospective in Combinatorics: Honoring Richard Stanleys 60th Birthday, Massachusetts Institute of Technology, Cambridge (2004)

8. Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN 2009, 1026-1106 (2009)

9. Seo, S.: A combinatorial proof of Postnikov's identity and a generalized enumeration of labeled trees. Electron. J. Combin. 11, #N3 (2005)

10. R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.