Original Research Article

Article volume = 2024 and issue = 2

Pages: 193–212

Article publication Date: November 08, 2024

You can download PDF file of the article here: Download

Visited 72 times and downloaded 30 times

Counting vertices among all noncrossing trees by levels and degrees

Fidel Ochieng Oduol and Isaac Owino Okoth

(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, we enumerate vertices among all noncrossing trees based on their levels and degrees. Moreover, we obtain the number of eldest children, first children, non-first children, leaves and non-leaves which reside at a given level. We use generating functions, butterfly decomposition of noncrossing trees and bijections to arrive at our results.

Keywords:

Noncrossing tree, level, degree, eldest child, first child, non-first child, leaf, non-leaf.

References:
  • [1] S. A. Abayo, I. O. Okoth, D. M. Kasyoki, Reachability in complete t-ary trees, Annals of Mathematics and Computer Science 18 (2023), 67–89. 1
  • [2] W. Y. C. Chen, N. Y. Li, L. W. Shapiro, The butterfly decomposition of plane trees, Discret. Appl. Math., 155(17) (2007), 2187–2201. 1, 1
  • [3] N. Dershowitz, S. Zaks, Enumerations of ordered trees, Discrete Math., 31(1) (1980), 9–28. 1
  • [4] E. Deutsch, M. Noy, Statistics on non-crossing trees, Discrete Math., 254(1-3) (2002), 75 – 87. 2.4, 3.1
  • [5] 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. 1
  • [6] P. Flajolet, M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204(1-3) (1999), 203 –229. 1
  • [7] M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180(1-3) (1998), 301-313. 1
  • [8] A. O. Nyariaro, I. O. Okoth, Reachability Results in Plane Trees, Commun. Adv. Math. Sci., 4(2) (2021), 75–88. 1
  • [9] I. O. Okoth, Combinatorics of oriented trees and tree-like structures, PhD Thesis, Stellenbosch University, 2015. 1, 1, 2.1, 2.3, 2.4
  • [10] I. O. Okoth, A. O. Nyariaro, Reachability results in labelled t-ary trees, Open J. Math. Sc, 5(1) (2021), 360-370. 1
  • [11] A. Panholzer, H. Prodinger, Bijection for ternary trees and non-crossing trees, Discret. Math., 250(1-3) (2002), 115–125. 1
  • [12] 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. 4
  • [13] S. Seo, H. Shin, A refined enumeration of p-ary labelled trees, Korean J. Math., 21(4) (2013), 495-502. 1
  • [14] S. Seunghyun, H. Shin, A refinement for ordered labeled trees, Korean J. Math., 20(2) (2012), 225-261. 1
  • [15] R. P. Stanley, Enumerative Combinatorics, Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999. 1, 1.1
  • [16] S. H. F. Yan, X. Liu, 2-noncrossing trees and 5-ary trees, Discrete Math., 309 no. 20 (2009) 6135–6138. 4
Cite this article as:
  • Fidel Ochieng Oduol and Isaac Owino Okoth, Counting vertices among all noncrossing trees by levels and degrees, Communications in Combinatorics, Cryptography & Computer Science, 2024(2), PP.193–212, 2024
  • Export citation to BibTeX