Bijections for classes of labelled trees

Document Type : Research Paper

Authors

Department of Pure and Applied Mathematics, Maseno University, Maseno, Kenya

Abstract

Trees are acyclic connected graphs. Plane trees, $d$-ary trees, binary trees, noncrossing trees and their generalizations, which are families of trees, have been enumerated by many authors using various statistics. These trees are known to be enumerated by Catalan or Catalan-like formulas (Fuss-Catalan numbers). One of the most common approaches to the enumeration of these trees is by means of generating functions. Another method that can be used to enumerate them is by constructing bijections between sets of the same cardinality. The bijective method is preferred to other methods by many combinatorialists. So, in this paper, we construct bijections relating $k$-plane trees, $k$-noncrossing increasing trees, $k$-noncrossing trees, $k$-binary trees and weakly labelled $k$-trees.

Keywords

Main Subjects


[1] A. Asinowski and T. Mansour, Dyck paths with coloured ascents, European J. Combin, 29 no. 5
(2008) 1262–1279.
[2] A. Cayley, A theorem on trees, Quart. J. Math., 23 (1889) 376–378.
[3] N. Dershowitz and S. Zaks, Enumerations of ordered trees, Discret. Math., 31 no. 1 (1980) 9–28.
[4] E. Deutsch and M. Noy, Statistics on non-crossing trees, Discrete Math., 254 no. 1-3 (2002) 75–87.
[5] P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discret. Math., 204 no. 1-3 (1999) 203–229.
[6] P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009.
[7] N. S. S. Gu, N. Y. Li and T. Mansour, 2-binary trees: bijections and related issues, Discret. Math., 308 no. 7 (2008) 1209–1221.
[8] N. S. S. Gu and H. Prodinger, Bijections for 2-plane trees and ternary trees, European J. Combin., 30 no. 4 (2009) 969–985.
[9] N. S. S. Gu, H. Prodinger and S. Wagner, Bijections for a class of plane trees, European J. Combin., 31 no. 3 (2010) 720–732.
[10] D. E. Knuth, The art of computer programming, 1, Fundamental algorithms, Third edition, Addison-Wesley, Reading, MA, 1997.
[11] 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.
[12] I. O. Okoth, Bijections for k-plane trees, Open J. Discret. Appl. Math, 5 no. 1 (2022) 29–35.
[13] I. O. Okoth, Enumeration of k-noncrossing trees and forests, Commun. Comb. Optim., 7 no. 2 (2022) 301–311.
[14] I. O. Okoth, On 2-noncrossing increasing trees, To appear in Open J. Discret. Appl. Math., (2021).
[15] I. O. Okoth and S. Wagner, Refined enumeration of k-plane trees and k-noncrossing trees, Annals of Combinatorics, (2023) 1-33.
[16] A. Panholzer and H. Prodinger, Bijections between certain families of labelled and unlabelled d-ary trees, Appl. Anal. Discrete Math., 3 (2009) 123–136.
[17] A. Panholzer and H. Prodinger, Bijection for ternary trees and non-crossing trees, Discret. Math., 250 no. 1-3 (2002) 115–125.
[18] S. X. M. Pang and L. Lv, K-Noncrossing Trees and K-Proper Trees, 2010 2nd International Conference on Information Engineering and Computer Science, Wuhan, (2010) 1–3.
[19] H. Prodinger, A simple bijection between a subclass of 2-binary trees and ternary trees, Discret. Math., 309 no. 4 (2009) 959–961.
[20] R. P. Stanley, Enumerative combinatorics, 2, With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999.
[21] S. H. F. Yan and X. Liu, 2-noncrossing trees and 5-ary trees, Discrete Math., 309 no. 20 (2009) 6135–6138.
 
Volume 13, Issue 3 - Serial Number 3
September 2024
Pages 197-211
  • Receive Date: 20 February 2022
  • Revise Date: 09 June 2023
  • Accept Date: 14 June 2023
  • Published Online: 01 September 2024