Journal of Integer Sequences, Vol. 15 (2012), Article 12.1.1

Counting Dyck Paths According to the Maximum Distance Between Peaks and Valleys

Toufik Mansour
Department of Mathematics
University of Haifa
31905 Haifa

Mark Shattuck
Department of Mathematics
University of Tennessee
Knoxville, TN 37996


A Dyck path of length 2n is a lattice path from (0,0) to (2n,0) consisting of up-steps u=(1,1) and down-steps d=(1,-1)which never passes below the x-axis. Let $\mathcal{D}_n$ denote the set of Dyck paths of length 2n. A peak is an occurrence of ud (an upstep immediately followed by a downstep) within a Dyck path, while a valley is an occurrence of du. Here, we compute explicit formulas for the generating functions which count the members of $\mathcal{D}_n$ according to the maximum number of steps between any two peaks, any two valleys, or a peak and a valley. In addition, we provide closed expressions for the total value of the corresponding statistics taken over all of the members of $\mathcal{D}_n$. Equivalent statistics on the set of 231-avoiding permutations of length n are also described.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A000108.)

Received August 8 2011; revised version received November 6 2011. Published in Journal of Integer Sequences, December 15 2011.

Return to Journal of Integer Sequences home page