##
**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

G_k(x) = 1 / (1-xG_{k-1}(x)), k >= 2, G_1(x) = 2 / (1+2x+sqrt{1-4x}).
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.

**
Full version:
pdf,
ps,
dvi,
latex,
**

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

Received October 16, 2000; revised version received February 8, 2001;
published in Journal of Integer Sequences, May 12, 2001.

Return to
**Journal of Integer Sequences home page**