Original Research Article

Article volume = 2025 and issue = 1

Pages: 1–18

Article publication Date: December 12, 2025

You can download PDF file of the article here: Download

Visited 15 times and downloaded 8 times

Enumeration of a variant of k-noncrossing trees

Fidel Ochieng Oduol(a), Isaac Owino Okoth(b,∗), Fredrick Oluoch Nyamwala(a)

(a) Department of Mathematics, Physics and Computing, Moi University, Eldoret, Kenya.

(b) Department of Pure and Applied Mathematics, Maseno University, Maseno, Kenya.

Abstract:

In this paper, a variant of k-noncrossing trees where all children (labelled 1) of all internal nodes in the (l, r)-representation of the noncrossing trees must be on the left of all others is introduced and enumerated by number of nodes, root degree, labels of the eldest child or youngest child of the root, length of the leftmost path and forests. Generating functions, symbolic method, right substitutions and Lagrange-Bürmann inversion are applied to obtain the results. Known results for noncrossing trees and nondecreasing 2-noncrossing trees follow as corollaries.

Keywords:

k1-noncrossing tree, root degree, eldest child, youngest child, forest.

References:
  • [1] E. Deutsch, M. Noy, Statistics on non-crossing trees, Discrete Math., 254 (2002), 75 – 87. 1
  • [2] P. Flajolet, M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204 (1999), 203–229. 1, 1, 6
  • [3] D. S. Hough, Descents in noncrossing trees, Electron. J. Combin. 10 (2003). 1
  • [4] Y. W. Kariuki, I. O. Okoth, Bijections of Plane Husimi graphs and certain combinatorial structures, Eur. J. Math. Appl. 3 (2023), 21. 1
  • [5] Y. W. Kariuki, I. O. Okoth, F. O. Nyamwala, Counting formulas and bijections of nondecreasing 2-noncrossing trees, Electron. J. Math. 7 (2024), 69–-87. 1, 1, 1, 2, 3, 6
  • [6] M. Noy, Enumeration of noncrossing trees on a circle, In Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995), 180 (1998), 301–313. 1
  • [7] A. P. O. Nyariaro, I. O. Okoth, Bijections for classes of labelled trees, Trans. Combin. 13 (2024), 197–211. 1
  • [8] F. O. Oduol, I.O. Okoth, Counting vertices among all noncrossing trees by levels and degrees, Commun. Combin. Cryptogr. Comput. Sci., 2(2024), 193-212. 1
  • [9] I. O. Okoth, Combinatorics of oriented trees and tree-like structures, PhD Thesis, Stellenbosch University (2015). 1, 1
  • [10] I. O. Okoth, Enumeration of k-noncrossing trees and forests, Commun. Comb. Optim. 7 (2022), 301–311. 1, 1
  • [11] I. O. Okoth, On Noncrossing and Plane Tree-Like Structures, Commun. Adv. Math. Sc. 4 (2021), 89–99. 1
  • [12] I. O. Okoth, On 2-noncrossing increasing trees, Open J. Discret. Appl. Math. 6(9) (2021), 39–50. 1
  • [13] I. O. Okoth, Refined enumeration of 2-noncrossing trees, Notes Number Theory Discret. Math., 27 (2021), 201–210. 1
  • [14] I. O. Okoth, D. M. Kasyoki, Generalized plane trees, Preprint, (2024). 1
  • [15] I. O. Okoth, S. Wagner, Locally oriented noncrossing trees, Electron. J. Combin., (2015), 15 pp. 1
  • [16] I. O. Okoth, S. Wagner, Refined enumeration of k-plane trees and k-noncrossing trees, Ann. Combin., (2024), 1–33. 1, 1, 7
  • [17] S. X. M. Pang, L. Lv, K-noncrossing trees and k-proper trees, 2nd International Conference on Information Engineering and Computer Science, Wuhan, (2010), 1–3. 1
  • [18] A. Panholzer, H. Prodinger, Bijection for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 115– 125. 1
  • [19] N.J.A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2019. Available at https://oeis.org. 1, 2
  • [20] H. S. Wilf, Generatingfunctionology, A. K. Peters, Ltd., Natick, MA, USA, 2006. 1.2
  • [21] S. H. F. Yan, X. Liu, 2-noncrossing trees and 5-ary trees, Discrete Math. 309 (2009), 6135–6138. 1
  • [22] S-L. Yang, M-y. Jiang, The m-Schröder paths and m-Schröder numbers, Discrete Math. 344 (2021), 112209. 1
Cite this article as:
  • Fidel Ochieng Oduol, Isaac Owino Okoth, Fredrick Oluoch Nyamwala, Enumeration of a variant of k-noncrossing trees, Communications in Combinatorics, Cryptography & Computer Science, 2025(1), PP.1–18, 2025
  • Export citation to BibTeX