On Enumeration of Dyck Paths with Colored Hills

Milan Janjić Department of Mathematics and Informatics University of Banja Luka Banja Luka, 78000 Republic of Srpska, BA

                    agnus@blic.net

Abstract

We continue to investigate the properties of the earlier defined functions f_{m} and g_{m}, which depend on an initial arithmetic function f_{0}. In this paper, values of f_{0} are the Fine numbers. We investigate functions f_{i}, g_{i}, (i = 1, 2, 3, 4), and show that these functions count Dyck paths having hills in different colors. For each function, we also derive an explicit formula. We also prove several results which mutually connect these functions. It appears that g_{2} and g_{3} are well-known objects called the Catalan triangles.

We finish with two identities relating different kind of combinatorial objects.

1 Introduction

This paper is a continuation of the investigations of restricted words from the author’s previous papers, where two quantities f_{m}(n) and g_{m}(n, k) are defined as follows. For an initial arithmetic function f_{0}, the function f_{m}, (m > 0) is the mth invert transform of f_{0}. The function g_{m}(n, k), (1 ≤ k ≤ n) is defined in the following way:

g_{m}(n, k) = ∑_{i_{1}+i_{2}+···+i_{k}=n} f_{m−1}(i_{1}) · f_{m−1}(i_{2}) ⋯ f_{m−1}(i_{k}).  (1)

Also, the following equation holds:

f_{m}(n) = ∑_{k=1}^{n} g_{m}(n, k).  (2)

We restate [2, Propositions 10] which will be used throughout the paper.

Proposition 1. Let f_{0} the arithmetic function whose values are nonnegative integers, and f_{0}(1) = 1. Assume next that, for n ≥ 1, we have f_{m−1}(n) words of length n − 1 over a finite alphabet α. Let x be a letter which is not in α. Then, the value of g_{m}(n, k) is the number of words of length n − 1 over the alphabet α ∪ {x} in which x appears exactly k − 1 times.

We denote by G_{m}(n) the array g_{m}(n, k) viewed as a lower triangular matrix of order n. It is proved in [2, Proposition 6] that

G_{m}(n) = G_{1}(n) · L_{n}^{m−1},  (3)

where L_{m−1} is the lower triangular Pascal matrix of order m − 1. In particular, we have

g_{m}(n, k) = ∑_{i=k}^{n} \binom{i − 1}{k − 1}g_{m−1}(n, i).  (4)

We also have the following equation:

∑_{n=k}^{∞} g_{m}(n, k)x^{n} = (∑_{i=1}^{∞} f_{m−1}(i)x^{i})^{k} .  (5)

Remark 2. We note that throughout the paper m, n, and k will be integers such that m > 0 and 1 ≤ k ≤ n.

We define the the initial function f_{0} such that f_{0}(n) = 𝔽_{n}, (n = 1, 2, …), where 𝔽_{1}, 𝔽_{2}, … are the Fine numbers with 𝔽_{1} = 1. Thus, f_{0}(1) = 1, f_{0}(2) = 0, f_{0}(3) = 1, and so on. The sequence of the Fine numbers is \underline{A000957} in OEIS [5].

2 A combinatorial result

All investigation in the paper are based on the following result.

Proposition 3. For m ≥ 1, we have

1. The value of g_{m}(n, k) is the number of Dyck paths of semilength n − 1 having hills in m colors, of which k − 1 are in color m.

2. The value of f_{m}(n) is the number of Dyck paths of semilength n − 1 having hills in m colors.

Proof. We use induction on m. We have f_{0}(n) = 𝔽_{n}. It is well-known that f_{0}(n) is the number of Dyck paths of semilength n − 1 with no hills. In particular, f_{0}(1) = 1 since the empty path has no hills. If we consider the symbol x in Proposition 1 as a hill (of color 1), then the right side of (1) counts the Dyck paths of semilength (i_{1}−1)+(i_{2}−1)+⋯+(i_{k}−1)+k−1 = n − 1 having k − 1 hills. Hence the assertion is true for m = 1.

