Statistics on Dyck Paths

Toufik Mansour Department of Mathematics University of Haifa 31905 Haifa Israel

and

Center for Combinatorics LPMC Nan’kai University Tianjin 300071 P. R. China

                toufik@math.haifa.ac.il

Abstract

In this paper we consider several statistics on the set of Dyck paths. Enumeration of Dyck paths according to length and various other parameters has been studied in several papers. However, the statistic “number of udu’s” has been considered only recently. We generalize this statistic and derive an explicit formula for the number of Dyck paths of length 2n according to the statistic “number of uu ⋯ udu’s” (“number of udud ⋯ udu’s”). As a consequence, we derive several known results, as well as many new results.

1 Introduction

A lattice path of length n is a sequence of points P_{1}, P_{2}, …, P_{n} with n ≥ 1 such that each point P_{i} belongs to the plane integer lattice and consecutive points P_{i} and P_{i+1} are connected by a line segment. We will consider lattice paths in ℤ^{2} whose permitted step types are upsteps u = (1, 1), down-steps d = (1, −1), and horizontal steps h = (1, 0). We will focus on paths that start from the origin and return to the x-axis, and that never pass below the x-axis. Let D_{n} denote the set of such paths, Dyck paths, of length 2n when only up-steps and down-steps are allowed, and let M_{n} denote the set of such paths, Motzkin paths, of length n when all the three types are allowed. It is well known that |D_{n}| = C_{n} = \frac{1}{n+1} \binom{2n}{n}, the n-th Catalan number (see [8, A000108]), having ordinary generating function C(x) = \frac{1−\sqrt{1−4x}}{2x} which satisfies the relation

xC^{2}(x) − C(x) − 1 = 0,  (1)

and |M_{n}| = M_{n}, the n-th Motzkin number (see [8, A001006]), having ordinary generating function M(x) = \frac{1−x−\sqrt{1−2x−3x^{2}}}{2x^{2}} , which satisfies the relation

x^{2}M^{2}(x) + (x − 1)M(x) + 1 = 0.  (2)

Let D be any Dyck path and p be any word on alphabet {u, d}. We say that the Dyck path D occurs p at low level if D can be decomposed as D = D′pR such that D′ is a Dyck path. Otherwise we say that the Dyck path D occurs p at high level.

The enumeration of Dyck paths according to length and various other parameters has been studied by several authors [1]-[7]. However, the statistic “number of udu’s” has been considered only recently [7, 9].

The paper is organized as follows. In Section 2 we consider the statistic “the number of uu ⋯ udu’s” and the statistic “the number of udud ⋯ du’s” in the set of Dyck paths. In Section 3 we consider these statistics at low and high level in the set of Dyck paths.

2 Enumeration of Dyck paths according to number of uu ⋯ udu’s or number of udud ⋯ udu’s

In this section we enumerate the number of Dyck paths according to the length and either the number of uu ⋯ udu’s or the number of udud ⋯ udu’s.

2.1 Enumeration of Dyck paths according to number of uu ⋯ udu’s

Let α_{i}(D) be the number of occurrences of \underbrace{uu ⋯ u}_{i} du in the Dyck path D, see Table 1.

Define the ordinary generating function for the number of Dyck paths of length 2n according to the statistics α_{1}, α_{2}, … as F (x; q_{1}, q_{2}, …) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n} ∏_{j≥1} q_{j}^{α_{j}(D)}. To study the above ordinary generating function we need the following notation

A_{k}(x; q_{1}, q_{2}, …) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n} ∏_{j≥1} q_{j}^{α_{j}^{k}(D)},

where α_{j}^{k}(D) = α_{j} (\underbrace{uu ⋯ u}_{k} D \underbrace{dd ⋯ d}_{k}). These ordinary generating functions satisfy the

following recurrence relations.

n\α_{1} 0 1 2 3 4 5 6 n\α_{2} 0 1 2 3 4 5 6
1  1  1  1
2  1 1  2  2
3  2 2 1  3  4 1
4  4 6 3 1  4  10 3 1
5  9 16 12 4 1  5  26 12 3 1
6  21 45 40 20 5 1  6  72 41 15 3 1
7  51 126 135 80 30 6 1 7  206 143 58 18 3 1

