Growing and Destroying Catalan-Stanley Trees
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....
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2018-02-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3964/pdf |
| _version_ | 1797270069100675072 |
|---|---|
| author | Benjamin Hackl Helmut Prodinger |
| author_facet | Benjamin Hackl Helmut Prodinger |
| author_sort | Benjamin Hackl |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:24Z |
| format | Article |
| id | doaj.art-4271381717384183980a024602548e26 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:24Z |
| publishDate | 2018-02-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-4271381717384183980a024602548e262024-03-07T15:36:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502018-02-01Vol. 20 no. 1Analysis of Algorithms10.23638/DMTCS-20-1-113964Growing and Destroying Catalan-Stanley TreesBenjamin HacklHelmut ProdingerStanley 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.https://dmtcs.episciences.org/3964/pdfmathematics - combinatorics05a16, 05c05, 05a15 |
| spellingShingle | Benjamin Hackl Helmut Prodinger Growing and Destroying Catalan-Stanley Trees Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05a16, 05c05, 05a15 |
| title | Growing and Destroying Catalan-Stanley Trees |
| title_full | Growing and Destroying Catalan-Stanley Trees |
| title_fullStr | Growing and Destroying Catalan-Stanley Trees |
| title_full_unstemmed | Growing and Destroying Catalan-Stanley Trees |
| title_short | Growing and Destroying Catalan-Stanley Trees |
| title_sort | growing and destroying catalan stanley trees |
| topic | mathematics - combinatorics 05a16, 05c05, 05a15 |
| url | https://dmtcs.episciences.org/3964/pdf |
| work_keys_str_mv | AT benjaminhackl growinganddestroyingcatalanstanleytrees AT helmutprodinger growinganddestroyingcatalanstanleytrees |