The second assertion holds by the formula (2).

Assume that for m > 1, the number f_{m−1}(n) equals the number of Dyck paths of semilength n − 1 having hills in m − 1 colors. Since f_{m−1}(1) = 1 and since the empty Dyck path has no hills, we may apply (2) to obtain the assertion.

We state particular result for m = 1. The value of f_{1}(n) is the number of Dyck paths of semilength n − 1, which equals the Catalan number C_{n−1}. Hence,

f_{1}(n) = C_{n−1}, (n = 1, 2, …).

Since f_{1}(1), f_{1}(2), … is the invert transform of f_{0}(1), f_{0}(2), …, we obtain the following relation between Fine and Catalan numbers.

Corollary 4. The sequence C_{0}, C_{1}, … of the Catalan numbers is the invert transform of the sequence 𝔽_{1}, 𝔽_{2}, … of the Fine numbers.

The sequence of the Catalan numbers is \underline{A000108} in OEIS [5]. From [2, Identity 12], by the use of the identity i · \binom{i−1}{k−1} = k\binom{i}{k}, we obtain the following identity relating the Fine and the Catalan numbers via the partial Bell polynomials B_{n,k}.

Identity 5.

(k − 1)!B_{n,k}(C_{0}, 2! · C_{1}, 3! · C_{2}, …) = ∑_{i=k}^{n} \binom{i}{k}(i − 1)!B_{n,i}(𝔽_{1}, 2! · 𝔽_{2}, 3! · 𝔽_{3}, …).

3 Triangle g_{1}(n, k)

According to Theorem 3, we have

Proposition 6. 1. The value of g_{1}(n, k) is the number of Dyck paths of semilength n − 1 having k − 1 hills.

2. The number of Dyck paths of semilngth n − 1 equals f_{1}(n).

The array g_{1}(n, k) is \underline{A065600} in OEIS [5].

Remark 7. The number g_{1}(n, k) is also the number of Lukasiewicz paths of length n having k level steps. Next, it is the number of 321-avoiding permutations of [n] having k fixed points (see comments of this array in OEIS [5]).

In Section 7, the following explicit formula will be derived.

g_{1}(n, k) = \frac{k}{n} · ∑_{i=k}^{n}(−2)^{i−k}\binom{i}{k}\binom{2n}{n − i}.  (6)

Since f_{0}(n) = g_{1}(n, 1), we have the following explicit formula for the Fine numbers.

𝔽_{n} = \frac{1}{n} · ∑_{i=1}^{n}(−2)^{i−1} · i · \binom{2n}{n − i}.

The sequence \{g_{1}(n, 2), n = 2, 3, …\} is \underline{A065601}, \{g_{1}(n, 3), n = 3, 4, …\} is \underline{A294527} in OEIS [5].

4 Triangle g_{2}(n, k)

The Segner formula for the Catalan numbers means that the sequence C_{1}, C_{2}, … of the Catalan numbers is the invert transform of the sequence C_{0}, C_{1}, . . .. This yields that f_{2}(n) = C_{n}, for all n. We thus obtain the following combinatorial interpretation of the Catalan numbers.

Corollary 8. The Catalan number C_{n} is the number of Dyck paths of semilength n − 1 having hills in two colors.

Remark 9. Note that this property of Catalan numbers does not appear explicitly in Stanley [6].

We also have the following identity relating the Catalan numbers and the partial Bell polynomials.

Identity 10.

(k − 1)!B_{n,k}(C_{1}, 2! · C_{1}, 3! · C_{3}, …) = ∑_{i=k}^{n} \binom{i}{k}(i − 1)!B_{n,i}(C_{0}, 2! · C_{1}, 3! · C_{2}, …).

We derive an explicit formula for g_{2}(n, k). It is known that

g(x) = \frac{1 − \sqrt{1 − 4x}}{2x}