Table 1: Number of Dyck paths of length 2n according to the statistics α_{1} and α_{2}.

Proposition 2.1 For all k ≥ 0,

\begin{aligned}A_{k}(x; q_{1}, q_{2}, …) & = 1 + x(1 − q_{1}q_{2} ⋯ q_{k+1}) − x(1 − q_{1}q_{2} ⋯ q_{k+1})A_{0}(x; q_{1}, q_{2}, …) \\ & +xA_{k+1}(x; q_{1}, q_{2}, …)A_{0}(x; q_{1}, q_{2}, …). \end{aligned}

Proof An equation for the generating function A_{k}(x; q_{1}, q_{2}, …) is obtained from the “first return decomposition” of a Dyck paths D: D = uP dQ, where P, Q are Dyck paths. Thus, the four possibilities of P and Q either being empty or nonempty Dyck paths (see Figure 1) give contribution x, x(A_{k+1}(x; q_{1}, q_{2}, …) − 1), xq_{1}q_{2} ⋯ q_{k+1}(A_{0}(x; q_{1},_{2} , …) − 1), and

P ≠ ∅  Q ≠ ∅  ^{P ≠ ∅  Q ≠ ∅}

Figure 1: First return decomposition of a Dyck path with nonempty Dyck paths.

x(A_{k+1}(x; q_{1}, q_{2}, …) − 1)(A_{0}(x; q_{1}, q_{2}, …) − 1), respectively. Hence, we have the following recurrence relation

\begin{aligned}A_{k}(x; q_{1}, q_{2}, …) & = 1 + x(1 − q_{1}q_{2} ⋯ q_{k+1}) − x(1 − q_{1}q_{2} ⋯ q_{k+1})A_{0}(x; q_{1}, q_{2}, …) \\ & +xA_{k+1}(x; q_{1}, q_{2}, …)A_{0}(x; q_{1}, q_{2}, …), \end{aligned}

for all k ≥ 0, as required. □

Theorem 2.1 The generating function F (x; q_{1}, q_{2}, …) satisfies the following equation

F (x; q_{1}, q_{2}, …) = ∑_{m≥0} x^{m}F^{m}(x; q_{1}, q_{2}, …)(1 + x(1 − F (x; q_{1}, q_{2}, …))(1 − q_{1}q_{2} … q_{m+1})).

Proof We simply use the fact A_{0}(x; q_{1}, q_{2}, …) = F (x; q_{1}, q_{2}, …) and apply (see Proposition 2.1) the recurrence relation

\begin{aligned}A_{k}(x; q_{1}, q_{2}, …) & = 1 + x(1 − q_{1}q_{2} ⋯ q_{k+1})(1 − A_{0}(x; q_{1}, q_{2}, …)) \\ & +xA_{k+1}(x; q_{1}, q_{2}, …)A_{0}(x; q_{1}, q_{2}, …). \end{aligned}

an infinite number of times and in each step we perform some rather tedious algebraic manipulations. □

Example 2.2 Define q_{1} = q, q_{2} = q^{−1}, and q_{i} = 1 for all i ≥ 3. Then Theorem 2.1 gives that the ordinary generating function f(x; q) = F (x; q, q^{−1}, 1, 1, …) satisfies

f(x; q) = \frac{1}{1 − xf(x; q)} + x(1 − f(x; q))(1 − q).

Solving the above equation we get that the ordinary generating function

