A decomposition algorithm for noncrossing trees (Q405065): Difference between revisions

Summary: Based on the classic bijective algorithm for trees due to \textit{W. Y. C. Chen} [Proc. Natl. Acad. Sci. USA 87, No. 24, 9635--9639 (1990; Zbl 0707.05019)], we present a decomposition algorithm for noncrossing trees. This leads to a combinatorial interpretation of a formula on noncrossing trees of size \(n\) with \(k\) descents. We also derive the formula for noncrossing trees of size \(n\) with \(k\) descents and \(i\) leaves, which is a refinement of the formula given by \textit{P. Flajolet} and \textit{M. Noy} [Discrete Math. 204, No. 1--3, 203--229 (1999; Zbl 0939.05005)]. As an application of our algorithm, we answer a question proposed by \textit{D. S. Hough} [Electron. J. Comb. 10, Research Paper N13, 5 p. (2003; Zbl 1031.05066)], which asks for a bijection between two classes of noncrossing trees with a given number of descents.