A Decomposition Algorithm for Noncrossing Trees
Copyright policy )A Decomposition Algorithm for Noncrossing Trees
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.
- Hebei University China (People's Republic of)
- Hebei University of Economics and Business China (People's Republic of)
- Hebei University of Technology China (People's Republic of)
bijection, Graph algorithms (graph-theoretic aspects), Exact enumeration problems, generating functions, Enumeration in graph theory, noncrossing tree, descent, Trees
bijection, Graph algorithms (graph-theoretic aspects), Exact enumeration problems, generating functions, Enumeration in graph theory, noncrossing tree, descent, Trees
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!