f(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{α_{1}(D)−α_{2}(D)}

is given by

\frac{1 + x(1 + x)(1 − q) − \sqrt{(x(1 + x)(1 − q) + 1)^{2} − 4x(1 + x(1 − q))^{2}}}{2x(1 + x(1 − q))} .

In particular, the number of Dyck paths D of length 2n such that α_{1}(D) = α_{2}(D) is given by (see [8, A078481])

\frac{1 + x + x^{2} − \sqrt{(1 + x + x^{2})^{2} − 4x(1 + x)^{2}}}{2x(1 + x)} .

Example 2.3 Define q_{2i−1} = q and q_{2i} = q^{−1} for all i ≥ 1. Then Theorem 2.1 gives

F (x; q, 1/q, q, 1/q, …) = 1 + x + xq(F (x; q, 1/q, q, 1/q, …) − 1) + x^{2}F^{3}(x; q, 1/q, q, …).

Then the Lagrange inversion formula (see [10]) gives that

∑_{n≥1} ∑_{D∈D_{n}} x^{n}q^{α_{1}(D)−α_{2}(D)+α_{3}(D)−···} = ∑_{n≥1} ∑_{j=0}^{n} ∑_{i=0}^{j} \binom{n}{j}\binom{i}{j}\binom{3i}{n − 1 + i − j}q^{j−i} \frac{x^{n+i}}{n} .

In particular, the number of Dyck paths D of length 2n with ∑_{i≥0} α_{2i+1}(D) = ∑_{i≥0} α_{2i}(D) is

given by

∑_{j=0}^{n−1} \frac{1}{n − j} \binom{n − j}{j}\binom{3j}{n − 1 − j}.

Example 2.4 Define q_{i} = q for all i ≥ 1. Then Theorem 2.1 gives that

S(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{α_{1}(D)+α_{2}(D)+···} = ∑_{m≥0} x^{m}S^{m}(x; q)(1 + x(1 − S(x; q))(1 − q^{m+1})),

which is equivalent to S(x; q) = 1 + \frac{x}{1−xS(x;q)} − \frac{xq(1−S(x;q))}{1−xqS(x;q)}. Differentiating the above equation with respect to q and substituting q = 1 with using the fact that S(x; 1) = C(x), the generating function for the Catalan numbers, gives that

∑_{n≥0} ∑_{D∈D_{n}}(α_{1}(D) + α_{2}(D) + ⋯)x^{n} = \frac{x^{2}C^{4}(x)}{1 − xC^{2}(x)} = ∑_{n≥2} \binom{2n − 1}{n − 2}x^{2}.

In other words, the statistic ∑_{D∈D_{n}} α_{1}(D) + α_{2}(D) + ⋯ equals \binom{2n−1}{n−2}, for all n ≥ 2 (see [8, A002054]).

Denote the ordinary generating function F (x; q_{1}, q_{2}, …) with q_{k} = q and q_{i} = 1 for all i ≠ k by F_{k}(x; q). Fix k ≥ 1, q_{k} = q and q_{i} = 1 for all i ≠ k. From the definitions it is easy to see that F_{k}(x; q) = F_{k−1}(x; q). Thus, Proposition 2.1 gives that

F_{k−1}(x; q) = 1 + x(1 − q) − x(1 − q)F_{0}(x; q) + xF_{k−1}(x; q)F_{0}(x; q),

and

F_{j+1}(x; q) = \frac{F_{j}(x; q) − 1}{xF_{j}(x; q)},

for all j = 0, 1, …, k − 2. To give an explicit formula for F_{k}(x; q) we need the following lemma.

Lemma 2.1 For all j = 0, 1, …, k − 1,

F_{j}(x; q) = \frac{\sqrt{x}U_{j}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{j−1}(\frac{1}{2\sqrt{x}})}{\sqrt{x} [\sqrt{x}U_{j−1}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{j−2}(\frac{1}{2\sqrt{x}})]},

where U_{j}(t) is the j-th Chebyshev polynomial of the second kind.

Proof We proceed by induction on j. The result is true for j = 0. For j ≥ 0 we have that F_{j+1}(x; q) = \frac{F_{j}(x;q)−1}{xF_{j}(x;q)}. Thus, by the induction hypothesis for j we obtain that the ordinary generating function F_{j+1}(x; q) equals

\frac{\sqrt{x}U_{j}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{j−1}(\frac{1}{2\sqrt{x}}) − \sqrt{x} [\sqrt{x}U_{j−1}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{j−2}(\frac{1}{2\sqrt{x}})]}{x [\sqrt{x}U_{j}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{j−1}(\frac{1}{2\sqrt{x}})]},

which is

\frac{\sqrt{x} [\frac{1}{\sqrt{x}}U_{j}(\frac{1}{2\sqrt{x}}) − U_{j−1}(\frac{1}{2\sqrt{x}})] F_{0}(x; q) − [\frac{1}{\sqrt{x}}U_{j−1}(\frac{1}{2\sqrt{x}}) − U_{j−2}(\frac{1}{2\sqrt{x}})]}{\sqrt{x} [\sqrt{x}U_{j}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{j−1}(\frac{1}{2\sqrt{x}})]}.

Using the recurrence relation U_{m}(t) = 2tU_{m−1}(t) − U_{m−2}(t) twice we get

\frac{\sqrt{x}U_{j+1}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{j}(\frac{1}{2\sqrt{x}})}{\sqrt{x} [\sqrt{x}U_{j}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{j−1}(\frac{1}{2\sqrt{x}})]},

as claimed. □

Now we are ready to give an explicit formula for the ordinary generating function F_{k}(x; q).

Theorem 2.5 Let

α(x; q) = x^{2}(1 − q)U_{k−2}(\frac{1}{2\sqrt{x}}) − x\sqrt{x}U_{k−1}(\frac{1}{2\sqrt{x}}),
β(x; q) = x\sqrt{x}(1 − q) [U_{k−3}(\frac{1}{2\sqrt{x}}) + \sqrt{x}U_{k−2}(\frac{1}{2\sqrt{x}})] − \sqrt{x}U_{k−1}(\frac{1}{2\sqrt{x}}),
γ(x; q) = \sqrt{x}(1 + x(1 − q))U_{k−3}(\frac{1}{2\sqrt{x}}) − U_{k−2}(\frac{1}{2\sqrt{x}}).

Then the ordinary generating function F_{k}(x; q) is given by

\frac{γ(x; q)}{β(x; q)}C (\frac{α(x; q)γ(x; q)}{β^{2}(x; q)}) ,

where U_{j}(t) is the j-th Chebyshev polynomial of the second kind and C(x) is the ordinary generating function for the Catalan numbers.

Proof The generating function F_{0}(x; q) satisfies the following equation

F_{k−1}(x; q) = 1 + x(1 − q) − x(1 − q)F_{0}(x; q) + xF_{k−1}(x; q)F_{0}(x; q).

Using Lemma 2.1 for j = k − 1 we get

F_{k−1}(x; q) = \frac{\sqrt{x}U_{k−1}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{k−2}(\frac{1}{2\sqrt{x}})}{\sqrt{x} [\sqrt{x}U_{k−2}(\frac{1}{2\sqrt{x}})F_{0}(x; q) − U_{k−3}(\frac{1}{2\sqrt{x}})]}.

Substituting the expression for F_{k−1}(x; q) in the above equation and using the recurrence relation U_{m}(t) = 2tU_{m−1}(t) − U_{m−2}(t) we obtain

α(x; q)F_{0}^{2}(x; q) − β(x; q)F_{0}(x; q) + γ(x; q) = 0.

Hence, by solving the above equation we get the desired result. □

For example, Theorem 2.5 for k = 1 gives F_{1}(x; q) = C (\frac{x}{1+x(1−q)}) (see [9, Equations 2.2 and 2.3]). In particular, F_{1}(x; 0) = C(x/(1 + x)). This result can be generalized by using Theorem 2.5 with q = 0.

Corollary 2.1 The ordinary generating function for the number of Dyck paths of length 2n that avoid \underbrace{uu ⋯ u}_{k} du is given by

\frac{U_{k}(\frac{1}{2\sqrt{x}}) + \sqrt{x}U_{k−1}(\frac{1}{2\sqrt{x}})}{(1 + x)U_{k}(\frac{1}{2\sqrt{x}})}C (\frac{xU_{k}(\frac{1}{2\sqrt{x}}) + x\sqrt{x}U_{k−1}(\frac{1}{2\sqrt{x}})}{(1 + x)^{2}U_{k}(\frac{1}{2\sqrt{x}})}) ,

where U_{j}(t) is the j-th Chebyshev polynomial of the second kind and C(x) is the ordinary generating function for the Catalan numbers.

For instance, the ordinary generating function for the number of Dyck paths of length 2n that avoid uudu is given by \frac{1}{1−x^{2}} C (\frac{x}{(1−x)(1+x)^{2}} ) (see [8, A105633]).

2.2 Enumeration of Dyck paths according to number of ud ⋯ udu’s

Let β_{i}(D) be the number of occurrences of \underbrace{udud ⋯ ud}_{i} u in the Dyck path D, see Table 2. Clearly, β_{1}(D) = α_{1}(D). Define the ordinary generating function for the number of Dyck

n\β_{2} 0 1 2 3 4 5 6
1  1
2  2
3  4 1
4  11 2 1
5  31 8 2 1
6  92 28 9 2 1
7  283 99 34 10 2 1

Table 2: Number of Dyck paths of length 2n according the statistic β_{2}.

paths of length 2n according to the statistics β_{1}, β_{2}, … as

G(x; q_{1}, q_{2}, …) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n} ∏_{j≥1} q_{j}^{β_{j}(D)}.

To study the above ordinary generating function we need the following notation

B_{k}(x; q_{1}, q_{2}, …) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n} ∏_{j≥1} q_{j}^{β_{j}^{k}(D)},

