A Natural Extension of Catalan Numbers

Noam Solomon and Shay Solomon^{1} Dept. of Mathematics and Computer Science Ben-Gurion University of the Negev Beer-Sheva 84105 Israel

                      noams@cs.bgu.ac.il
                      shayso@cs.bgu.ac.il

Abstract A Dyck path is a lattice path in the plane integer lattice ℤ × ℤ consisting of steps (1, 1) and (1, −1), each connecting diagonal lattice points, which never passes below the x-axis. The number of all Dyck paths that start at (0, 0) and finish at (2n, 0) is also known as the nth Catalan number. In this paper we find a closed formula, depending on a non-negative integer t and on two lattice points p_{1} and p_{2}, for the number of Dyck paths starting at p_{1}, ending at p_{2}, and touching the x-axis exactly t times. Moreover, we provide explicit expressions for the corresponding generating function and bivariate generating function.

1 Introduction

The Catalan sequence is the sequence {C_{n}}_{n≥0} = {1, 1, 2, 5, 14, 42, 132, 429, …}, where C_{n} = \frac{1}{n+1} \binom{2n}{n} is called the nth Catalan number. It is sequence \underline{A000108} in Sloane’s Encyclopedia of Integer Sequences. The generating function for the Catalan numbers is given by C(x) = \frac{1−\sqrt{1−4x}}{2x}. The Catalan numbers provide a complete answer to the problem of counting certain properties of more than 165 different combinatorial structures (see [21, p. 219] and [20]). For convenience, the generalization of Catalan numbers presented in this paper is translated in terms of Dyck paths.

A Dyck path is a lattice path in the integer lattice ℤ×ℤ consisting of rise-steps (1, 1) and fall-steps (1, −1) that connect diagonal lattice points, which never goes below the x-axis. (See Figure 1 for an illustration.) Let D((i, j), (i′, j′)) denote the set of all Dyck paths that start at (i, j) and finish at (i′, j′). The number of steps in any such Dyck path equals i′ − i. Notice that |D((i, j), (i′, j′))| = 0 iff at least one of the following conditions holds:

1Corresponding author. Tel: +972-8-642-8087; Fax: +972-8-647-7650.

Figure 1: (a) A Dyck path of length 12 from (0, 0) to (12, 0), having exactly two contact points–the starting point and the finishing point. (b) A Dyck path of length 11 from (1, 1) to (12, 2), having no contact points.

• i > i′.

• j′ − j > i′ − i.

• j′ − j ≠ i′ − i (mod 2).

• j′ < 0 or j < 0.

Otherwise, as a corollary of the Ballot theorem (cf. [10, p. 73]), we get that

|D((i, j), (i′, j′))| = \binom{i′ − i}{\frac{i′−i+|j′−j|}{2}} − \binom{i′ − i}{\frac{i′−i+j′+j+2}{2}}.  (1)

The number of Dyck paths that start at (0, 0) and finish at (2n, 0) is also known as the nth Catalan number C_{n}.

There is an extensive literature on Dyck paths, often disguised by means of similar combinatorial objects as Catalan numbers, Motzkin paths, Schröder paths, staircase walks, Ballot-numbers, and more. We mention here but a limited number of examples of previous work.

The notion of a peak on a Dyck path was introduced by Deutsch in [7], where it is shown that the number of Dyck paths of length 2n starting and ending on the x-axis with no peaks at height 1 is given by the nth Fine number F_{n}, {F_{n}}_{n≥0} = {1, 0, 1, 2, 6, 18, 57, …}. In [19], a complete answer for the number of Dyck paths in D((0, 0), (2n, 0)) with no peaks at height k is given. Further, an explicit expression for the generating function for the number of Dyck paths in D((0, 0), (2n, 0)) with exactly r peaks at height k is provided [15].

