Korean J. Math.  Vol 21, No 4 (2013)  pp.495-502
DOI: https://doi.org/10.11568/kjm.2013.21.4.495

A refined enumeration of $p$-ary labeled trees

Seunghyun Seo, Heesung Shin


Let $\mathcal{T}^{(p)}_n$ be the set of $p$-ary labeled trees on $\{1,2,\dots,n\}$. A maximal decreasing subtree of an $p$-ary labeled tree is defined by the maximal $p$-ary subtree from the root with all edges being decreasing. In this paper, we study a new refinement $\mathcal{T}^{(p)}_{n,k}$ of $\mathcal{T}^{(p)}_n$, which is the set of $p$-ary labeled trees whose maximal decreasing subtree has $k$ vertices.

Subject classification

05A15, 05C05, 05C30


Full Text:



Franc ̧ois Bergeron, Philippe Flajolet, and Bruno Salvy, Varieties of increasing trees, In CAAP ’92 (Rennes, 1992), volume 581 of Lecture Notes in Comput. Sci., pages 24–48. Springer, Berlin, 1992. (Google Scholar)

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathemat- ics, Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1989. A foundation for computer science. (Google Scholar)

Seunghyun Seo and Heesung Shin, A generalized enumeration of labeled trees and reverse Pru ̈fer algorithm, J. Combin. Theory Ser. A. 114 (7) (2007), 1357–1361. (Google Scholar)

Seunghyun Seo and Heesung Shin, On the enumeration of rooted trees with fixed size of maximal decreasing trees, Discrete Math. 312 (2) (2012), 419–426. (Google Scholar)

Seunghyun Seo and Heesung Shin, A refinement for ordered labeled trees, Korean J. Math. 20 (2) (2012), 255–261. (Google Scholar)

Richard P. Stanley, Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cam- bridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. (Google Scholar)


  • There are currently no refbacks.

ISSN: 1976-8605 (Print), 2288-1433 (Online)

Copyright(c) 2013 By The Kangwon-Kyungki Mathematical Society, Department of Mathematics, Kangwon National University Chuncheon 21341, Korea Fax: +82-33-259-5662 E-mail: kkms@kangwon.ac.kr