where β_{j}^{k}(D) = β_{j} (\underbrace{ud ⋯ ud}_{k} D). These ordinary generating functions satisfy the following recurrence relations. Proposition 2.2 For all k ≥ 0,

\begin{matrix}B_{k}(x; q_{1}, q_{2}, …) = ∏_{i=1}^{k} q_{i}^{k−i} + x ∏_{i=1}^{k+1} q_{i}^{k+1−i}(B_{0}(x; q_{1}, q_{2}, …) − 1)B_{0}(x; q_{1}, q_{2}, …) \\ +xB_{k+1}(x; q_{1}, q_{2}, …). \end{matrix}

Proof An equation for the generating function B_{k}(x; q_{1}, q_{2}, …) is obtained from the “first return decomposition” of a Dyck paths D: D = uP dQ, where P and Q are Dyck paths. Then each Dyck path D that starts with \underbrace{udud … ud}_{k} can be decomposed as either D = \underbrace{udud … ud}_{k}, D = \underbrace{udud … ud}_{k} uP dQ with P a nonempty Dyck path, or D = \underbrace{udud … ud}_{k+1} Q (see Figure 2 for k = 2). Thus, the ordinary generating function B_{k}(x; q_{1}, q_{2}, …) is given by

P ≠ ∅  Q  Q

