Original Research Article

Article volume = 2024 and issue = 2

Pages: 119–135

Article publication Date: April 08, 2024

You can download PDF file of the article here: Download

Visited 234 times and downloaded 102 times

On non-decreasing 2-plane trees

Yvonne Wakuthii Kariuki(a), Isaac Owino Okoth(b), and Fredrick Oluoch Nyamwala(c)

(a) Department of Mathematics, Kibabii University, Bungoma, Kenya.

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

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

Abstract:

In this paper, we have introduced the set of non-decreasing 2-plane trees. These are plane trees whose vertices receive labels from the set {1, 2} such that the sum of labels of adjacent vertices is at most 3 and that the labels of siblings are weakly increasing from left to right. We have obtained the formula for the number of these trees with a given number of vertices and label of the root. Further, we have obtained the number of these trees given root degrees and label of the eldest child of the root. We have also constructed bijections between the set of non-decreasing 2-plane trees with roots labelled 2 and the sets of little Schröder paths, plane trees in which leaves receive two labels, restricted lattice paths and increasing tableaux. For non-decreasing 2-plane trees with roots labelled 1, we have obtained bijections between the set of these trees and the sets of large Schröder paths and row-increasing tableaux.

Keywords:

Non-decreasing 2-plane tree, Large Schröder path, Little Schröder path, Lattice path, Increasing tableau, Row-increasing tableau.

References:
  • [1] M. Aguiar, W. Moreira, Combinatorics of the free Baxter algebra, arXiv preprint math/0510169 (2005). 1, 3.3
  • [2] F. Ardila, Algebraic and geometric methods in enumerative combinatorics, Handbook of enumerative combinatorics (2015), 589–678. 1
  • [3] N. G. de Bruijn, D. E. Knuth, S. O. Rice, The average height of planted plane trees, Graph Theory and Computing, Academic Press, (1972), 15–22. 1
  • [4] N. G. de Bruijn, B. J. M. Morselt, A note on plane trees, J. Combin. Theory, 2(1) (1967), 27–34. 1
  • [5] N. Dershowitz, S. Zaks, Enumerations of ordered trees, Discret. Math., 31(1) (1980), 9–28. 1
  • [6] R. R. X. Du, X. Fan, Y. Zhao, Enumeration on row-increasing tableaux of shape 2 × n, arXiv preprint arXiv:1803.01590 (2018). 1, 4.2
  • [7] I. M. Gessel, Lagrange inversion, J. Combin. Theory, Ser. A 144 (2016), 212-249. 1.1
  • [8] I. M. Gessel, Schröder numbers, large and small, A talk at CanaDAM (2009). 1
  • [9] N. S. S. Gu, H. Prodinger, Bijections for 2-plane trees and ternary trees, Europ. J. Combin., 30(4) (2009), 969–985. 2
  • [10] 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. 1, 2, 5
  • [11] Y. W. Kariuki, I. O. Okoth, Bijections of Plane Husimi graphs and certain combinatorial structures, Eur. J. Math. Appl. 3 (2023), 21. 1
  • [12] K. O. Lumumba, I. O. Okoth, D. M. Kasyoki, Refined enumeration of 2-plane trees, Preprint. 1, 2
  • [13] W. Mlotkowski, K. A. Penson, The probability measure corresponding to 2-plane trees, arXiv preprint arXiv:1304.6544 (2013). 2
  • [14] A. P. O. Nyariaro, I. O. Okoth, Bijections for classes of labelled trees, Transactions on Combinatorics, 13(3) (2024), 197–211. 2
  • [15] I. O. Okoth, Bijections of k-plane trees, Open Journal of Discrete Applied Mathematics, 5(1) (2022), 29–35. 2
  • [16] I. O. Okoth, On 2-noncrossing increasing trees, Open Journal of Discrete Applied Mathematics, (2021). 2
  • [17] I. O. Okoth, S. Wagner, Refined enumeration of k-plane trees and k-noncrossing trees, Annals of Combinatorics (2023), 1–33. 2
  • [18] O. Pechenik, Cyclic sieving of increasing tableaux and small Schroeder paths, J. Combin.Theory, Ser. A, 125(2014), 357–378. 1, 3.4
  • [19] H. Prodinger, Weighted unary, binary trees, Hex trees, marked ordered trees, and related structures, arXiv preprint arXiv:2106.14782 (2021). 1
  • [20] H. Prodinger, S. J. Selkirk, S. Wagner, On two subclasses of Motzkin paths and their relation to ternary trees, Algorithmic Combinatorics: Enumerative Combinatorics, Special Functions and Computer Algebra: In Honour of Peter Paule on his 60th Birthday (2020), 297–316. 1
  • [21] F. Qi, B-N Guo, Some explicit and recursive formulas of the large and little Schrƶder numbers, Arab J. Math. Sci. 23(2) (2017), 141–147. 1
  • [22] L. W. Shapiro, C. J. Wang, A bijection between 3-Motzkin paths and Schrƶder paths with no peak at odd height, J. Integer Seq., 12(2) (2009), 3. 1
  • [23] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences (OEIS). Available online at http://oeis.org. 1
  • [24] R. P. Stanley, Polygon dissections and standard Young tableaux, J. Comb. Theory, Ser. A, 76 (1996), 175–177. 1
Cite this article as:
  • Yvonne Wakuthii Kariuki, Isaac Owino Okoth, and Fredrick Oluoch Nyamwala, On non-decreasing 2-plane trees, Communications in Combinatorics, Cryptography & Computer Science, 2024(2), PP.119–135, 2024
  • Export citation to BibTeX