140 research outputs found
Growing and destroying Catalan–Stanley trees
No full textCITATION: 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.orgStanley 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://www.semanticscholar.org/paper/Growing-and-Destroying-Catalan-Stanley-Trees-Hackl-Prodinger/eced0779211103ebf2752dc775e2a91b5beb5d73Publisher's versio
Down-step statistics in generalized Dyck paths
No full textThe number of down-steps between pairs of up-steps in -Dyck paths, a
generalization of Dyck paths consisting of steps such
that the path stays (weakly) above the line , is studied. Results are
proved bijectively and by means of generating functions, and lead to several
interesting identities as well as links to other combinatorial structures. In
particular, there is a connection between -Dyck paths and perforation
patterns for punctured convolutional codes (binary matrices) used in coding
theory. Surprisingly, upon restriction to usual Dyck paths this yields a new
combinatorial interpretation of Catalan numbers
Binomial Sums and Mellin Asymptotics with Explicit Error Bounds: A Case Study
No full textMaking use of a newly developed package in the computer algebra system SageMath, we show how to perform a full asymptotic analysis by means of the Mellin transform with explicit error bounds. As an application of the method, we answer a question of Bóna and DeJonge on 132-avoiding permutations with a unique longest increasing subsequence that can be translated into an inequality for a certain binomial sum
Uncovering a Random Tree
No full textWe consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with n vertices is generated uniformly at random. Thereafter, the vertices are uncovered one by one, in order of their labels. With each new vertex, all edges to previously uncovered vertices are uncovered as well. In this way, one obtains a growing sequence of forests. Three particular aspects of this process are studied in this extended abstract: first the number of edges, which we prove to converge to a stochastic process akin to a Brownian bridge after appropriate rescaling. Second, the connected component of a fixed vertex, for which different phases are identified and limiting distributions determined in each phase. Lastly, the largest connected component, for which we also observe a phase transition
Counting Ascents in Generalized Dyck Paths
No full textNon-negative Lukasiewicz paths are special two-dimensional lattice paths never passing below their starting altitude which have only one single special type of down step. They are well-known and -studied combinatorial objects, in particular due to their bijective relation to trees with given node degrees.
We study the asymptotic behavior of the number of ascents (i.e., the number of maximal sequences of consecutive up steps) of given length for classical subfamilies of general non-negative Lukasiewicz paths: those with arbitrary ending altitude, those ending on their starting altitude, and a variation thereof. Our results include precise asymptotic expansions for the expected number of such ascents as well as for the corresponding variance
Using Fiction to Teach Writing and Revision Techniques
No full textWould you like to take your writing and that of your students to the next level? This interactive session, led by award-winning and best-selling author Jo Watson Hackl, will equip you with tools and techniques to use with your students to help make their writing more powerful, more persuasive and more fun. Handouts include writing prompts, brainstorming tools, tips to keep inspiration close at hand, and an author-created bookmark revision tool that can be used for both creative writing and academic essays
Asymptotic analysis of shape parameters of trees and lattice paths
No full textBenjamin HacklDissertation Alpen-Adria-Universität Klagenfurt 2018Zusammenfassung in deutscher Sprach
Asymptotic analysis of shape parameters of trees and lattice paths
No full textBenjamin HacklDissertation Alpen-Adria-Universität Klagenfurt 2018Zusammenfassung in deutscher Sprach
Asymptotic analysis of lattice paths and related structures
No full textBenjamin HacklMasterarbeit Alpen-Adria-Universität Klagenfurt 2015Zusammenfassung in deutscher Sprach
Asymptotic analysis of lattice paths and related structures
No full textBenjamin HacklMasterarbeit Alpen-Adria-Universität Klagenfurt 2015Zusammenfassung in deutscher Sprach
- …
