A decomposition algorithm for noncrossing trees

MaRDI QIDQ405065zbMATH OpenFDO

Authors Lun Lv, Sabrina X. M. Pang

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p5

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bijectiondescentnoncrossing tree

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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.

Recommendations

• Decomposition and merging algorithms for noncrossing forests
• Descents in noncrossing trees
• Noncrossing trees and noncrossing graphs
• Statistics on non-crossing trees
• Locally oriented noncrossing trees

Cites work

• A general bijective algorithm for trees.
• Analytic combinatorics of non-crossing configurations
• Bijections for ternary trees and non-crossing trees
• Consecutive pattern avoidances in non-crossing trees
• Descents in noncrossing trees
• Dyck path enumeration
• Dyck paths with coloured ascents
• Enumeration of noncrossing trees on a circle
• scientific article; zbMATH DE number 6683596 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Noncrossing trees and noncrossing graphs
• Statistics on non-crossing trees
• The cyclic sieving phenomenon for non-crossing forests

Cited in

(6)

• Descents in noncrossing trees
• Decomposition and merging algorithms for noncrossing forests
• Noncrossing trees and noncrossing graphs
• A general bijective algorithm for increasing trees
• Parameterized algorithms for non-separating trees and branchings in digraphs
• An Iterative Heuristic Algorithm for Tree Decomposition

This page was built for publication: A decomposition algorithm for noncrossing trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405065)