Enumeration of k-noncrossing trees and forests

Document Type : Original paper

Author

Department of Pure and Applied Mathematics, School of Mathematics, Statistics and Actuarial Science, Maseno University, Maseno, Kenya

Abstract

A   $k$-noncrossing tree is a noncrossing tree where each node receives a label in $\{1,2,\ldots,k\}$ such that the sum of labels along an ascent does not exceed $k+1,$ if we consider a path from a fixed vertex called the root. In this paper, we provide a proof for a formula that counts the number of $k$-noncrossing trees in which the root (labelled by $k$) has degree $d$. We also find a formula for the number of forests in which each component is a $k$-noncrossing tree whose root is labelled by $k$.

Keywords

Main Subjects

References

1] E. Deutsch and M. Noy, Statistics on non-crossing trees, Discrete Math. 254 (2002), no. 1-3, 75–87.
[2] P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math. 204 (1999), no. 1-3, 203–229.
[3] D.S. Hough, Descents in noncrossing trees, Electron. J. Combin. 10 (2003), Aticle ID: 13.
[4] M. Noy, Enumeration of noncrossing trees on a circle, Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995), vol. 180, 1998, pp. 301–313.
[5] Isaac O. Okoth and S. Wagner, Locally oriented noncrossing trees, Electron. J. Combin. 22 (2015), Aticle ID 3.36.
[6] S.X.M. Pang and L. Lv, K-noncrossing trees and k-proper trees, 2010 2nd International Conference on Information Engineering and Computer Science, 2010, pp. 1–3.
[7] S.X.M. Pang and L. Lv, A refinement of leaves on noncrossing trees, Graphs Combin. 29 (2013), no. 1, 131–143.
[8] A. Panholzer and H. Prodinger, Bijection for ternary trees and non-crossing trees, Discrete Math. 250 (2002), no. 1-3, 115–125.
[9] D.G. Rogers, A Schr¨oder triangle: Three combinatorial problems, Proc. Fifth Austrian Conf., Lecture Notes in Mathematics 622 (Springer-Verlag, Berlin), 1977, pp. 175–196.
[10] S.H.F. Yan and X. Liu, 2-noncrossing trees and 5-ary trees, Discrete Math. 309 (2009), no. 20, 6135–6138.
 
Communications in Combinatorics and Optimization
Volume 7, Issue 2
December 2022
Pages 301-311

Files

Share

How to cite

Statistics