Generalization of a variant of  k -plane trees

Enumeration of plane trees and noncrossing trees was recently unified by considering d-dimensional plane trees in which ordinary plane trees are 1-dimensional plane trees and noncrossing trees are 2-dimensional plane trees. Also, recently variants of k-plane trees and k-noncrossing trees were introduced and enumerated according to number of nodes, root degree, label of the eldest or youngest child of the root, length of the leftmost path and number of forests with a given number of components. In this paper, we have generalized a variant of k-plane trees and k-noncrossing trees to a d-dimensional version and obtained closed formulas for the trees based on the aforementioned parameters. We have used symbolic method to find the generating functions, obtained the right substitution to solve the generating functions and applied Lagrange-Bürmann inversion to obtain the formulas. The results of this paper unify known results in the counting of k-plane trees and k-noncrossing trees.

Keywords

k₁-plane tree; d-dimensional k₁-plane tree; root degree; eldest child; youngest child; leftmost path; forest

References

1. de Bruijn NG, Morselt BJM. A note on plane trees. Journal of Combinatorial Theory. 1967; 2(1): 27–34. doi: 10.1016/S0021-9800(67)80111-X

2. Noy M. Enumeration of noncrossing trees on a circle. Discrete Mathematics. 1998; 180(1–3): 301–313. doi: 10.1016/S0012-365X(97)00121-0

3. Dershowitz N, Zaks S. Enumerations of ordered trees. Discrete Mathematics. 1980; 31(1): 9–28. doi: 10.1016/0012-365X(80)90168-5

4. Eu SP, Seo S, Shin H. Enumerations of vertices among all rooted ordered trees with levels and degrees. Discrete Mathematics. 2017; 340(9): 2123–2129. doi: 10.1016/j.disc.2017.04.007

5. Du RRX, He J, Yun X. Counting Vertices with Given Outdegree in Plane Trees and k-ary Trees. Graphs and Combinatorics. 2019; 35: 221–229. doi: 10.1007/s00373-018-1975-8

6. Stanley RP. Enumerative Combinatorics, 2nd ed. Cambridge University Press; 1999.

7. Sloane NJA. The On-Line Encyclopaedia of Integer Sequences. Available online: https://oeis.org (accessed on 1 May 2025).

8. Gu NSS, Prodinger H. Bijections for 2-plane trees and ternary trees. European Journal of Combinatorics. 2009; 30(4): 969–985. doi: 10.1016/j.ejc.2008.06.006

9. Gu NSS, Prodinger H, Wagner S. Bijections for a class of labelled plane trees. European Journal of Combinatorics. 2010; 31(3): 720–732. doi: 10.1016/j.ejc.2009.10.007

10. Oduol FO, Okoth IO, Nyamwala FO. Enumeration of a variant of k-plane trees. Journal of Algebra Combinatorics Discrete Structures and Applications. 2024. Preprint.

11. Panholzer A, Prodinger H. Bijection for ternary trees and non-crossing trees. Discrete Mathematics. 2002; 250(1–3): 181–195. doi: 10.1016/S0012-365X(01)00282-5

12. Flajolet P, Noy M. Analytic combinatorics of non-crossing configurations. Discrete Mathematics. 1999; 204(1–3): 203–229. doi: 10.1016/S0012-365X(98)00372-0

13. Hough DS. Descents in noncrossing trees. Electronic Journal of Combinatorics. 2003; 10: 1–5. doi: 10.37236/1753

14. Deutsch E, Noy M. Statistics on non-crossing trees. Discrete Mathematics. 2002; 254(1–3): 75–87. doi: 10.1016/S0012-365X(01)00366-1

15. Yan SHF, Liu X. 2-noncrossing trees and 5-ary trees. Discrete Mathematics. 2009; 309(20): 6135–6138. doi: 10.1016/j.disc.2009.03.044

16. Pang SXM, Lv L. K-noncrossing trees and k-proper trees. In: Proceedings of the 2010 2nd International Conference on Information Engineering and Computer Science; 25-26 December 2010; Wuhan, China. pp. 1–3.

17. Oduol FO, Okoth IO, Nyamwala FO. Enumeration of a variant of k-noncrossing trees. Indian Journal of Discrete Mathematics. 2024. Preprint.

18. Okoth IO, Kasyoki DM. Generalized plane trees. Bulletin of the Institute of Combinatorics and its Applications. 2024. Preprint.

19. Nyariaro AO, Okoth IO, Nyamwala FO. Generalized k-plane trees. Journal of Discrete Mathematics and its Applications. 2024. Preprint.

20. Wilf HS. Generatingfunctionology, 3rd ed. A K Peters/CRC Press; 2006.

Refbacks

There are currently no refbacks.

Editor-in-Chief

Prof. Youssri Hassan Youssri

Cairo University, Egypt

Indexing & Archiving

News & Announcements

2025-05-08

Prof. Rami Ahmad El-Nabulsi is highly deserving of a Lifetime Achievement Award

Prof. Rami Ahmad El-Nabulsi, Researcher at Czech Academy of Science, Czech Republic, received the Lifetime Achievement Award!

2025-03-01

Publication Frequency of MSS changes to be quarterly!

We are pleased to announce that, effective from 2025, the publication frequency of this journal will be adjusted to a quarterly schedule, with four issues released annually in March, June, September, and December....

2024-09-20

Highly Read Article Recommendation

Since the journal launched in 2023, we have been proud to publish a plethora of insightful findings in the realms of mathematics and systems science....

2024-07-10

Meeting our Editor-in-Chief and Associate Editor

It is with great pride that we introduce Prof. Youssri Hassan Youssri and Prof. Ali Akgül, who are the Editor-in-Chief and Associate Editor of our esteemed journal.

More Announcements...

Member Application

Apply to be Reviewer

Apply to be EBM

Journal Center

Asia Pacific Academy of Science Pte. Ltd. (APACSCI) specializes in international journal publishing. APACSCI adopts the open access publishing model and provides an important communication bridge for academic groups whose interest fields include engineering, technology, medicine, computer, mathematics, agriculture and forestry, and environment.

more