is the ordinary generating function for the sequence C_{0}, C_{1}, . . .. It follows from (5) that ∑_{n=k}^{∞} g_{2}(n, k)x^{n} is the expansion of [xg(x)]^{k} into powers of x. Hence, we have

∑_{n=k}^{∞} g_{2}(n, k)x^{n} = (\frac{1 − \sqrt{1 − 4x}}{2})^{k} .

Using the binomial theorem and the expansion of a binomial series, we obtain

∑_{n=k}^{∞} g_{2}(n, k)x^{n} = (\frac{1 − \sqrt{1 − 4x}}{2})^{k} = 2^{−k} ∑_{i=0}^{k}(−1)^{i}\binom{k}{i}(1 − 4x)^{\frac{i}{2}} .

On the other hand, we have

(1 − 4x)^{\frac{i}{2}} = ∑_{n=0}^{∞}(−4)^{n}\binom{\frac{i}{2}}{n}x^{n} = ∑_{n=0}^{∞}(−2)^{n} · \frac{∏_{t=0}^{n−1}(i − 2t)}{n!}.

We thus obtain

∑_{n=k}^{∞} g_{2}(n, k)x^{n} = ∑_{n=0}^{∞} (∑_{i=0}^{k}(−1)^{i+n}2^{n−k}\binom{k}{i}\frac{∏_{t=0}^{n−1}(i − 2t)}{n!}) x^{n}.

Comparing coefficients of the same powers of x, we firstly obtain

g_{2}(n, k) = \frac{2^{n−k}}{n!} ∑_{i=0}^{k}(−1)^{i+n}\binom{k}{i} ∏_{t=0}^{n−1}(i − 2t), (n ≥ k).

It is clear that ∏_{t=0}^{n−1}(i − 2t) = 0, if n is even.

If i is odd, we denote i = 2j − 1, (1 ≤ j ≤ ⌊\frac{k+1}{2}⌋). It is easy to see that

∏_{t=0}^{n−1}(2j − 2t − 1) = ∏_{u=0}^{j−1}(2j − 2t − 1) · ∏_{u=j}^{n−1}(2j − 2t − 1)
= (−1)^{n−j}(2j − 1)!!(2n − 2j − 1)!!.

Finally, we have Proposition 11. The following formula holds:

g_{2}(n, k) = \frac{2^{n−k}}{n!} ∑_{j=1}^{⌊ \frac{k+1}{2} ⌋}(−1)^{j−1}\binom{k}{2j − 1} · (2j − 1)!! · (2n − 2j − 1)!!.  (7)

In particular, since g_{2}(n, 1) = f_{1}(n) = C_{n−1}, we obtain the following result. Corollary 12. For n > 1, we have

C_{n−1} = \frac{2^{n−1}}{n!} · (2n − 3)!!.

Remark 13. The preceding is the famous Euler formula for the Catalan numbers.

Remark 14. We note that array g_{2}(n, k) is the mirror of the Catalan triangle. It appears as \underline{A033184} in OEIS [5]. The Catalan triangle is \underline{A009766}.

We now prove that g_{2}(n, k) satisfies a simple recurrence relation.

Proposition 15. The following recurrence holds:

g_{2}(n + 1, k + 1) = g_{2}(n + 1, k + 2) + g_{2}(n, k).  (8)

Proof. According to (1), we have

g_{2}(n + 1, k + 1) = ∑_{i_{1}+i_{2}+···+i_{k+1}=n+1} C_{i_{1}−1} · C_{i_{2}−1} ⋯ C_{i_{k+1}−1},  (9)

where the sum is taken over positive i_{t}.

Firstly, we extract the terms obtained for i_{k+1} = 1. Since C_{i_{k+1}−1} = C_{0} = 1, we obtain

g_{2}(n, k) = ∑_{i_{1}+i_{2}+···i_{k}=n} C_{i_{1}−1} · C_{i_{2}−1} ⋯ C_{i_{k}−1},

