Counting Dyck Paths with Strictly Increasing Peak Sequences

Abstract:

      In this paper we consider the enumeration of subsets of the set, say ${\cal D}_m$, of those Dyck paths of arbitrary length with maximum peak height equal to $m$ and having a strictly increasing sequence of peak height (as one goes along the path). Bijections and the methods of generating trees together with those of Riordan arrays are used to enumerate these subsets, resulting in many combinatorial structures counted by such well-known sequences as the Catalan nos., Narayana nos., Motzkin nos., Fibonacci nos., Schr\"{o}der nos., and the unsigned Stirling numbers of the first kind. In particular, we give two configurations which do not appear in Stanley's well-known list of Catalan structures.