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 Israel Mark Shattuck Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

Abstract:

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