which is the second term on the right-hand side in formula (8).

It remains to calculate the sum on the right-hand side of Equation (8), when i_{k+1} > 1. We consider the equation

g_{2}(n + 1, k + 2) = ∑_{j_{1}+j_{2}+···+j_{k+1}+j_{k+2}=n+1} C_{j_{1}−1} · C_{j_{2}−1} ⋯ C_{j_{k+1}−1} · C_{j_{k+2}−1}.

Denote j_{k+1} +j_{k+2} = i_{k+1} > 1. This equation is fulfilled for the following pairs of (j_{k+1}, j_{k+2}):

{(1, i_{k+1} − 1), (2, i_{k+1} − 2), …, (i_{k+1} − 1, 1)}.

. We rearrange terms in the sum as follows:

g_{2}(n + 1, k + 2) = ∑_{j_{1}+···+j_{k}+i_{k+1}=n+1} C_{j_{1}−1}C_{j_{2}−1} ⋯ C_{j_{k}−1} · ∑_{i=1}^{i_{k+1}−1} C_{i−1}C_{i_{k+1}−1−i}.

Segner formula implies ∑_{i=1}^{i_{k+1}−1} C_{i−1}C_{i_{k+2}−1−i} = C_{i_{k+1}−1}. We thus obtain

g_{2}(n + 1, k + 2) = ∑_{j_{1}+···+j_{k}+i_{k+1}=n+1} C_{j_{1}−1}C_{j_{2}−1} ⋯ C_{j_{k}−1} · C_{i_{k+1}−1},

for i_{k+1} > 1, which is the first term in Equation (8).

We now prove that the following recurrence holds:

Proposition 16. For n, k > 1, we have

g_{2}(n, k) = ∑_{i=k−1}^{n−2} g_{2}(n − 1, i) + 1.  (10)

Proof. From Proposition 15, we obtain the following sequence of equations.

g_{2}(n + 1, 3) = g_{2}(n + 1, 2) − g_{2}(n, 1),
g_{2}(n + 1, 4) = g_{2}(n + 1, 3) − g_{2}(n, 2),
⋮
g_{2}(n + 1, k + 2) = g_{2}(n + 1, k + 1) − g_{2}(n, k).

Adding terms on the left-hand sides of these equations, and those on the right-hand sides, we obtain

∑_{i=1}^{k} g_{2}(n, i) = g_{2}(n + 1, 2) − g_{2}(n + 1, k + 2).

Replacing n by n − 1, and k by k − 2, (k > 2), we obtain

g_{2}(n, 2) = g_{2}(n, k) + ∑_{i=1}^{k−2} g_{2}(n − 1, i).

In particular, for k = n, this equation becomes

g_{2}(n, 2) = ∑_{i=1}^{n−2} g_{2}(n − 1, i) + 1,

and the formula follows.

This result gives an interesting property of the Catalan triangle which is analogous to the horizontal recurrence of the binomial coefficients.

Corollary 17. The sum of the first k terms in the nth row of the Catalan triangle equals the kth term in (n + 1)th row.

We now derive a simpler explicit formula for g_{2}(n, k).

Proposition 18. The following formula holds: g_{2}(n, n) = 1, and

g_{2}(n, k) = \frac{k ∏_{i=1}^{n−k−1}(n + i)}{(n − k)!}.  (11)

Equivalently,

g_{2}(n, k) = \frac{k}{n − k} \binom{2n − k − 1}{n}, (n > k).  (12)

Proof. Using the recurrence (8), we have

g_{2}(n + 1, k + 1) − g_{2}(n, k) = \frac{(n + 2) ⋯ (2n − k − 1) · [(k + 1)(2n − k) − k(n + 1)]}{(n − k)!}

= \frac{(n + 2) ⋯ (2n − k − 1) · (k + 2)(n − k)}{(n − k)!}

