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

Main Article Content

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.

Article Details


[1] 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

[2] 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

[3] 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

[4] 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

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

[6] 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