Dyck paths with parity restrictions for the final runs to the origin: A study of the height
Date
2012
Authors
Prodinger H.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Stanley and Callan considered Dyck paths where the lengths of the run to the origin is always odd resp. the last one even, and the other ones odd. These subclasses are also enumerated by (shifted) Catalan numbers. We study the (average) height of these objects, assuming all such Dyck paths of length 2n to be equally likely, and find that it behaves like ~ π/n, as in the unrestricted case. This classic result for unrestricted Dyck paths is from de Bruijn, Knuth and Rice [2], and to this day, there are no simpler proofs for this, although more general results have been obtained by Flajolet and Odlyzko [4].
Description
Article
Keywords
asymptotic equivalent, Dyck paths, generating functions, height
Citation
Fundamenta Informaticae
117
04-Jan
279
285
117
04-Jan
279
285