Peaks and Valleys in Motzkin Paths

Abstract

A Motzkin path is a non-negative lattice path in N² starting at the origin, where only three types of steps are allowed: the diagonal up step (1, 1) called u, the diagonal down step (1, −1) called d and the horizontal step (1, 0) called h. We consider paths of size n, ending at the point (n, 0). A peak is defined to be a node between the following steps: uh, hh, hd and ud, and a valley is a node between dh, hh, hu and du. A sharp peak or a sharp valley is the node between the steps ud and du respectively. We also define a low peak to be a peak on level one and a low valley to be a valley on level zero. In this paper, we find the asymptotic expressions for the average number of peaks, sharp peaks, low peaks, low sharp peaks and similarly for valleys on Motzkin paths of size n as n →∞.