Connections between Dyck paths and pattern-avoiding permutations have been a subject of ongoing research. Among various works in this context is the work of Knuth [13], where it is shown that S_{n}(312) satisfy the Catalan recurrence, and the works of Bandlow and Killpatrick [2], Krattenthaler [14], and Mansour et al. [16], where bijections between Dyck paths and permutations that avoid certain patterns of size three are presented.

The close relationship between lattice paths and queueing theory models has been extensively studied. The seminal papers by Mohanty [17] and Flajolet and Guillemin [11] offer lattice path perspectives for the Karlin-McGregor theory of birth-death processes, which is closely related to various queueing theory models. The book by Fayolle et al. on random walks in the plane integer lattice [9] is historically motivated by such queueing theory questions [8]. In [18], a combinatorial technique based on lattice path counting is applied to derive the transient solution of the M/M/c queueing model, and in [3] this result is extended to (almost) arbitrary birth-death processes. In [1], equilibrium probability distributions of the queue length in the M/M/1, M/E_{k}/1 and E_{l}/E_{k}/1 queueing models are presented, based on the generating function for the number of minimal lattice paths. In [6], service times of customers in the M/M/1 queueing model are analyzed, and it is shown that a family of polynomial generating sequence associated with Dyck paths of length 2n provide the correlation function of the successive services in a busy period with n + 1 customers.

Brak and Essam [4] considered the case of k ≥ 1 non-intersecting Dyck paths that start and finish on the x-axis. For the particular case of k = 1, the contact polynomial defined as P_{n}(x) := ∑_{t=2}^{n+1} |D_{t}((0, 0), (2n, 0))|x^{t} is proved^{2} to satisfy P_{n}(C(x)) = ∑_{ℓ=0}^{∞} C_{n+ℓ}x^{ℓ}. Via a bijection between bi-colored Dyck paths and plain Dyck paths, the analogue of the Chu-Vandemonde summation formula for Dyck paths is derived.

In this paper we study “generalized” Dyck paths, starting and ending at arbitrary points in the non-negative half-plane, “touching” the x-axis any predetermined number of times, and never passing below the x-axis. We say that a Dyck path P touches the x-axis t times, if exactly t points on P have zero as their y coordinate. Following [4], any point of P that intersects the x-axis is called a contact. Denote the set of all Dyck paths starting at (i, j), ending at (i′, j′), and touching the x-axis exactly t times by D_{t}((i, j), (i′, j′)). We have D((i, j), (i′, j′)) = ⋃_{t∈ℕ} D_{t}((i, j), (i′, j′)). Notice that

|D_{0}((0, 1), (2n, 1))| = |D((0, 0), (2n, 0))| = C_{n}.

More generally, we have |D_{0}((i, j), (i′, j′))| = |D((i, j − 1), (i′, j′ − 1))|. In the sequel, we henceforth concentrate on Dyck paths that touch the x-axis at least once.

1.1 Main Results

Our main contribution is the following theorem, for which we provide a simple combinatorial proof.

Theorem 1. For any pair of lattice points (i, j) and (i′, j′), and for any integer t ≥ 1,

