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

Counting Peaks at Height k in a Dyck Path

Toufik Mansour

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

(Mentions sequence A000108 .)

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