Bijections for classes of labelled trees

Nyariaro, Albert P. Oloo; Okoth, Isaac Owino

doi:10.22108/toc.2023.132794.1965

تعداد نشریات	43
تعداد شماره‌ها	1,637
تعداد مقالات	13,313
تعداد مشاهده مقاله	29,870,089
تعداد دریافت فایل اصل مقاله	11,944,663

	Bijections for classes of labelled trees
Transactions on Combinatorics
دوره 13، شماره 3، آذر 2024، صفحه 197-211 اصل مقاله (520.77 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2023.132794.1965
نویسندگان
Albert P. Oloo Nyariaro؛ Isaac Owino Okoth^*
Department of Pure and Applied Mathematics, Maseno University, Maseno, Kenya
چکیده
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.
کلیدواژه‌ها
$k$-plane tree؛ $k$-noncrossing tree؛ $k$-binary tree؛ weakly labelled $k$-tree

مراجع
[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.
آمار تعداد مشاهده مقاله: 110 تعداد دریافت فایل اصل مقاله: 185

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Bijections for classes of labelled trees