|D_{t}((i, j), (i′, j′))| = \{ \begin{matrix}0, & if j < 0 or j′ < 0; \\ |D((i, j + t − 2), (i′ − t, 0))|, & if j′ = 0; \\ |D((i, j + t − 1), (i′ − t, j′ − 1))|− \\ |D((i, j + t − 2), (i′ − t, j′ − 2))|, & if j′ > 0. \end{matrix}

In the degenerate case t + |j| + |j′| + |i′ − i| = 1, |D_{t}((i, j), (i′, j′))| = 1.

We also find an explicit expression for the corresponding generating function.

2In [4], a combinatorial proof for P_{n}(C(x)) = ∑_{ℓ=0}^{∞} C_{n+ℓ}x^{ℓ} is provided. However, this result had already been proved analytically in an earlier work [5].

Theorem 2. For any non-negative integers j, j′ and t, with t ≥ 1,

D_{t}^{j,j′}(x) := ∑_{n≥0} d_{t}^{j,j′}(n)x^{n} = \frac{(1 − \sqrt{1 − 4x^{2}})^{t+j+j′−1}}{2^{(t+j+j′−1)} · x^{(j+j′)}} ,

where D_{t}^{j,j′}(x) is the generating function of the sequence d_{t}^{j,j′}(n) := |D_{t}((0, j), (n, j′))|.

We derive the bivariate generating function as an easy consequence of Theorem 2.

Corollary 3. For any non-negative integers j and j′,

Φ^{j,j′}(x, y) := ∑_{t≥1,n≥0} d_{j,j′}(n, t)x^{n}y^{t} = \frac{y(1 − \sqrt{1 − 4x^{2}})^{j+j′}}{2^{(j+j′−1)}x^{(j+j′)}(y · \sqrt{1 − 4x^{2}} + 2 − y)},

where Φ^{j,j′}(x, y) is the bivariate generating function of the sequence d_{j,j′}(n, t) := |D_{t}((0, j), (n, j′))|.

1.2 Minor Results

• By Theorem 1 and (1), we determine the coefficients of the contact polynomial, as follows:

P_{n}(x) := ∑_{t=2}^{n+1} |D_{t}((0, 0), (2n, 0))|x^{t} = ∑_{t=2}^{n+1} |D((0, 0), (2n − t, t − 2))|x^{t}

= ∑_{t=2}^{n+1} [\binom{2n − t}{n − 1} − \binom{2n − t}{n}] x^{t} = ∑_{t=2}^{n+1} \frac{t − 1}{n − t + 1}\binom{2n − t}{n}x^{t}.

• The following formula, which is the analogue of the Chu-Vandemonde summation formula for Dyck paths, was proved in [4]:

\frac{1}{n + b + 1}\binom{2n + 2b}{n + b} = ∑_{m=1}^{n} \frac{m}{n}\binom{2n − m − 1}{n − 1}\frac{m + 1}{b + m + 1}\binom{2b + m}{b}, ∀b ≥ 0, n ≥ 1

(2)

In Section 4, we provide a simple proof for (2) using different techniques that involve our new knowledge on the contact polynomial and an interesting identity from [5].

1.3 Notation and Basic Facts

Consider some infinite sequence {s_{n}}_{n≥0} := {s_{0}, s_{1}, s_{2}, …}. It is common to denote the nth element s_{n} also as s(n) and the entire sequence {s_{n}}_{n≥0} also as s. For n < 0, define s_{n} := 0. For any integer m, define s[m] as the sequence {s_{m}, s_{m+1}, …}, namely, s[m]_{n} = s_{n+m} if n ≥ 0, and 0 otherwise. We define H(s) as the sequence \{s_{0}, 0, s_{1}, 0, s_{2}, 0 …\}, namely, H(s)_{n} = s\frac{n}{2} if n is even, and 0 otherwise. We define s^{k} to be the result of applying k convolutions of s with itself, that is, s^{k} := s ∗ s … ∗ s.

Fact 1. For any sequences of non-negative integers s and t with generating functions S(x) and T (x), respectively, we have

• The generating function of their convolution s ∗ t is S(x) · T (x).

• The generating function of s[m] is^{3} S(x) · x^{−m}.

• The generating function of H(s) is S(x^{2}).

• The generating function of s^{k} is S(x)^{k}.

We will use the following observation in the sequel (often implicitly):

Observation 1. For any integers i, i′, j, j′ and t, with t ≥ 1, there are natural bijections between

• D_{t}((i, j), (i′, j′)) and D_{t}((0, j), (i′ − i, j′)).

• D_{t}((i, j), (i′, j′)) and D_{t}((i, j′), (i′, j)).

2 Proof of Theorem 1

This section is organized as follows. We start with an investigation of Dyck paths that touch the x-axis exactly once (Section 2.1). Then, we show that there is a bijection between the set of Dyck paths that touch the x-axis any predetermined number of times and the set of Dyck paths that touch it just once (Section 2.2). Equipped with appropriate tools, we conclude with a simple proof of Theorem 1 (Section 2.3).

Remark 4. Observe that there is a natural bijection between

D_{t}((i, j), (i′, 0))

and

D_{t−1}((i, j), (i′ − 1, 1)),

implying that the case j′ = 0 of Theorem 1 may be deduced directly from the case j′ > 0. Nevertheless, we provide an alternative proof for the case j′ = 0, independent of the case j′ > 0.

2.1 Touching the x-Axis Just Once

In this section we restrict our attention to Dyck paths that touch the x-axis once.

Lemma 5. For any integers i, j and i′, such that j > 0,

|D_{1}((i, j), (i′, 0))| = |D((i, j − 1), (i′ − 1, 0))|.

3In the sequel, whenever a shifted sequence s[m] with a positive integer m is used, S(x) will always be divisible by x^{m}. Thus the notation S(x) · x^{−m} is unambiguous .

P  f(P)

Figure 2: The Dyck path P on the left is in D_{1}((0, 1), (9, 2)), having (1, 0) as a unique contact point. The Dyck path f(P) on the right is in D_{3}((0, 1), (8, 1)), having in addition to (1, 0) also (3, 0) and (5, 0) as contact points.

Proof. For any Dyck path P in D_{1}((i, j), (i′, 0)), its last move is a fall-step, connecting (i′ − 1, 1) and (i′, 0). Omitting this last move from P yields a Dyck path of length i′ − 1 that finishes at (i′ − 1, 1), never passing below y = 1. This naturally induces a bijection between D_{1}((i, j), (i′, 0)) and D_{0}((i, j), (i′ − 1, 1)). The proof is concluded by observing that |D_{0}((i, j), (i′ − 1, 1))| = |D((i, j − 1), (i′ − 1, 0))|.

Lemma 6. For any integers i, j, i′ and j′, such that j ≥ 0 and j′ > 0,

|D_{1}((i, j), (i′, j′))| = |D((i, j), (i′ − 1, j′ − 1))| − |D((i, j − 1), (i′ − 1, j′ − 2))|.

Proof. We first claim that there is a bijection between

D_{1}((i, j), (i′, j′))

and

S := ⋃_{k>0} D_{k}((i, j), (i′ − 1, j′ − 1)).

To see this, consider the following map f, taking a Dyck path P in D_{1}((i, j), (i′, j′)) and sending it to the one obtained from it by omitting the step which occurs immediately after reaching the contact point. (See Figure 2 for an illustration.) Clearly, f(P) touches the x-axis at least once, starts at (i, j), and finishes at (i′−1, j′−1); that is, f(P) ∈ ⋃_{k>0} D_{k}((i, j), (i′− 1, j′ − 1)). It is easy to verify that f is bijective, as required.

Observe that

S = D((i, j), (i′ − 1, j′ − 1)) \ D_{0}((i, j), (i′ − 1, j′ − 1))

and

|D_{0}((i, j), (i′ − 1, j′ − 1))| = |D((i, j − 1), (i′ − 1, j′ − 2))|,

and we are done.

2.2 The General Case

We use the next statement in the special case ℓ = t − 1 for proving Theorem 1.

P′ f(P) P  ^{p_{2}}  ^{p_{3}}  ^{p_{4}}^{p_{1}}^{y = −3}

Figure 3: The Dyck path P at the top is in D_{4}((0, 1), (13, 2)), and has four contact points: p_{1} = (3, 0), p_{2} = (5, 0), p_{3} = (7, 0) and p_{4} = (11, 0). The path P′ at the middle part of the figure is a diagonal lattice path of length 10 from (0, 1) to (10, −1), obtained from P by omitting the three rise-steps U_{1}, U_{2} and U_{3}. The Dyck path f(P) at the bottom is in D_{1}((0, 4), (10, 2)), having one contact point–(8, 0).

Proposition 7. For any integers i, j, i′, j′, ℓ, such that j, j′ ≥ 0, t ≥ 1 and 0 ≤ ℓ ≤ t − 1, there is a bijection between D_{t}((i, j), (i′, j′)) and D_{t−ℓ}((i, j + ℓ), (i′ − ℓ, j′)).

Proof. We construct a bijection f : D_{t}((i, j), (i′, j′)) → D_{t−ℓ}((i, j + ℓ), (i′ − ℓ, j′)). Let P be some path in D_{t}((i, j), (i′, j′)). Denote the t contact points of P, from left to right, by p_{1}, …, p_{t}, and let U_{i} be the step in P which occurs immediately after reaching p_{i}, for each 1 ≤ i ≤ ℓ. As P does not pass below the x-axis, the U_{i}’s are all rise-steps. Consider the Dyck path P′ obtained from P by omitting these ℓ rise-steps and define f(P) as the one obtained from it by a shift of all the points in it, ℓ units up. (See Figure 3 for an illustration in the case ℓ = t − 1.)

Observe that f(P) starts at (i, j + ℓ), finishes at (i′ − ℓ, j′), touches the x-axis exactly t − ℓ times, and never passes below the x-axis. Hence, f(P) ∈ D_{t−ℓ}((i, j + ℓ), (i′ − ℓ, j′)). To show that f is bijective, we construct its inverse. Take some Dyck path Q in D_{t−ℓ}((i, j + ℓ), (i′ − ℓ, j′)). Let Q′ be the Dyck path obtained from Q by a shift of all points in it, ℓ units down. Let q_{1} be the left-most point in Q′ that touches the x-axis and define q_{i} as the left-most point in Q′ with y-coordinate 1 − i, for each 2 ≤ i ≤ ℓ. We define f^{−1}(Q) to be the Dyck path obtained from Q′ by inserting a rise-step U_{i} immediately after reaching q_{i}, for each 1 ≤ i ≤ ℓ. It is easy to verify that f^{−1}(Q) ∈ D_{t}((i, j), (i′, j′)) and f(f^{−1}(Q)) = Q. The proposition follows.

2.3 Proof of Theorem 1

Suppose first that t + |j| + |j′| + |i′ − i| > 1. The result is immediate if either j < 0 or j′ < 0. We henceforth assume that j, j′ ≥ 0. Setting ℓ = t − 1 in Proposition 7, we find that

|D_{t}((i, j), (i′, j′)| = |D_{1}((i, j + t − 1), (i′ − t + 1, j′)|.

We distinguish the two following cases:

Case 1: j′ = 0. We need to show that

|D_{1}((i, j + t − 1), (i′ − t + 1, 0))| = |D((i, j + t − 2), (i′ − t, 0))|.

If j + t − 1 > 0, then this equation follows from Lemma 5. Otherwise t = 1, j = j′ = 0, and so, |i′ − i| > 0. It is easy to verify that both hand sides of the equation vanish in the latter case.

Case 2: j′ > 0. By Lemma 6, we have

|D_{1}((i, j+t−1), (i′−t+1, j′))| = |D((i, j+t−1), (i′−t, j′−1))|−|D((i, j+t−2), (i′−t, j′−2))|.

In the degenerate case t+|j|+|j′|+|i′ −i| = 1, we have t = 1, j = j′ = 0, and i′ = i. The result in this case follows from the fact that D_{1}((i, 0), (i, 0)) is comprised of a single Dyck path of length zero that starts and finishes at (i, 0).

3 Proof of Theorem 2

Define ϕ(n, k) := |D_{k+2}((0, 0), (n, 0))|, for any non-negative integers n and k, and let a_{n} := ϕ(n, 0). It is easy to verify that for odd values of n, a_{n} = 0, whereas for even values of n, a_{n} = c_{\frac{n}{2} −1}, except for n = 0, where a_{0} = 0. Equivalently, we have a_{n} = H(C[−1])_{n}. Thus, the generating function for the sequence a is given by A(x) = \frac{1−\sqrt{1−4x^{2}}}{2} .

We use Lemmas 8 and 9 to prove Theorem 2.

Lemma 8. For any non-negative integers n and k, ϕ(n, k) = a^{k+1}(n).

Proof. We construct a bijection

g : D_{k+2}((0, 0), (n, 0)) → ⨁ ; {1≤n_{i}∈ℕ|n=∑_{i=1}^{k+1} n_{i}} ∏_{i=1}^{k+1} D_{2}((0, 0), (n_{i}, 0)).

Let P be some path in D_{k+2}((0, 0), (n, 0)). Denote the k + 2 contact points of P, from left to right, by p_{1} = (x_{1}, 0), …, p_{k+2} = (x_{k+2}, 0). (Note that x_{1} = 0, x_{k+2} = n.) Those points

p_{2} = (4, 0)^{p_{2} = (4, 0)}  ^{p_{3} = (10, 0)}^{p_{1} = (0, 0)}  ^{(4, 0)}^{(0, 0)}  S′_{2}  ^{p_{3} = (10, 0)} P S_{1}  S_{2} S′_{1}  ^{(6, 0)}^{(0, 0)}^{p_{1} = (0, 0)}  ^{p_{2} = (4, 0)}

Figure 4: (a) The Dyck path P is in D_{3}((0, 0), (10, 0)), and has three contact points: p_{1} = (0, 0), p_{2} = (4, 0) and p_{3} = (10, 0). (b) A partition of P according to its contact points into two consecutive sub-paths S_{1} and S_{2}, where S_{1} is in D_{2}((0, 0), (4, 0)) and S_{2} is in D_{2}((4, 0), (10, 0)). (c) The Dyck path S′_{1} (respectively, S′_{2}) is obtained from S_{1} (resp., S_{2}) by a shift of all points in it, x_{1} = 0 (resp., x_{2} = 4) units left.

define a partition of P into consecutive sub-paths, namely, for each 1 ≤ i ≤ k + 1, we define S_{i} to be the sub-path of P between p_{i} and p_{i+1}. For each 1 ≤ i ≤ k +1, define n_{i} = x_{i+1} −x_{i}, and let S′_{i} be the Dyck path in D_{2}((0, 0), (n_{i}, 0)) obtained from S_{i} by a shift of all points in it, x_{i} units left. (See Figure 4 for an illustration.) We define g(P) as ∏_{i=1}^{k+1} S′_{i}. Clearly, this map is bijective (the inverse is given by the concatenation of all sub-paths {S′_{i}} in their respective order). This implies that both sets have the same cardinality, that is,

ϕ(n, k) = ∑ ; {1≤n_{i}∈ℕ|n=∑_{i=1}^{k+1} n_{i}} ∏_{i=1}^{k+1} |D_{2}((0, 0), (n_{i}, 0))| = ∑ ; {1≤n_{i}∈ℕ|n=∑_{i=1}^{k+1} n_{i}} ∏_{i=1}^{k+1} a_{n_{i}}. (3)

Since a_{0} = 0, the right-hand side of (3) is equal to ∑_{{0≤n_{i}∈ℕ|n=∑_{i=1}^{k+1} n_{i}}} ∏_{i=1}^{k+1} a_{n_{i}}. But the latter term is precisely a^{k+1}(n), which completes the proof.

The following statement implies that the problem of finding the number of Dyck paths that start and finish at points with arbitrary y-coordinates is equivalent to the problem of finding the number of Dyck paths that start and finish on the x-axis. It follows as a simple corollary of Proposition 7 and Observation 1.

Lemma 9. For any integers i, i′, j, j′ and t, such that j, j′ ≥ 0 and t ≥ 1, there is a bijection between D_{t}((i, j), (i′, j′)) and D_{t+j+j′}((i, 0), (i′ + j + j′, 0)).

To complete the proof of Theorem 2, we distinguish the two following cases: Case 1: t + j + j′ = 1. In this case t = 1, j = j′ = 0, and so, d_{j}^{j,j′}(n) = d_{1}^{0,0}(n) = |D_{1}((0, 0), (n, 0))|. By Theorem 1, d_{1}^{0,0}(n) = 0 for all n > 0, and d_{1}^{0,0}(0) = 1. It follows that

D_{1}^{0,0}(x) = ∑_{n≥0} d_{1}^{0,0}(n)x^{n} = 1 = \frac{(1 − \sqrt{1 − 4x^{2}})^{t+j+j′−1}}{2^{(t+j+j′−1)} · x^{(j+j′)}} .

Case 2: t + j + j′ ≥ 2. By Lemma 9, we have

d_{t}^{j,j′}(n) = |D_{t}((0, j), (n, j′))| = |D_{t+j+j′}((0, 0), (n + j + j′, 0))| = ϕ(n + j + j′, t + j + j′ − 2).

By Lemma 8, we deduce that

d_{t}^{j,j′}(n) = ϕ(n + j + j′, t + j + j′ − 2) = a^{t+j+j′−1}(n + j + j′) = a^{t+j+j′−1}[j + j′](n).

Therefore,

D_{t}^{j,j′}(x) = ∑_{n≥0} d_{t}^{j,j′}(n)x^{n} = \frac{A(x)^{t+j+j′−1}}{x^{(j+j′)}} = \frac{(1 − \sqrt{1 − 4x^{2}})^{t+j+j′−1}}{2^{(t+j+j′−1)} · x^{(j+j′)}} .

4 Chu-Vandemonde Summation Formula

In this section we provide a simple proof for the analogue of the Chu-Vandemonde summation formula for Dyck paths, which was already obtained by different techniques in [4, p. 4, Eq. (18)] Refer to [12] for similar results.

Following [4], we define B_{p,q} := |D((0, 0), (p, q))|, for any non-negative integers p and q. By Theorem 1 and the second part of Observation 1, the equation

P_{n}(x) = ∑_{t=2}^{n+1} |D_{t}((0, 0), (2n, 0))|x^{t} = ∑_{t=2}^{n+1} |D((0, t − 2), (2n − t, 0))|x^{t} = ∑_{t=2}^{n+1} B_{2n−t,t−2}x^{t}

holds. In [4, 5], it is proved that P_{n}(C(x)) = ∑_{b=0}^{∞} C_{n+b}x^{b}. We obtain the following identity:

\begin{matrix}∑_{b=0}^{∞} C_{n+b}x^{b} = ∑_{t=2}^{n+1} B_{2n−t,t−2}(\frac{1−\sqrt{1−4x}}{2x})^{t} = ∑_{t=2}^{n+1} B_{2n−t,t−2}^{\frac{( \frac{1−\sqrt{1−4x}}{2} )^{t}}{x^{t}}} = \\ ∑_{t=2}^{n+1} B_{2n−t,t−2} ∑_{m=0}^{∞} a^{t}(2m + 2t)x^{m} = ∑_{b=0}^{∞}(∑_{t=2}^{n+1} B_{2n−t,t−2} · a^{t}(2b + 2t))x^{b}. \end{matrix}  (4)

By Lemma 8 and Theorem 1, we have

a^{t}(2b + 2t) = |D_{t+1}((0, 0), (2b + 2t, 0))| = |D((0, t − 1), (2b + t − 1, 0))| = B_{2b+t−1,t−1}.

Equating coefficients in (4) yields

C_{n+b} = ∑_{t=2}^{n+1} B_{2n−t,t−2}B_{2b+t−1,t−1} = ∑_{m=1}^{n} B_{2n−m−1,m−1}B_{2b+m,m}, ∀b ≥ 0

or equivalently,

\frac{1}{n + b + 1}\binom{2n + 2b}{n + b} = ∑_{m=1}^{n} \frac{m}{n}\binom{2n − m − 1}{n − 1}\frac{m + 1}{b + m + 1}\binom{2b + m}{b}, ∀b ≥ 0, n ≥ 1

which is the analogue of the Chu-Vandemonde formula for Dyck paths.

References

[1] I. Arizono, H. Ohta, S. J. Deutsch, and C. Wang, An analysis of the E_{l}/E_{k}/1 queueing system by restricted minimal lattice paths, J. Operational Research Society 46 (1995), 245–253.

[2] J. Bandlow and K. Killpatrick, An area-to-inv bijection between Dyck paths and 312-avoiding permutations, Electron. J. Combin. 8 (1) (2001), Article #R40.

[3] W. Böhm, A. Krinik, and S. G. Mohanty, The combinatorics of birth-death processes and applications to queues, Queueing Syst. 26 (1997), 255–267.

[4] R. Brak and J. W. Essam, Bicoloured Dyck paths and the contact polynomial for n non-intersecting paths in a half-plane lattice, Electron. J. Combin. 10 (2003), Article #R35.

[5] R. Brak, J. W. Essam, and A. Owczarek, New results for directed vesicles and chains near an attractive wall, J. Stat. Phys. 93 (1998), 155–192.

[6] M. Draief and J. Mairesse, Services within a busy period of an M/M/1 queue and Dyck paths, Queueing Syst. 49 (2005), 73–84.

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

[8] G. Fayolle and R. Iasnogorodski, Two coupled processors: the reduction to a Riemann-Hilbert problem, Probab. Theory Related Fields 47 (1979), 325–351.

[9] G. Fayolle, R. Iasnogorodski, and V. Malyshev, Random Walks in the Quarter-Plane, Springer, 1999.

[10] W. Feller, An Introduction to Probability Theory and its Applications, Volume 1, Wiley, 1967.

[11] P. Flajolet and F. Guillemin, The formal theory of birth-and-death processes, lattice path combinatorics, and continued fractions, Adv. Appl. Probab. 32 (2000), 750–778.

[12] H. Gould, Some generalizations of Vandermonde convolution, Amer. Math. Monthly 63 (1956), 84–91.

[13] D. E. Knuth, The Art of Computer Programming, Volume 1, Addison-Wesley, 1973.

[14] C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001), 510–530.

[15] T. Mansour, Counting peaks at height k in a Dyck path, J. Integer Seq. 5 (2002), Article 02.1.1.

[16] T. Mansour, E. Y. P. Deng, and R. R. X. Du, Dyck paths and restricted permutations, Discrete Appl. Math. 154 (2006), 1593–1605.

[17] S. G. Mohanty, Combinatorial aspects of some random walks, in P. Revesz and B. Toth, eds., Random Walks, János Bolyai Mathematical Society, Budapest, 1999, pp. 259–273.

[18] K. Muto, H. Miyazaki, Y. Seki, Y. Kimura, Y. Shibata, Lattice path counting and M/M/c queueing systems, Queueing Syst. 19 (1995), 193–214.

[19] P. Peart and W. J. Woan, Dyck paths with no peaks at height k, J. Integer Seq. 4 (2001), Article 01.1.3.

[20] R. Stanley, Catalan Addendum, 2008. Available via

    http://www-math.mit.edu/∼rstan/ec/catadd.pdf.

[21] R. Stanley, Enumerative Combinatorics, Volume 1, Wadsworth and Brooks/Cole, 1986.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 11B83, 11Y55. Keywords: Catalan numbers, Dyck paths.

(Concerned with sequence \underline{A000108}.)

Received December 30 2007; revised version received August 7 2008. Published in Journal of Integer Sequences, August 7 2008. Slight revision, August 17 2008.

Return to Journal of Integer Sequences home page.