= \frac{(k + 2)(n + 2) ⋯ (2n − k − 1)}{(n − k − 1)!} = g_{2}(n + 1, k + 2).

and the assertion follows from Proposition 15.

From (10), we obtain the following identity: Identity 19. For n > k, we have

\frac{k}{n − k} · \binom{2n − k − 1}{n} = ∑_{i=k−1}^{n−2} \frac{i}{n − i − 1}\binom{2n − 3 − i}{n − 1} + 1.

We denote by A(n, k) the mirror triangle of g_{2}(n, k). Hence, A(n, k) = g_{2}(n, n − k + 1). Proposition 20. The triangle A(n, k) satisfies the following conditions:

1. A(n, 1) = 1, A(n, n) = C_{n−1}.

2. A(n + 1, k + 1) = A(n + 1, k) + A(n, k + 1),

3. A(n, n − 1) = C_{n−1}. Proof. 1. We have A(n+1, 1) = g_{2}(n+1, n+1) = f_{0}(1)^{n+1} = 1. Also, A(n, n) = g_{2}(n, 1) =

C_{n−1}.

2. We have A(n + 1, k + 1) = g_{2}(n + 1, n − k + 1). Using Proposition 15 yields A(n + 1, k + 1) = g_{2}(n + 1, n − k + 2) + g_{2}(n, n − k) = A(n + 1, k) + A(n, k + 1).

3. We have A(n, n−1) = g_{2}(n, 2). According to (1), we have g_{2}(n, 2) = ∑_{i=1}^{n−2} C_{i−1}C_{n−i−2}. Applying the Segner formula yields A(n, n − 1) = C_{n−1}.

Remark 21. We note that the triangle A(n, k) is the Catalan triangle, considered in Koshy[3, Chapter 15]. The chapter is devoted to a family of binary words.

Comparing result which is obtained in this book and our result, we obtain Proposition 22. The following sets has the same number of elements:

1. The number of Dyck paths of semilength n−1 having hills in two colors, of which n−k hills in color 2.

2. The number of binary words of length n + k − 2 having n − 1 ones and k − 1 zeros and no initial segment has more zeros than ones.

We also add a short bijective proof.

Proof. In a Dyck path of semilength n − 1 with n − k hills of color 2, we replace each hill of color 2 by 1. Between two hills of color 2 are the standard Dyck paths, which we interpret as binary words having the same number of zeros and ones, and no initial segment having more zeros that ones. In this way we obtain a binary words having n − 1 ones and k − 1 zeros, and no initial segment has more zeros then ones. It is clear that this correspondence is injective.

Conversely, if w is a binary word from 2. We start from the last zero in w. Each ones following this zero we replace by a hill of color 2. Scanning from this zero to the left, we find the smallest interval having the same number of zeros and ones. We replace this interval by the Dyck path which semilength equals the number of zeros. Then we apply the same procedure on the remaining binary word. When we find the Dyck path designated by the foremost zero to the left, we replace the remaining ones by a hill of color 2. This correspondence is also injective.

5 Triangle g_{3}(n, k)

From Theorem 3, we obtain

Proposition 23. 1. The value of g_{3}(n, k) is the number of Dyck paths of semilength n−1 with hills in three colors, of which k − 1 hills in color 3.

2. The number of Dyck paths of semilngth n − 1 having hills in three colors equals f_{3}(n).

We derive an explicit formula for g_{3}(n, k).

Proposition 24. We have

g_{3}(n, k) = \frac{k}{n}\binom{2n}{n − k}.  (13)

Proof. According to (2), we have

g_{3}(n, k) = ∑_{i=k}^{n} \binom{i − 1}{k − 1}g_{2}(n, i).

Using (11) yields

g_{3}(n, k) = ∑_{i=k}^{n} \binom{i − 1}{k − 1}\frac{i · (n + 1) · (n + 2) ⋯ (2n − i − 1)}{(n − i)!}

Using the identity i · \binom{i−1}{k−1} = k\binom{i}{k} implies

