A combinatorial proof of Postnikov's identity and a generalized enumeration of labeled trees

Preprint English OPEN
Seo, Seunghyun;
  • Subject: Mathematics - Combinatorics | 05C05, 05C30 (Secondary) | 05A15 (Primary)

In this paper, we give a simple combinatorial explanation of a formula of A. Postnikov relating bicolored rooted trees to bicolored binary trees. We also present generalized formulas for the number of labeled k-ary trees, rooted labeled trees, and labeled plane trees.
  • References (5)

    [1] A. Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376-378.

    [2] J. Pitman and R. P. Stanley, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom. 27 (2002), no. 4, 603-634.

    [3] A. Postnikov, Permutohedra, associahedra, and beyond, Retrospective in Combinatorics: Honoring Richard Stanley's 60th Birthday, Massachusetts Institute of Technology, Cambridge, Massachusetts, 2004, slide available at: http://www-math.mit.edu/~apost/talks/perm-slides.pdf

    [4] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.

    [5] D. Stanton and D. White, Constructive Combinatorics, Springer-Verlag, New York, 1986.

  • Related Organizations (3)
  • Metrics
Share - Bookmark