Counting vertices among all higher-dimensional plane trees

Oduol, Fidel Ochieng; Okoth, Isaac Owino; Kaneba, Christopher Munyiwa

doi:10.22061/jdma.2025.12275.1146

Counting vertices among all higher-dimensional plane trees

Document Type : Full Length Article

Authors

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

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

10.22061/jdma.2025.12275.1146

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.

Keywords