g_{3}(n, k) = \frac{k}{n} · ∑_{i=k}^{n} \binom{i}{k}\frac{n(n + 1) · (n + 2) ⋯ (2n − i − 1)}{(n − i)!},

that is

g_{3}(n, k) = \frac{k}{n} · ∑_{i=k}^{n} \binom{i}{k}\binom{2n − i − 1}{n − 1}.

Hence, our statement is equivalent to the following binomial identity.

Identity 25. We have

\binom{2n}{n + k} = ∑_{i=k}^{n} \binom{i}{k}\binom{2n − i − 1}{n − 1}.  (14)

Proof. We prove the identity combinatorially. We count subsets of n + k elements of the set width 2n element after the position of the (k + 1)th element. If i + 1 is the position of the k + 1th element of the set then we have \binom{i}{k} elements before and \binom{2n−i−1}{n−1} after this element. Since k ≤ i ≤ n the identity is true.

Remark 26. The Catalan triangle g_{3}(n, k) is defined by Shapiro [4]. It is the array \underline{A039598} in OEIS [5].

Taking into account its original combinatorial interpretation, we obtain

Corollary 27. The following sets has the same number of elements:

1. The number of nonintersecting lattice paths of length n in the first quadrant at the distance k.

2. The number of Dyck paths of semilength n − 1 having hills in three colors, of which k − 1 hills are of color 3.

Proof. Consider a pair of paths of length n − 1 at the distance k. We may extend these paths to the pair of nonintersecting paths of length n in the following ways:

1. Add either the vertical or horizontal step to both paths. We thus obtain a path of length n and of the distance k.

2. Add the vertical step to the path above and the horizontal step to the path below, we obtain the pair of paths of length n and of distance is k + 1.

3. Add the horizontal step to the path above and the vertical step to the path below, we obtain the pair of paths of length n and of distance is k − 1.

Hence, if we denote by B(n, k) the number of nonintersecting paths of length n and the distance k, we have the following recurrence:

B(n, k) = B(n − 1, k + 1) + 2B(n − 1, k) + B(n − 1, k − 1).

It is easy to check that g_{3}(n, k) satisfies this recurrence.

Remark 28. This array is also considered in Koshy[3, Chapter 14]. We note that no connection between triangles from Chapters 14 and 15 is mentioned in this book. We see that they are closely related.

We derive one more relation between g_{2}(n, k) and g_{3}(n, k).

Proposition 29. We have

g_{2}(n, k) = ∑_{i=0}^{k−1} \binom{k}{i}g_{3}(n − k, k − i).  (15)

Proof. Using [2, Proposition 2], we obtain

g_{2}(n, k) = ∑_{i_{1}+i_{2}+···+i_{k}=n} C_{i_{1}−1} · C_{i_{2}−1} ⋯ C_{i_{k}−1},

where the sum is taken over positive i_{t}, (t = 1, …, k). Replacing i_{t} − 1 = j_{t}, (t = 1, 2, …, k) we obtain

g_{2}(n, k) = ∑_{j_{1}+j_{2}+···+j_{k}=n−k} C_{j_{1}} · C_{j_{2}} ⋯ C_{j_{k}},

where the sum is taken over nonnegative j_{t}. Note that in the case k = n we have g_{2}(n, n) = 1. We consider the case k < n. Assume that there are i, (0 ≤ i ≤ k − 1) of j_{t} which are equal 0. Then

g_{2}(n, k) = ∑_{i=0}^{k−1} \binom{k}{i} · ∑_{s_{1}+s_{2}+···+s_{k−i}=n−k} C_{s_{1}} · C_{s_{2}} ⋯ C_{s_{k−i}},

where s_{t} > 0, (t = 1, 2, …, k − i) and k − i ≥ n − k. According Equation (1), we have

∑_{s_{1}+s_{2}+···+s_{k−i}=n−k} C_{s_{1}} · C_{s_{2}} ⋯ C_{s_{k−i}} = g_{3}(n − k, k − i),

