Counting Dyck Paths According to the Maximum Distance Between Peaks and

Valleys

Toufik Mansour Department of Mathematics University of Haifa 31905 Haifa Israel

                toufik@math.haifa.ac.il

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

                 shattuck@math.utk.edu

Abstract

A Dyck path of length 2n is a lattice path from (0, 0) to (2n, 0) consisting of upsteps u = (1, 1) and down-steps d = (1, −1) which never passes below the x-axis. Let 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 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 D_{n}. Equivalent statistics on the set of 231-avoiding permutations of length n are also described.