Counting vertices among all higher-dimensional plane trees

Document Type : Full Length Article

Authors

1 Department of Mathematics, Physics and Computing, Moi University, Eldoret, Kenya.

2 Department of Pure and Applied Mathematics, School of Mathematics, Statistics and Actuarial Science, Maseno University, Maseno, Kenya

Abstract

In this paper, we study the enumeration of vertices in d-dimensional plane trees with respect to their levels and degrees. This class of trees generalizes both ordinary plane trees and noncrossing trees. Our approach builds upon a decomposition framework that extends the butterfly decomposition of plane trees introduced by Chen, Li and Shapiro, as well as that of noncrossing trees studied by Oduol and Okoth. We derive both explicit and asymptotic formulas for the enumeration of vertices, eldest children, first children, non-first children and non-leaves at specified levels and degrees. The results are obtained through a combination of generating function techniques, refined butterfly decompositions and bijective methods. This work extends previous enumeration results on ordinary plane trees and noncrossing trees and provides new insights into the combinatorial structure of their higher-dimensional analogues.

Graphical Abstract

Counting vertices among all higher-dimensional plane trees

Keywords

Main Subjects


[1] S. A. Abayo, I. O. Okoth, D. M. Kasyoki, Reachability in complete t-ary trees, Ann. Math. Comput.
Sci. 18 (2023) 67–89. https://doi.org/10.56947/amcs.v18.191
[2] W. Y. C. Chen, N. Y. Li, L. W. Shapiro, The butterfly decomposition of plane trees, Discrete Appl.
Math. 155(17) (2007) 2187–2201. https://doi.org/10.1016/j.dam.2007.04.020
[3] N. Dershowitz, S.Zaks, Enumerations of ordered trees, Discrete Math. 31(1) (1980) 9–28.
https://doi.org/10.1016/0012-365X(80)90168-5
[4] S-P. Eu, S. Seo, H. Shin, Enumerations of vertices among all rooted ordered trees with levels and
degrees, Discrete Math. 340(9) (2017) 2123–2129. https://doi.org/10.48550/arXiv.1605.00715
[5] N. S. S. Gu, H. Prodinger, S. Wagner, Bijections for a class of labeled plane trees, Europ. J. Combin.
31(3) (2010) 720–732. https://doi.org/10.1016/j.ejc.2009.10.007
[6] P. Flajolet, M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math. 204(1-3)
(1999) 203–229. https://doi.org/https://doi.org/10.1016/S0012-365X(98)00372-0
[7] M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180(1-3) (1998) 301–313.
https://doi.org/10.1016/S0012-365X(97)00121-0
[8] A. O. Nyariaro, I. O. Okoth, Reachability results in plane trees, Commun. Adv. Math. Sci. 4(2)
(2021) 75–88. https://doi.org/10.33434/cams.936558
[9] A. O. Nyariaro, I. O. Okoth, F. O. Nyamwala, Generalized k-plane trees, J. Disc. Math. Appl. 10(2)
(2025) 161–182. https://doi.org/10.22061/jdma.2025.11859.1122
[10] F. O. Oduol, I. O. Okoth, Counting vertices among all noncrossing trees by levels and degrees, Commun. Cryptogr. & Computer Sci. 2024(2) (2024) 193–212.
https://doi.org/http://cccs.sgh.ac.ir/ Articles/2024/ issue2/2-7
[11] I. O. Okoth, Combinatorics of Oriented Trees and Tree-Like Structures, PhD Thesis, Stellenbosch University, 2015. https://scholar.sun.ac.za/server/api/core/bitstreams/345540f5-7912-
44dc-bd6a-d3b7f89c0df5/content
[12] I. O. Okoth, D. M. Kasyoki, Generalized plane trees, (2024) Preprint.
[13] I. O. Okoth, A. O. Nyariaro, Reachability results in labelled t-ary trees, Open J. Math. Sc. 5(1)(2021)
360–370. https://doi.org/10.30538/oms2021.0171
[14] S. X. M. Pang, L. Lv, K-noncrossing trees and K-proper trees, 2010 2nd International Conference on Information Engineering and Computer Science, Wuhan, (2010) 1–3.
https://doi.org/10.1109/ICIECS.2010.5677757
[15] A. Panholzer, H. Prodinger, Bijection for ternary trees and non-crossing trees, Discret. Math. 250(1-
3) (2002) 115–125. https://doi.org/10.1016/S0012-365X(01)00282-5
[16] S. Seo, H. Shin, A refined enumeration of p-ary labeled trees, Korean J. Math. 21(4) (2013) 495–502.
https://doi.org/10.11568/kjm.2013.21.4.495
[17] S. Seunghyun, H. Shin, A refinement for ordered labeled trees, Korean J. Math. 20(2) (2012) 225–
261. https://doi.org/10.11568/kjm.2012.20.2.255
[18] R. P. Stanley, Enumerative Combinatorics, Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999. https:// doi.org/10.1017/
CBO9780511609589
Volume 11, Issue 1
March 2026
Pages 59-80
  • Receive Date: 19 July 2025
  • Revise Date: 15 September 2025
  • Accept Date: 11 November 2025
  • First Publish Date: 28 February 2026
  • Publish Date: 01 March 2026