Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.1

Counting Peaks at Height k in a Dyck Path

Toufik Mansour

Université Bordeaux 1
351, cours de la Libération
33405 Talence Cedex, France

Abstract: A Dyck path is a lattice path in the plane integer lattice Z x Z consisting of steps (1,1) and (1,-1), which never passes below the x-axis. A peak at height k on a Dyck path is a point on the path with coordinate y=k that is immediately preceded by a (1,1) step and immediately followed by a (1,-1) step. In this paper we find an explicit expression for the generating function for the number of Dyck paths starting at (0,0) and ending at (2n,0) with exactly r peaks at height k. This allows us to express this function via Chebyshev polynomials of the second kind and the generating function for the Catalan numbers.

Full version:  pdf,    dvi,    ps,    latex    

(Mentions sequence A000108 .)

Received March 21, 2002; revised version received April 14, 2002. Published in Journal of Integer Sequences May 1, 2002.

Return to Journal of Integer Sequences home page