Dyck paths with parity restrictions for the final runs to the origin: A study of the height

Prodinger H. (2012)


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].

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/21826
This item appears in the following collections: