Growing and destroying Catalan–Stanley trees
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Discrete Mathematics and Theoretical Computer Science
Abstract
Stanley lists the class of Dyck paths where all returns to the axis are of odd length as one of the many objects enumerated
by (shifted) Catalan numbers. By the standard bijection in this context, these special Dyck paths correspond
to a class of rooted plane trees, so-called Catalan–Stanley trees.
This paper investigates a deterministic growth procedure for these trees by which any Catalan–Stanley tree can be
grown from the tree of size one after some number of rounds; a parameter that will be referred to as the age of the
tree. Asymptotic analyses are carried out for the age of a random Catalan–Stanley tree of given size as well as for the
“speed” of the growth process by comparing the size of a given tree to the size of its ancestors.
Description
CITATION: Hack, B. & Prodinger, H. 2018. Growing and destroying catalan–stanley trees. Discrete Mathematics and Theoretical Computer Science, 20(1):1-14, doi:10.23638/DMTCS-20-1-11.
The original publication is available at https://www.semanticscholar.org
The original publication is available at https://www.semanticscholar.org
Keywords
Planar trees, Catalan–Stanley trees, Dyck paths, Asymptotic analysis
Citation
Hack, B. & Prodinger, H. 2018. Growing and destroying catalan–stanley trees. Discrete Mathematics and Theoretical Computer Science, 20(1):1-14, doi:10.23638/DMTCS-20-1-11