Journal of Integer Sequences, Vol. 4 (2001), Article 01.1.3

Dyck Paths With No Peaks At Height k

Paul Peart and Wen-Jin Woan
Department of Mathematics
Howard University
Washington, D.C. 20059, USA

Email addresses: pp@scs.howard.edu, wwoan@howard.edu

Abstract: A Dyck path of length 2n is a path in two-space from (0,0) to (2n,0) which uses only steps (1,1) (north-east) and (1,-1) (south-east). Further, a Dyck path does not go below the x-axis. A peak on a Dyck path is a node that is immediately preceded by a north-east step and immediately followed by a south-east step. A peak is at height k if its y-coordinate is k. Let G_k(x) be the generating function for the number of Dyck paths of length 2n with no peaks at height k with k >= 1. It is known that G_1(x) is the generating function for the Fine numbers (sequence A000957). In this paper, we derive the recurrence

It is interesting to see that in the case k=2 we get G_2(x)=1+xC(x), where C(x) is the generating function for the ubiquitous Catalan numbers (A000108). This means that the number of Dyck paths of length 2n+2, n >= 0, with no peaks at height 2 is the Catalan number c_n = 1 / (n+1) Binomial(2n, n). We also provide a combinatorial proof for this last fact by introducing a bijection between the set of all Dyck paths of length 2n+2 with no peaks at height 2 and the set of all Dyck paths of length 2n.

Keywords: Dyck paths, Catalan number, Fine number, generating function.

(Concerned with sequences A000108, A000957, A059019, A059027.)