Refined enumeration of 2-noncrossing trees

Isaac Owino Okoth
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 27, 2021, Number 2, Pages 201–210
DOI: 10.7546/nntdm.2021.27.2.201-210
Full paper (PDF, 197 Kb)

Details

Authors and affiliations

Isaac Owino Okoth
Department of Pure and Applied Mathematics, Maseno University
Private Bag, Maseno, Kenya

Abstract

A 2-noncrossing tree is a connected graph without cycles that can be drawn in the plane with its vertices on the boundary of circle such that the edges are straight line segments that do not cross and all the vertices are coloured black and white with no ascent (i, j), where i and j are black vertices, in a path from the root. In this paper, we use generating functions to prove a formula that counts 2-noncrossing trees with a black root to take into account the number of white vertices of indegree greater than zero and black vertices. Here, the edges of the 2-noncrossing trees are oriented from a vertex of lower label towards a vertex of higher label. The formula is a refinement of the formula for the number of 2-noncrossing trees that was obtained by Yan and Liu and later on generalized by Pang and Lv. As a consequence of the refinement, we find an equivalent refinement for 2-noncrossing trees with a white root, among other results.

Keywords

• 2-noncrossing trees
• Local orientation
• Sources

2020 Mathematics Subject Classification

• 05A19
• 05C05
• 05C30

References

1. Deutsch. E., & Noy, M. (2002). Statistics on non-crossing trees, Discrete Mathematics, 254, 1–3, 75–87.
2. Du, R. R. X., & Yin, J. (2010). Counting labelled trees with a given indegree sequence, Journal of Combinatorial Theory, Series A, 117, 3, 345 – 353.
3. Flajolet, P., & Noy, M. (1999). Analytic combinatorics of non-crossing configurations, Discrete Mathematics, 204, 1–3, 203–229.
4. Noy, M. (1998). Enumeration of noncrossing trees on a circle. In Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995), Vol. 180, 301–313.
5. Okoth, I. O., & Wagner, S. (2015). Locally oriented noncrossing trees. Electronic Journal of Combinatorics, 22(3), Article ID P3.36.
6. Okoth, I. O., & Wagner, S. (2020). Refined enumeration of k-plane trees and k-noncrossing trees. Preprint.
7. Pang, S. X. M., & Lv, L. (2010). K-Noncrossing Trees and K-Proper Trees. 2010 2nd International Conference on Information Engineering and Computer Science, Wuhan, 1–3.
8. Stanley, R. P. (1999). Enumerative Combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge.
9. Yan, S. H. F., & Liu, X. (2009). 2-noncrossing trees and 5-ary trees. Discrete Mathematics, 309(20), 6135–6138.