Original Research Article

Article volume = 2024 and issue = 2

Pages: 152–168

Article publication Date: August 18, 2024

You can download PDF file of the article here: Download

Visited 122 times and downloaded 53 times

Enumeration of k-plane trees and forests

Albert Oloo Nyariaro(a) and Isaac Owino Okoth(b)*

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

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

Abstract:

A k-plane tree is an ordered tree in which the vertices are labelled by integers {1, 2, . . . , k} and satisfies the condition i + j ⩽ k + 1 where i and j are adjacent vertices in the tree. These trees are known to be counted by Fuss-Catalan numbers. In this paper, we use generating functions and decomposition of trees to enumerate these trees according to degree of the root, label of the first child of the root and number of forests of k-plane trees. The results of this paper generalize known results for 2-plane trees and plane trees.

Keywords:

k-plane tree, degree, first child, forest.

References:
  • [1] N. Dershowitz, S. Zaks, Enumerations of ordered trees, Discret. Math., 31(1) (1980), 9–28. 1, 2
  • [2] H. W. Gould, Some generalizations of Vandermonde’s convolution, The American Mathematical Monthly, 63(1956), 84–91. 1.5
  • [3] N. S. S. Gu, H. Prodinger, Bijections for 2-plane trees and ternary trees, Europ. J. Combin., 30(4)(2009), 969–985. 1, 1
  • [4] N. S. S. Gu, H. Prodinger, S. Wagner, Bijections for a class of labelled plane trees, Europ. J. Combin., 31(3) (2010), 720–732. 1, 1, 2
  • [5] K. O. Lumumba, I. O. Okoth, D. M. Kasyoki, Refined enumeration of 2−plane trees, Preprint, (2024). 1, 2, 2, 3, 3
  • [6] A. P. O. Nyariaro, I. O. Okoth, Bijections for classes of labelled trees, Trans. Combin., 13(3) (2024), 197–211. 1, 2
  • [7] I. O. Okoth, Bijections of k-plane trees, Open J. Discret. Appl. Math., 5(1) (2022), 29–35. 1, 2, 4.2, 4.2
  • [8] I. O. Okoth, Enumeration of k-noncrossing trees and forests, Commun. Comb. Optim., 7(2) (2022) 301–311. 1, 2, 4.2
  • [9] I. O. Okoth, On 2-noncrossing increasing trees, Open J. Discret. Appl. Math., 6(2) (2023), 39–50. 1, 1
  • [10] I. O. Okoth, S. Wagner, Refined enumeration of k-plane trees and k-noncrossing trees, Ann. Combin. (2023), 1–33. 1
  • [11] K. H. Rosen, Discrete Mathematics and its Applications, The McGraw Hill Companies, (2007). 1.2, 1, 1.3, 1.4
  • [12] S. Seo, H. Shin, A generalized enumeration of labelled trees and reverse Prüfer algorithm, J. Combin. Theory Ser. A, 114(7) (2007), 1357–1361. 1
  • [13] S. Seunghyun, H. Shin, A refinement for ordered labeled trees, Korean J. Math., 20(2) (2012), 225–261. 1
  • [14] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences (OEIS), Available online at http://oeis.org. 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] H. S. Wilf, Generatingfunctionology, A. K. Peters, Ltd., Natick, MA, USA, (2006). 1.1
Cite this article as:
  • Albert Oloo Nyariaro and Isaac Owino Okoth*, Enumeration of k-plane trees and forests, Communications in Combinatorics, Cryptography & Computer Science, 2024(2), PP.152–168, 2024
  • Export citation to BibTeX