A Decomposition Algorithm for Noncrossing Trees

Abstract

Based on the classic bijective algorithm for trees due to Chen, 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 Flajolet and Noy. As an application of our algorithm, we answer a question proposed by Hough, which asks for a bijection between two classes of noncrossing trees with a given number of descents.