which proves the statement.

We next derive an explicit formula for f_{3}(n).

Proposition 30. The following formula holds:

f_{3}(n) = \binom{2n − 1}{n}.

Proof. We have

f_{3}(n) = \frac{1}{n} ∑_{k=1}^{n} k\binom{2n}{n − k} = \frac{1}{n} ∑_{k=0}(n − k)\binom{2n}{k}

= ∑_{k=0}^{n} \binom{2n}{k} − ∑_{k=1}^{n} \frac{k}{n} · \frac{2n}{k} · \binom{2n − 1}{k − 1}

= 1 + ∑_{k=1}^{n} (\binom{2n − 1}{k} + \binom{2n − 1}{k − 1}) − 2 ∑_{k=1}^{n} \binom{2n − 1}{k − 1}

= ∑_{k=0}^{n} \binom{2n − 1}{k} − ∑_{k=0}^{n−1} \binom{2n − 1}{k}

= \binom{2n − 1}{n}.

The sequence f_{3}(n), n = 1, 2, … is \underline{A001700} in OEIS [5].

Remark 31. The preceding proof means that results in this paper depend only on the fundamental properties of Fine and Catalan numbers and some of our earlier results.

6 Triangle g_{4}(n, k)

Taking into account Proposition 30, we conclude that this case is considered in [2, Section 4], where the following results are obtained.

Proposition 32. 1. The following equation holds:

g_{4}(n, k) = \frac{2^{n−k}}{n!} ∑_{i=1}^{k}(−1)^{k−i}\binom{k}{i} · ∏_{j=0}^{n−1}(i + 2j).  (16)

2. The value of g_{4}(n, k) is the number of ternary words of length 2n − 1, having k − 1 letters equal to 2, and in all binary subwords the number of ones is greater by 1 than the number of zeros. Also, each 2 is both preceded and followed by a binary subword.

3. The value of f_{4}(n) is the number of ternary words of length 2n−1 in which 2 is preceded and followed by a binary subword in which the number of ones is greater by 1 than the number of zeros.

The array g_{4}(n, k) is \underline{A049027}, f_{4}(n) is \underline{A035324}.

As a consequence, we have the following bijections:

Corollary 33. The following sets have the same number of elements.

1. The set of Dyck paths of semilength n − 1 having hills in four colors, of which k − 1 are in color 4.

2. The set of ternary words of length 2n − 1, having k − 1 letters equal to 2, and in all binary subwords the number of ones is greater by 1 than the number of zeros. Also, each 2 is both preceded and followed by a binary subword.

Corollary 34. The following sets have the same number of elements. 1. The set of Dyck paths of semilength n − 1 having hills in four color.

2. The set of ternary words of length 2n−1, such that in all binary subwords the number of ones is greater by 1 than the number of zeros, and each 2 is both preceded and followed by a binary subword.

7 Some explicit formulas and identities

From (3) and the fact that, for each integer p, we have

L_{n}^{p} = (p^{i−j}\binom{i − 1}{j − 1})_{n×n} ,

a mutually connection among different g_{m}(n, k) is easy to obtain.

Up to now, we have no an explicit formulas for g_{1}(n, k).

In matrix form, we have G_{1}(n) = G_{3}(n)L_{n}^{−2}. Hence, the following equation holds:

g_{1}(n, k) = \frac{k}{n} · ∑_{i=k}^{n}(−2)^{i−k}\binom{i}{k}\binom{2n}{n − i}.  (17)

Since g_{1}(n, 1) = 𝔽_{n}, we have the following explicit formula for the Fine numbers: Identity 35.

𝔽_{n} = \frac{1}{n} · ∑_{i=1}^{n}(−2)^{i−1} · i · \binom{2n}{n − i}.

We next derive an explicit formula for the central binomial coefficients. Identity 36. We have