Figure 2: First return decomposition of a Dyck path according the statistic ududu.

∏_{i=1}^{k} q_{i}^{k−i} + x ∏_{i=1}^{k+1} q_{i}^{k+1−i}(B_{0}(x; q_{1}, q_{2}, …) − 1)B_{0}(x; q_{1}, q_{2}, …) + xB_{k+1}(x; q_{1}, q_{2}, …),

for all k ≥ 0, as required. □

Theorem 2.6 The generating function G(x; q_{1}, q_{2}, …) is given by

G(x; q_{1}, q_{2}, …) = C (\frac{x ∑_{m≥0} x^{m} ∏_{i=1}^{m+1} q_{i}^{m+1−i}}{1 + x ∑_{m≥0} x^{m} ∏_{i=1}^{m+1} q_{i}^{m+1−i}} ) ,

where C(x) is the generating function for the Catalan numbers.

Proof We simply use the fact that B_{0}(x; q_{1}, q_{2}, …) = G(x; q_{1}, q_{2}, …) and apply the recurrence relation

\begin{aligned}B_{k}(x; q_{1}, q_{2}, …) & = ∏_{i=1}^{k} q_{i}^{k−i} + x ∏_{i=1}^{k+1} q_{i}^{k+1−i}(B_{0}(x; q_{1}, q_{2}, …) − 1)B_{0}(x; q_{1}, q_{2}, …) \\ & +xB_{k+1}(x; q_{1}, q_{2}, …) \end{aligned}

an infinite number of times and in each step we perform some rather tedious algebraic manipulations. □

Example 2.7 Let q_{2i−1} = q and q_{2i} = q^{−1} for all i ≥ 1. Then Theorem 2.6 gives that

∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{β_{1}(D)−β_{2}(D)+···} = C (\frac{x(1 + xq)}{1 + x})

which is equivalent to

∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{β_{1}(D)−β_{2}(D)+···} = 1 + ∑_{n≥1} x^{n} ∑_{i=0}^{n+1} ∑_{j=0}^{i+1} C_{i}\binom{i + 1}{j}\binom{n − 1 − j}{i}q^{j}.

In particular, the ordinary generating function for the number of Dyck paths D of length 2n with

∑_{i≥1} β_{2i−1}(D) = ∑_{i≥1} β_{2i}(D)  (3)

is given by C(x/(1 + x)) = M(x), that is, the number of Dyck paths D of length 2n with (3) is given by M_{n}, the n-th Mozkin number.

Example 2.8 Let q_{i} = q for all i ≥ 1. Then, similar to Example 2.4, we obtain from Theorem 2.6 that

∑_{D∈D_{n}}(β_{1}(D) + β_{2}(D) + ⋯) = ∑_{j=0}^{n−2} \binom{2j + 2}{j},

for all n ≥ 2.

Denote the ordinary generating function G(x; q_{1}, q_{2}, …) with q_{k} = q and q_{i} = 1 for all i ≠ k by G_{k}(x; q). For example, if q_{1} = q and q_{i} = 1, i = 2, 3, …, then Theorem 2.6 gives G_{1}(x; q) = C (\frac{x}{1+x(1−q)}) (see [9, Equations 2.2 and 2.3]). In general, if q_{k} = q and q_{i} = 1 for all i ≠ k, then Theorem 2.5 gives an explicit formula for the ordinary generating function G_{k}(x; q).

Corollary 2.2 The ordinary generating function for the Dyck paths of length 2n according to the statistic β_{k} is given by

