Dyck Paths with Parity Restrictions for the Final Runs to the Origin: a Study of the Height

• Autorzy: Prodinger H.
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

Dyck paths; height; generating functions; asymptotic equivalent

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 279--285
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Prodinger H.

• Department of Mathematics University of Stellenbosch 7602 Stellenbosch, South Africa,

Bibliografia

• [1] D. Callan. The 136th manifestation of Cn. arXiv:math, 0511010 (3 pages), 2005.
• [2] N. G. De Bruijn, D. E. Knuth, and S. O. Rice. The average height of planted plane trees. In R. C. Read, editor, Graph Theory and Computing, pages 15-22. Academic Press, 1972.
• [3] P. Flajolet, X. Gourdon, and P. Dumas. Mellin transforms and asymptotics: Harmonic sums. Theoretical Computer Science, 144:3-58, 1995.
• [4] P. Flajolet and A. Odlyzko. The average height of binary trees and other simple trees. Journal of Computer and System Science, 25:171-213, 1982.
• [5] P. Flajolet and A. Odlyzko. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics, 3(2):216-240, 1990.
• [6] P. Flajolet and H. Prodinger. Register allocation for unary-binary trees. SIAM J. Comput., 15:629-640, 1986.
• [7] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, Cambridge, 2008.
• [8] H. Prodinger. The height of planted plane trees revisited. Ars Combinatoria, 16 B:51-55, 1983.
• [9] H. Prodinger. Some analytic techniques for the investigation of the asymptotic behaviour of tree parameters. EATCS Bulletin, 47:180-199, 1992.
• [10] H. Prodinger. The location of the first maximum in the first sojourn of a Dyck path. Discrete Mathematics and Theoretical Computer Science, 10:125-134, 2008.
• [11] R. Stanley. Enumerative combinatorics. Vol. 2. Cambridge University Press, Cambridge, 1999.