\binom{2n − 2}{n − 1} = ∑_{i=1}^{n}(−1)^{i−1}i · \binom{2n}{n − i}.

Proof. We have

f_{1}(n) = ∑_{k=1}^{n} g_{1}(n, k) = \frac{1}{n} ∑_{k=1}^{n} ∑_{i=k}^{n} k(−2)^{i−k}\binom{i}{k}\binom{2n}{n − i}.

Changing the order of summation yields

f_{1}(n) = \frac{1}{n} ∑_{i=1}^{n} \binom{2n}{n − i} · ∑_{k=1}^{i} k(−2)^{i−k}\binom{i}{k}.

Next, we have

∑_{k=1}^{i} k(−2)^{i−k}\binom{i}{k} = i ∑_{t=0}^{i−1}(−2)^{t}\binom{i − 1}{t} = (−1)^{i−1}i.

Next, we write g_{2} as an alternating sums.

Since G_{2}(n) = G_{3}(n) · L_{n}^{−1}, we have

g_{2}(n, k) = \frac{k}{n} · ∑_{i=k}^{n}(−1)^{i−k}\binom{i}{k} · \binom{2n}{n − i}.  (18)

Comparing this equation and (12), we obtain the following identity: Identity 37. For k > 0, we have

\binom{2n − k − 1}{n} = \frac{n − k}{k} ∑_{i=k}^{n}(−1)^{i−k}\binom{i}{k}\binom{2n}{n − i}.

Also, since g_{2}(n, 1) = C_{n−1}, we obtain the following formula for the Catalan numbers. Identity 38.

C_{n−1} = \frac{1}{n} ∑_{i=1}^{n}(−1)^{i−1}i · \binom{2n}{n − i}.

We finish with two identities. The first one consists of eight items: a sum, a product, two integers, a rising factorial, a falling factorial, and two binomial coefficients. Identity 39.

k · ∏_{i=1}^{n−k−1}(n + i) = (n − k − 1)! · ∑_{i=0}^{k−1}(k − i)\binom{k}{i}\binom{2n − 2k}{n + 2k − i}.

The identity is derived from Equation (15).

From the equality G_{4}(n) = G_{3}(n)L_{n}, we obtain the identity consisting of ten items: an integer, two sums, a power of −1, a power of 2, a falling factorial, a rising factorial, and three binomial coefficients.

Identity 40.

∑_{i=k}^{n} i\binom{i − 1}{k − 1}\binom{2n}{n − i} = \frac{2^{n−k}}{(n − 1)!} ∑_{i=1}^{k}(−1)^{k+i}\binom{k}{i}i(i + 2) ⋯ (i + 2n − 2).

Remark 41. Note that the same method may be applied for enumeration of different kind of paths in which exists a part analogous to the hill in Dyck paths. This is, for instance, the case of Schroeder and Motzkin paths.

8 Acknowledgment

I would like to thank to Professor Djura Paunic for his help about the proof of Proposition 30.

References

[1] M. Janjić, Some formulas for numbers of restricted words, J. Integer Sequences 20 (2017), Article 17.6.5.

[2] M. Janjić, Pascal triangle and restricted words, J. Integer Sequences 21, (2018), Article 18.1.4.

[3] T. Koshy, Catalan Numbers with Applications, Oxford Univ. Press, 2009.

[4] L. W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976), 83–90.

[5] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, https://oeis.org.

[6] R. Stanley, Catalan Numbers, Cambridge University Press, 2015.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 11B39. Keywords: Fine number, Catalan number, Catalan triangle.

(Concerned with sequences \underline{A000108}, \underline{A000957}, \underline{A001700}, \underline{A009766}, \underline{A033184}, \underline{A035324}, \underline{A039598}, \underline{A049027}, \underline{A065600}, \underline{A065601}, and \underline{A294527}.)

Received May 29 2018; revised version received October 18 2018. Published in Journal of Integer Sequences, December 13 2018.

Return to Journal of Integer Sequences home page.