On a variant of $k$-plane trees
DOI:
https://doi.org/10.13069/jacodesmath.v12i3.329Keywords:
$k$-plane tree, $k_1$-plane tree, Root degree, Eldest child, Youngest child, ForestAbstract
In this paper, we introduce a class of plane trees whose vertices receive labels from the set $\{1, 2, \dots, k\}$ such that the sum of labels of adjacent vertices does not exceed $k + 1$ and all vertices of label $1$ are always on the left of all other vertices. Using generating functions, we enumerate these trees by number of vertices and label of the root, root degree, label of the eldest or youngest child of the root and forests.
Accepted: 9 February 2025
Downloads
References
F. Ardila, Algebraic and geometric methods in enumerative combinatorics, Handbook of Enumerative Combinatorics (2015) 589–678.
N. G. de Bruijn, B. J. M. Morselt, A note on plane trees, Journal of Combinatorial Theory 2(1) (1967) 27–34.
N. Dershowitz, S. Zaks, Enumerations of ordered trees, Discrete Mathematics 31(1) (1980) 9–28.
I. M. Gessel, Schröder numbers, large and small, A talk at CanaDAM (2009).
N. S. S. Gu, H. Prodinger, Bijections for 2-plane trees and ternary trees, European Journal of Combinatorics 30(4) (2009) 969–985.
N. S. S. Gu, H. Prodinger, S. Wagner, Bijections for a class of labelled plane trees, European Journal of Combinatorics 31(3) (2010) 720–732.
Y. W. Kariuki, I. O. Okoth, Bijections of Plane Husimi graphs and certain combinatorial structures, European Journal of Mathematics and Applications 3(21) (2023).
Y. W. Kariuki, I. O. Okoth, F. O. Nyamwala, On non-decreasing 2-plane trees, Electronic Journal of Mathematics 2 (2024) 2783–5456.
K. O. Lumumba, I. O. Okoth, D. M. Kasyoki, Refined enumeration of 2-plane trees, European Journal of Mathematics and Applications 5(8) (2025).
A. P. O. Nyariaro, I. O. Okoth, Bijections for classes of labelled trees, Transactions on Combinatorics 13(3) (2024) 197–211.
I. O. Okoth, Bijections of k-plane trees, Open Journal of Discrete Applied Mathematics 5(1) (2022) 29–35.
I. O. Okoth, On 2-noncrossing increasing trees, Open Journal of Discrete Applied Mathematics 6(2) (2023) 39–50.
I. O. Okoth, On noncrossing and plane tree-like structures, Communications in Advanced Mathematical Sciences 4(2) (2021) 89–99.
I. O. Okoth, S. Wagner, Refined enumeration of k-plane trees and k-noncrossing trees, Annals of Combinatorics (2023) 1–33.
C. A. Onyango, I. O. Okoth, D. M. Kasyoki, Enumeration of plane and d-ary tree-like structures, Annals of Mathematics and Computer Science 17 (2023) 10–25.
F. Qi, B. N. Guo, Some explicit and recursive formulas of the large and little Schröder numbers, Arab Journal of Mathematical Sciences 23(2) (2017) 141–147.
K. H. Rosen, Discrete Mathematics and its Applications, The McGraw Hill Companies, 2007.
G. Rote, Binary trees having a given number of nodes with 0, 1, and 2 children, Séminaire Lotharingien de Combinatoire B38b (1997).
L. W. Shapiro, C. J. Wang, A bijection between 3-Motzkin paths and Schröder paths with no peak at odd height, Journal of Integer Sequences 12(2) (2009).
N. J. A. Sloane, The online encyclopedia of integer sequences (OEIS).
R. P. Stanley, Enumerative Combinatorics, Cambridge University Press, Vol. 2, 1999.
R. P. Stanley, Exercises on Catalan numbers and related numbers, Cambridge University Press (1999).
R. P. Stanley, Polygon dissections and standard Young tableaux, Journal of Combinatorial Theory, Series A 76 (1996) 175–177.
H. S. Wilf, Generatingfunctionology, A K Peters/CRC Press, Natick, MA, USA, 2006.
