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 [6]). In this paper, we derive the recurrence

G_{k}(x) = \frac{1}{1 − xG_{k−1}(x)}, k ≥ 2, G_{1}(x) = \frac{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} = \frac{1}{n+1} \binom{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.

1 Introduction

In [1] it was shown that Fine numbers (A000957) count Dyck paths with no peaks at height 1. One of the results of this paper is that the Catalan numbers (A000108) count Dyck paths with no peaks at height 2. This provides yet another combinatorial setting for the Catalan numbers (cf. [4], [5], [6], [7] ).

A Dyck path is a path in two-space which starts at the origin, stays above the x-axis, and allows only steps of (1, 1) (i.e. north-east) and (1, −1) (i.e. south-east). A Dyck path ends on the x-axis. A Dyck path therefore has even length with the number of north-east steps equal to the number of south-east steps. A lattice point on the path is called a peak if it 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. Here are two Dyck paths each of length 10:

∘  ∘
∘  ∘  ∘  ∘
∘  ∘  ∘
×  ∘

∘  ∘
∘  ∘  ∘
∘  ∘  ∘
×  ∘  ∘

The first path has one peak at height 2 and two peaks at height 3. It has no peaks at height 1. The second path has one peak at height 1 and two at height 3. It has no peaks at height 2. Reference [1] contains much information about Dyck paths. It is known that the number of Dyck paths of length 2n is c_{n}, the n^{th} Catalan number, given by

c_{n} = \frac{1}{n + 1} \binom{2n}{n} .

We will prove that the number of these paths with no peaks at height 2 is c_{n−1} . It is known [1] that the number of these paths with no peaks at height 1 is f_{n}, the n^{th} Fine number with generating function

F (x) = \frac{1}{1 − x^{2}C^{2}(x)} = 1 + x^{2} + 2x^{3} + 6x^{4} + 18x^{5} + 57x^{6} + 186x^{7} + O (x^{8})

where C(x) = \frac{1−\sqrt{1−4x}}{2x} is the generating function for the Catalan numbers. See [1], [2], and [3] for further information about the Fine numbers. Theorem 2 below contains a proof that the Fine numbers count Dyck paths with no peaks at height 1. In Theorem 1, we obtain the recurrence

G_{k}(x) = \frac{1}{1 − xG_{k−1}(x)} , k ≥ 2,

where G_{k}(x) is the generating function for the number of Dyck paths of length 2n with no peaks at height k. In Section 3 we introduce a bijection between the set of all Dyck paths of length 2n and the set of all Dyck paths of length 2n + 2 with no peaks at height 2. This bijection provides a combinatorial proof that G_{2}(x) = 1 + xC(x).

2 Theorems

We will use the fact that

F (x) = ∑_{n≥0} f_{n}x^{n} = \frac{C(x)}{1 + xC(x)}.

Theorem 1: Let G_{m}(x) = ∑_{n≥0} g(m, n)x^{n} be the generating function for Dyck paths of length 2n

with no peaks at height m, m ≥ 1. Then

G_{m}(x) = \frac{1}{1 − xG_{m−1}(x)} ; m ≥ 2 .

Proof. The set of all Dyck paths of length 2n , n ≥ 0, with no peaks at height m consists of the trivial path ( the origin) and paths with general form shown in the diagram.

\begin{aligned}& A \\ × & & B \end{aligned}

It starts with a north-east step followed by a segment labeled A which represents any Dyck path of length 2k, 0 ≤ k ≤ n − 1 , with no peaks at height m − 1. A is followed by a south-east step followed by a segment labeled B which represents any Dyck path of length 2n − 2 − 2k with no peaks at height m. Therefore

g(m, 0) = 1, g(m, n) = ∑_{k=0}^{n−1} g(m − 1, k)g(m, n − 1 − k) = [x^{n−1}] {G_{m−1}(x)G_{m}(x)}.

i.e. g(m, 0) = 1, g(m, n) = [x^{n}] {xG_{m−1}(x)G_{m}(x)} ; n ≥ 1,

where [x^{k}] denotes ”coefficient of x^{k} in ”. That is,

G_{m}(x) = 1 + x G_{m−1}(x)G_{m}(x) ,

or equivalently,

G_{m}(x) = \frac{1}{1 − xG_{m−1}(x)}

Theorem 2: The number of Dyck paths of length 2n with no peaks at height 1 is the Fine number f_{n} for n ≥ 0 . Proof. With the notation of Theorem 1, we will prove that

G_{1} = ∑_{n=0}^{∞} g(1, n)x^{n} = \frac{1}{1 − x^{2}C^{2}}

Obviously, g(1, 0) = 1 and g(1, 1) = 0. For n ≥ 2 , a Dyck path of length 2n with no peaks at height 1 has the form of the diagram in the proof of Theorem 1 with A any Dyck path of length 2k, 1 ≤ k ≤ n − 1 , and B a Dyck path of length 2n − 2k − 2 with no peaks at height 1. Therefore, for n ≥ 2 , we have

g(1, n) = ∑_{k=1}^{n−1} c_{k} g(1, n − k − 1) = [x^{n−1}]{C(x)G_{1}(x)} − g(1, n − 1)
= [x^{n}]{xC(x)G_{1}(x)} − g(1, n − 1)

Therefore

G_{1}(x) = 1 + ∑_{n≥2} g(1, n)x^{n} = 1 + xC(x)G_{1}(x) − x − xG_{1}(x) + x
= 1 + xG_{1}(x) (C(x) − 1) = 1 + xG_{1}(x)xC^{2}(x)

That is,

G_{1}(x) = \frac{1}{1 − x^{2}C^{2}(x)}

Theorem 3: The number of Dyck paths of length 2n with no peaks at height 2 is the Catalan number c_{n−1} , for n ≥ 1.

Proof. From Theorem 1,

G_{2}(x) = \frac{1}{1 − xG_{1}(x)} = \frac{1}{1 − x\frac{C(x)}{1+xC(x)}} = 1 + xC(x)

Remark: In [1] it was shown that

\frac{f_{n−1}}{c_{n}} → \frac{1}{9} as n → ∞

Therefore

\frac{f_{n}}{c_{n}} → \frac{4}{9} as n → ∞

Since

\frac{c_{n−1}}{c_{n}} → \frac{1}{4} as n → ∞

we see that, for sufficiently large n, approximately \frac{4}{9} of the Dyck paths of length 2n have no peaks at height 1, while approximately \frac{1}{4} have no peaks at height 2. Remark: G_{3}(x) = \frac{2}{2−3x+x\sqrt{(1−4x)}} = 1 + x + 2x^{2} + 4x^{3} + 9x^{4} + 22x^{5} + 58x^{6}

+163x^{7} + 483x^{8} + 1494x^{9} + O (x^{10}) (sequence A059019 in [6] ).

3 A bijection between two Catalan families

We end with a bijection between the two Catalan families mentioned in this paper. Let Φ be the set of all Dyck paths of length 2n and let Ψ be the set of all Dyck paths of length 2n + 2 with no peaks at height 2. We define a bijection between Φ and Ψ as follows. First, starting with a Dyck path P from Φ, we obtain a Dyck path P̂ from Ψ using the following steps.

(1) Attach a Dyck path of length 2 to the left of P to produce P^{∗}.

(2) Let S^{∗} be a maximal sub-Dyck path of P^{∗} with S^{∗} having no peaks at height 1. To each such S^{∗} add a north-east step at the beginning and a south-east step at the end to produce sub-Dyck path S̃. This step produces a Dyck path P̃.

(3) From P̃ eliminate each Dyck path of length 2 that is to the immediate left of each S̃. We now have a unique element P̂ of Ψ.

To obtain P from P̂ , we reverse the steps as follows:

(1) Let Ŝ be a sub-Dyck path of P̂ between two consecutive points on the x-axis with Ŝ having no peaks at height 1. To each Ŝ add a Dyck path of length 2 immediately to the left. This step produces a Dyck path P̃ .

(2) Let S̃ be a maximal sub-Dyck path of P̃ . From each such S̃ remove the left-most north-east step and the right-most south-east step to produce a sub-Dyck path S^{∗}. This step produces a Dyck path P^{∗} of length 2n+2.

(3) From P^{∗} , remove the left-most Dyck path of length 2 to produce P.

For example, we obtain a Dyck path of length 18 with no peaks at height 2 starting with a Dyck path of length 16 as follows:

P = \begin{aligned}& & & & & & & & & & & ∘ & & ∘ \\ & & ∘ & & ∘ & & & & & & ∘ & & ∘ & & ∘ \\ & ∘ & & ∘ & & ∘ & & ∘ & & ∘ & & & & & & ∘ \\ × & & & & & & ∘ & & ∘ & & & & & & & & ∘ \end{aligned}

P^{∗} = \begin{aligned}& & & & & & & & & & & & & ∘ & & ∘ \\ & & & & ∘ & & ∘ & & & & & & ∘ & & ∘ & & ∘ \\ & ∘ & & ∘ & & ∘ & & ∘ & & ∘ & & ∘ & & & & & & ∘ \\ × & & ∘ & & & & & & ∘ & & ∘ & & & & & & & & ∘ \end{aligned}

P̃ = \begin{aligned}& & & & & & & & & & & & & & & & ∘ & & ∘ \\ & & & & & ∘ & & ∘ & & & & & & & & ∘ & & ∘ & & ∘ \\ & & & & ∘ & & ∘ & & ∘ & & & & & & ∘ & & & & & & ∘ \\ & ∘ & & ∘ & & & & & & ∘ & & ∘ & & ∘ & & & & & & & & ∘ \\ × & & ∘ & & & & & & & & ∘ & & ∘ & & & & & & & & & & ∘ \end{aligned}

P̂ = \begin{aligned}& & & & & & & & & & & & ∘ & & ∘ \\ & & & ∘ & & ∘ & & & & & & ∘ & & ∘ & & ∘ \\ & & ∘ & & ∘ & & ∘ & & & & ∘ & & & & & & ∘ \\ & ∘ & & & & & & ∘ & & ∘ & & & & & & & & ∘ \\ × & & & & & & & & ∘ & & & & & & & & & & ∘ \end{aligned}

It is now easy to show that the Catalan numbers count paralellogram polynominoes ( or Fat Path Pairs ) with no columns at height 2 (see [7], p. 257).

References

[1] E. Deutsch. Dyck Path Enumeration. Discrete Math. 204 (1999), no. 1-3, 167-202.

[2] E. Deutsch & L. W. Shapiro. Fine Numbers. Preprint.

[3] T. Fine. Extrapolation when very little is known about the source. Information and Control 16 (1970) 331-359.

[4] H. W. Gould. Bell & Catalan Numbers: Research Bibliography of Two Special Number Sequences, 6th ed. Morgantown, WV: Math Monongliae, 1985.

[5] L. W. Shapiro. A Catalan Triangle. Discrete Math. 14 (1976) 83-90.

[6] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://www.research.att.com/∼njas/sequences/ .

[7] R. P. Stanley. Enumerative Combinatorics. Vol. 2. Cambridge University Press, 1999.

(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.