G_{k}(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{β_{k}} = C (\frac{x(1 − xq − x^{k}(1 − q))}{1 − xq − x^{k+1}(1 − q)}) ,

where C(x) is the generating function for the Catalan numbers.

For instance, Corollary 2.2 for k = 2 and q = 0 gives that the ordinary generating function for the number of Dyck paths of length 2n that avoid UDUDU is given by

C (\frac{x(1 − x^{2})}{1 − x^{3}}) = 1 + ∑_{n≥1} x^{n} (∑_{i=1}^{n} ∑_{j=0}^{(n−m)/2}(−1)^{\frac{n−m+j}{3}} \binom{m}{j}\binom{\frac{n+2m−2j}{3} − 1}{m − 1}C_{m}) .

3 Enumeration of Dyck paths according to number of uu … udu’s or number of udud … udu’s at low and high levels

In this section we consider the following statistics on Dyck paths: number of low (high) level uu … udu’s or number of low (high) level udud … udu’s (for the case k = 1, see [9, Section 3]).

3.1 Enumeration of Dyck paths according to number of uu … udu’s at low and high levels

Let γ_{k} (resp. γ′_{k}) be the number of occurrences of \underbrace{uu … u}_{k} du at low (resp. high) level. Denote

the ordinary generating function for the number of Dyck paths of length 2n according to the statistics γ_{k} (resp. γ′_{k}) by

L_{k}(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{γ_{k}(D)} (resp. H_{k}(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{γ′_{k}(D)}) .

Theorem 3.1 Let k ≥ 2. Then the number of Dyck paths of length 2n with γ_{k} = m is given by

∑_{j≥0}(−1)^{j} \frac{(m + j)(k + 1) + 1}{2n + 1 − (m + j)(k + 1)}\binom{m + j}{j}\binom{2n + 1 − (m + j)(k + 1)}{n + 1}.

Proof Consider any Dyck path D = uP dQ, where P and Q are Dyck paths. So D contains a_{k} := \underbrace{uu … u}_{k} du if either P starts with a_{k−1} or Q contains a_{k} (see Figure 3). Thus,

P  Q

Figure 3: First return decomposition of a Dyck path.

L_{k}(x; q) = 1 + xt_{1}(x; q)L_{k}(x; q), where t_{j}(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{γ_{k}(\underbrace{uu … u}_{j} D \underbrace{dd … d}_{j})} for all j = 1, 2, … k − 1. Again, using the first return decomposition of a Dyck path we obtain that the ordinary generating function t_{j}(x; q) equals 1 + xt_{j+1}(x; q)C(x), where C(x) is the ordinary generating function for the Catalan numbers and j = 1, 2, …, k − 2. In addition, t_{k−1}(x; q) = 1 + x + xC(x)(C(x) − 1) + xq(C(x) − 1). Therefore, it is easy to check that

t_{1}(x; q) = (xC(x))^{k−2}t_{k−1}(x; q) + ∑_{j=0}^{k−3}(xC(x))^{j}.

This implies that the ordinary generating function L_{k}(x; q) is given by

L_{k}(x; q) = \frac{1}{1 − x (\frac{1−(xC(x))^{k−2}}{1−xC(x)} + (xC(x))^{k−2}t_{1}(x; q)))}.

By using the identity C(x) = \frac{1}{1−xC(x)} (see (1)) we arrive at

L_{k}(x; q) = \frac{C(x)}{1 + (1 − q)(xC(x))^{k+1}} = ∑_{m≥0} \frac{x^{m(k+1)}C^{m(k+1)+1}(x)}{(1 + (xC(x))^{k+1})^{m+1}} ,

which is equivalent to

L_{k}(x; q) = ∑_{m≥0} ∑_{j≥0}(−1)^{j}\binom{m + j}{j}x^{(m+j)(k+1)}C^{(m+j)(k+1)+1}(x).

On other hand, by applying the Lagrange inversion formula in [10], we get that

C^{k}(x) = ∑_{n≥0} \frac{k}{2n + k} \binom{2n + k}{n}x^{n}.

Hence, the x^{n}q^{m} coefficient in the ordinary generating function L_{k}(x; q) is given by

∑_{j≥0}(−1)^{j} \frac{(m + j)(k + 1) + 1}{2n + 1 − (m + j)(k + 1)}\binom{m + j}{j}\binom{2n + 1 − (m + j)(k + 1)}{n + 1},

as required. □ For example, Theorem 3.1 for k = 2 (for the case k = 1 see [9,

Theorem 3.1]) gives that the number of Dyck paths of length 2n having γ_{2} = m is given by

∑_{j≥0}(−1)^{j} \frac{3(m + j) + 1}{2n + 1 − 3(m + j)}\binom{m + j}{j}\binom{2n + 1 − 3(m + j)}{n + 1}.

Theorem 3.2 The ordinary generating function for the number of Dyck paths of length 2n according to the statistic γ′_{k} is given by

H_{k}(x; q) = \frac{1}{1 − x\frac{1 − x^{k}(1 − q)F_{k}^{k−1}(x; q)(F_{k}(x; q) − 1)}{1 − xF_{k}(x; q)}} ,

where the explicit formula for the ordinary generating function F_{k}(x; q) is given by Theorem 2.5.

Proof Again (see Theorem 3.1), by using the first return decomposition of a Dyck path D (D = uP dQ where P and Q are Dyck paths, see Figure 3), we obtain that the ordinary generating function H_{k}(x; q) satisfies H_{k}(x; q) = 1 + xt_{1}(x; q)H_{k}(x; q), where t_{j}(x; q) satisfies the recurrence relation t_{j}(x; q) = 1 + xt_{j+1}(x; q)F_{k}(x; q), for j = 1, 2, … k, and t_{k}(x; q) = 1 + x + x(t_{k}(x; q) − 1)F_{k}(x; q) + xq(F_{k}(x; q) − 1). Solving the above system of equations we get the desired result. □

Theorems 3.1 and 3.2 give the following result. For γ′_{1} = 0, we obtain that the number of Dyck paths of length 2n is given by the n-th Motzkin number (see [9, Equation 3.6]). For γ′_{2} = 0, we obtain that the ordinary generating function for the number of Dyck paths of length 2n is given by

\frac{2x^{3} + x^{2} − 5x + 3 − (2x + 1)\sqrt{x^{4} − 2x^{3} − 5x^{2} − 2x + 1}}{2(x^{5} + x^{4} + 4x^{3} + 5x^{2} − 4x + 1)}.

3.2 Enumeration of Dyck paths according to number of ud … udu’s at low and high levels

Let δ_{k} (resp. δ′_{k}) be the number of occurrences of \underbrace{udud … ud}_{k} u at low (resp. high) level.

Denote the ordinary generating function for the number of Dyck paths of length 2n according to the statistics δ_{k} (resp. δ′_{k}) by

L′_{k}(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{δ_{k}(D)} (resp. H′_{k}(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{δ′_{k}(D)}) .

Using the same techniques as in the previous subsection we obtain the following results.

Theorem 3.3 Let k ≥ 1. Then the ordinary generating function for the number of Dyck paths of length 2n according to the statistic δ_{k} is given by

L′_{k}(x; q) = \frac{1 − x^{k+1} − xq(1 − x^{k})}{1 − x^{k+1} − x(1 − x^{k})C(x) − xq(1 − x^{k} − x(1 − x^{k−1})C(x))}.

Moreover, the ordinary generating function for the number of Dyck paths of length 2n with δ_{k} = m is

\frac{x^{m+k}(1 − x)^{2}C(x)(1 − x^{k} − x(1 − x^{k−1})C(x))^{m−1}}{(1 − x^{k+1} − x(1 − x^{k})C(x))^{m+1}}

when m ≥ 1, and \frac{1−x^{k+1}}{1−x^{k+1}−x(1−x^{k})C(x)} when m = 0.

For example, the number of Dyck paths of length 2n having δ_{1} = 0 is given by \frac{1+x}{1+x−xC(x)} (see [9, Page 5]), and having δ_{2} = 0 is given by \frac{1+x+x^{2}}{1+x+x^{2}−x(1+x)C(x)}.

To enumerate the number of Dyck paths of length 2n according to the statistic δ′_{k} we use the first return decomposition of a Dyck path and Corollary 2.2. Thus we obtain the following result.

Theorem 3.4 Let k ≥ 1. Then the ordinary generating function for the number of Dyck paths of length 2n according to the statistic δ′_{k} is given by

H′_{k}(x; q) = \frac{1}{1 − xG_{k}(x; q)},

where

G_{k}(x; q) = ∑_{n≥0} ∑_{D∈D_{n}} x^{n}q^{β_{k}} = C (\frac{x(1 − xq − x^{k}(1 − q))}{1 − xq − x^{k+1}(1 − q)}) .

For example, the ordinary generating function for the number of Dyck paths of length 2n having δ′_{1} = 0 is given by M(x) (see [9, Equation 3.6]).

References

[1] E. Deutsch, Dyck path enumeration, Discr. Math. 204 (1999), 167–202.

[2] G. Kreweras, Joint distribution of three descriptive parameters of bridges, Combinatoire Énumérative, Proc. (Montréal, Que., 1985/Québec, Que., 1985), Lec. Notes in Math. 1234 (1986), 177–191.

[3] G. Kreweras and P. Moszkowski, A new enumerative property of the Narayana numbers, J. Statist. Plann. and Infer. 14 (1986), 63–67.

[4] G. Kreweras and Y. Poupard, Subdivision des nombres de Narayana suivant deux paramétres supplémentaires, Europ. J. Combin. 7 (1986), 141–149.

[5] T. Mansour, Counting peaks at height k in a Dyck path, Journal of Integer Sequences 5 (2002), Article 02.1.1.

[6] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math. 49:2 (1997), 301–320.

[7] D. Merlini, R. Sprugnoli, and M. C. Verri, Some statistics on Dyck paths, J. Statist. Plann. and Infer. 101 (2002), 211–227.

[8] N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New York (1995).

[9] Y. Sun, The statistic “number of udu’s” in Dyck paths, Discr. Math. 287 (2004), 177– 186.

[10] H. Wilf, Generatingfunctionology, Academic Press, New York, 1990.

2000 Mathematics Subject Classification: 05A05, 05A15, 42C05.

Keywords: Chebyshev polynomials, Dyck paths, Generating functions.

(Concerned with sequences \underline{A000108}, \underline{A001006}, \underline{A002054}, \underline{A078481}, and \underline{A105633}.)

Received October 2 2005; revised version received January 16 2006. Published in Journal of Integer Sequences, January 17 2006.

Return to Journal of Integer Sequences home page.