Benjamin Hackl ; Helmut Prodinger - Growing and Destroying Catalan-Stanley Trees

dmtcs:3964 - Discrete Mathematics & Theoretical Computer Science, February 28, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-11
Growing and Destroying Catalan-Stanley TreesArticle

Authors: Benjamin Hackl ; Helmut Prodinger

    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.


    Volume: Vol. 20 no. 1
    Section: Analysis of Algorithms
    Published on: February 28, 2018
    Accepted on: February 14, 2018
    Submitted on: September 28, 2017
    Keywords: Mathematics - Combinatorics,05A16, 05C05, 05A15
    Funding:
      Source : OpenAIRE Graph
    • Asymptotic Analysis of Extremal Discrete Structures; Funder: Austrian Science Fund (FWF); Code: P 24644

    Consultation statistics

    This page has been seen 511 times.
    This article's PDF has been downloaded 297 times.