Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles

Paul Barry School of Science Waterford Institute of Technology Ireland

                     pbarry@wit.ie

Abstract

We find closed-form expressions and continued fraction generating functions for a family of generalized Catalan numbers associated with a set of Pascal-like number triangles that are defined by Riordan arrays. We express these generalized Catalan numbers as the moments of appropriately defined orthogonal polynomials. We also describe them as the row sums of related Riordan arrays. Links are drawn to the Narayana numbers and to lattice paths. We further generalize this one-parameter family to a three-parameter family. We use the generalized Catalan numbers to define generalized Catalan triangles. We define various generalized Motzkin numbers defined by these general Catalan numbers. Finally we indicate that the generalized Catalan numbers can be associated with certain generalized Eulerian numbers by means of a special transform.

1 Introduction

The Catalan numbers [26] are among the most important numbers in combinatorics. They have many important properties, which are shared to one degree or another with related sequences. This has prompted works which extend or generalize the Catalan numbers in various ways [1, 13]. In this note, we use the theory of Riordan arrays, and in particular a family of Pascal-like Riordan arrays, to find families of generalized Catalan numbers. A short introduction to Riordan arrays is provided later in this section.

In fact, we find families of Catalan-like polynomials, which through specialization, give us generalized Catalan numbers. All are found to be moment sequences, like the Catalan numbers themselves, and in most cases we give their Hankel transforms. A feature that they share is that the coefficient arrays of the defining orthogonal polynomials are Riordan arrays.

The Catalan numbers

C_{n} = \frac{1}{n + 1}\binom{2n}{n}

\underline{A000108} which begin

1, 1, 2, 5, 14, 42, 132, 429, …,

occur in two ways in Pascal’s triangle (B_{n,k} = \binom{n}{k}). First of all, as indicated by the above formula, they are equal to the central binomial coefficients \binom{2n}{n}, divided by n + 1. That \binom{2n}{n} is divisible by n + 1 for all n is an interesting arithmetical property of Pascal’s triangle [10]. As is well-known, the central binomial coefficients \binom{2n}{n} \underline{A000984}, form the central spine of Pascal’s triangle \underline{A007318} when it is viewed as a centrally symmetric (or palindromic) triangle.

1

1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15  20  15  6  1

The alternative view of the Catalan numbers is as

C_{n} = B_{2n,n} − B_{2n,n−1} = \binom{2n}{n} − \binom{2n}{n − 1} = \binom{2n}{n} − \binom{2n}{n + 1}.

We illustrate C_{n} = \binom{2n}{n} − \binom{2n}{n+1} below.

1

1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15  20  15  6  1

When we view Pascal’s triangle as a lower-triangular matrix, we see these numbers as the difference of adjacent elements on alternate rows.

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 1 & 3 & 3 & 1 & 0 & 0 & 0 \\ 1 & 4 & 6 & 4 & 1 & 0 & 0 \\ 1 & 5 & 10 & 10 & 5 & 1 & 0 \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 \end{matrix} ) .

We recall that \binom{2n}{n} has the generating function

∑_{k=0}^{n} \binom{2n}{n}x^{n} = \frac{1}{\sqrt{1 − 4x}},

while the Catalan numbers C_{n} have the generating function

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

We then have

c(x) = \frac{1}{x}Rev(x(1 − x)),

and

c(x) = \frac{1}{1 − x − \frac{x^{2}}{1 − 2x − \frac{x^{2}}{1 − 2x − \frac{x^{2}}{1 − 2x − ⋯}}}}.

Here, the notation Rev refers to the reversion of a power series. If f(x) is a power series with f(0) = 0 and f′(0) ≠ 0, then f̄(x) = Rev(f)(x) is the solution u = u(x) to the equation f(u) = x such that u(0) = 0.

The Catalan numbers C_{n} are the row sums of the Riordan array

(1, x(1 − x))^{−1} = (1, xc(x)).

We also have the moment representation

C_{n} = \frac{1}{2π} ∫_{0}^{4} \frac{\sqrt{x(4 − x)}}{x} dx.

In the sequel, we shall generalize the Catalan numbers, and we shall seek to state the generalizations of the foregoing statements.

We shall be principally interested in this note in a family of Pascal-like triangles (T_{n,k}(r)) depending on an integer parameter r, where T_{n,k}(0) = B_{n,k}. That is, Pascal’s triangle coincides with r = 0. For r = 1, we get the Delannoy triangle \underline{A008288} which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 \\ 1 & 5 & 5 & 1 & 0 & 0 & 0 \\ 1 & 7 & 13 & 7 & 1 & 0 & 0 \\ 1 & 9 & 25 & 25 & 9 & 1 & 0 \\ 1 & 11 & 41 & 63 & 41 & 11 & 1 \end{matrix} ) .

The generalized Catalan numbers T_{2n,n}(1) − T_{2n,n+1}(1) in this case begin

1, 2, 6, 22, ….

These are the Schroeder numbers \underline{A006318}, which count Schroeder paths from (0, 0) to (2n, 0).

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 \\ 1 & 5 & 5 & 1 & 0 & 0 & 0 \\ 1 & 7 & 13 & 7 & 1 & 0 & 0 \\ 1 & 9 & 25 & 25 & 9 & 1 & 0 \\ 1 & 11 & 41 & 63 & 41 & 11 & 1 \end{matrix} ) .

Integer sequences in this note are referred to by their Annnnnn number from the On-Line Encyclopedia of Integer Sequences [24, 25] where such a number is known. All matrices in this note are integer valued, lower triangular, and invertible. In particular the main diagonal will always consist of all 1’s. Where examples are given, a suitable truncation is shown.

We recall that an ordinary Riordan array (g(x), f(x)) [4, 21, 22] is defined by two generating functions,

g(x) = g_{0} + g_{1}x + g_{2}x^{2} + ⋯, g_{0} ≠ 0,

and

f(x) = f_{1}x + f_{2}x^{2} + f_{3}x^{3} + ⋯, f_{1} ≠ 0,

with the (n, k)-th element of the corresponding lower-triangular matrix being given by

[x^{n}]g(x)f(x)^{k}.

In the sequel we shall always assume that g_{0} = f_{1} = 1. The inverse of the Riordan array (g(x), f(x)) is given by

(g(x), f(x))^{−1} = (\frac{1}{g(f̄(x))}, f̄) ,

where f̄(x) denotes the compositional inverse of f(x). Thus we have f(f̄(x)) = x and f̄(f(x)) = x. The product law for Riordan arrays (which coincides with matrix multiplication) is given by

(g(x), f(x)) · (u(x), v(x)) = (g(x)u(f(x)), v(f(x)).

The Hankel transform [15, 16] of a sequence a_{n} is the sequence h_{n} where h_{n} = |a_{i+j}|_{0≤i,j≤n}. If the g.f. of a_{n} is expressible as a continued fraction [6, 27] of the form

\frac{μ_{0}}{1 − α_{0}x − \frac{β_{1}x^{2}}{1 − α_{1}x − \frac{β_{2}x^{2}}{1 − α_{2}x − \frac{β_{3}x^{2}}{1 − α_{3}x − ⋯}}}},

then the Hankel transform of a_{n} is given by [15] the Heilermann formula

h_{n} = μ_{0}^{n+1}β_{1}^{n}β_{2}^{n−1} ⋯ β_{n−1}^{2}β_{n}.

If the g.f. of a_{n} is expressible as the following type of continued fraction:

\frac{μ_{0}}{1 + \frac{γ_{1}x}{1 + \frac{γ_{2}x}{1 + ⋯}}},

then we have

h_{n} = μ_{0}^{n+1}(γ_{1}γ_{2})^{n}(γ_{3}γ_{4})^{n−1} ⋯ (γ_{2n−3}γ_{2n−2})^{2}(γ_{2n−1}γ_{2n}).

A Motzkin path of length n is a lattice path from (0, 0) to (n, 0) with steps northeast, (1, 1), east (1, 0) and southeast, (1, −1), that does not go below the x-axis.

A Schroeder path of semi-length n is a lattice path from (0, 0) to (2n, 0) with steps northeast, (1, 1), east (2, 0) and southeast, (1, −1), that does not go below the x-axis.

2 Generalized Catalan numbers

The Riordan array

(\frac{1}{1 − x}, \frac{x(1 + rx)}{1 − x})

defines a Pascal-like matrix [7] with general term T_{n,k} given by

T_{n,k}(r) = ∑_{j=0}^{k} \binom{k}{j}\binom{n − j}{k}r^{j} = ∑_{j=0}^{n−k} \binom{k}{j}\binom{n − k}{j}(r + 1)^{j}.  (1)

These number triangles are “Pascal-like” in the sense that

T_{n,k} = T_{n,n−k}, T_{n,0} = 1, T_{n,n} = 1, T_{n,k} = 0 for n > k.

This array begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & r + 2 & 1 & 0 & 0 & 0 \\ 1 & 2r + 3 & 2r + 3 & 1 & 0 & 0 \\ 1 & 3r + 4 & r^{2} + 6r + 6 & 3r + 4 & 1 & 0 \\ 1 & 4r + 5 & 3r^{2} + 12r + 10 & 3r^{2} + 12r + 10 & 4r + 5 & 1 \end{matrix} ) .

We have

T_{n,k}(0) = \binom{n}{k},

hence for r = 0, the obtained number triangle is indeed Pascal’s triangle \underline{A007318}. The central coefficients of these triangles are given by

T_{2n,n}(r) = ∑_{k=0}^{n} \binom{n}{k}\binom{2n − k}{n}r^{k} = ∑_{k=0}^{n} \binom{n}{k}^{2}(r + 1)^{k}.

Similarly, we have that

T_{2n,n−1}(r) = ∑_{k=0}^{n−1} \binom{n − 1}{k}\binom{2n − k}{n − 1}r^{k} = ∑_{k=0}^{n} \binom{n − 1}{n − 1 − k}\binom{n + 1}{k}(r + 1)^{k}.

We define the generalized Catalan numbers associated with the Riordan array (\frac{1}{1−x}, \frac{x(1+rx)}{1−x}) to be the numbers

C_{n}(r) = T_{2n,n}(r) − T_{2n,n−1}(r).  (2)

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & r + 2 & 1 & 0 & 0 & 0 \\ 1 & 2r + 3 & 2r + 3 & 1 & 0 & 0 \\ 1 & 3r + 4 & r^{2} + 6r + 6 & 3r + 4 & 1 & 0 \\ 1 & 4r + 5 & 3r^{2} + 12r + 10 & 3r^{2} + 12r + 10 & 4r + 5 & 1 \end{matrix} ) .

The polynomial sequence C_{n}(r) begins

1, r + 1, r^{2} + 3r + 2, ….

Proposition 1. The generating function of C_{n}(r) is given by

c(x; r) = \frac{1 − rx − \sqrt{1 − 2x(r + 2) + r^{2}x^{2}}}{2x} .

Proof. By [5], we have that the generating function of T_{2n,n}(r) is given by

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

We now let

(\frac{1}{1 − x}, \frac{x(1 + rx)}{1 − x}) = (G(x), xF (x)).

Then

T_{2n,n−1} = [x^{2n}]G(x)(xF (x))^{n−1}

= [x^{n}]\frac{G(x)}{xF (x)^{2}} F (x)^{n+1}

= (n + 1)\frac{1}{n + 1}[x^{n}]\frac{G(x)}{xF (x)^{2}} F (x)^{n+1}

= [x^{n}]\frac{G(v(x))}{v(x)F (v(x))^{2}} v′(x)

where

v(x) = Rev (\frac{x}{F (x)}) ,

and where we have used Lagrange inversion [5, 18]. Now in this case we have

v(x) = Rev (\frac{x(1 − x)}{1 + rx}) = \frac{1 − rx − \sqrt{1 − 2x(r + 2) + r^{2}x^{2}}}{2} .

We find that the generating function of T_{2n,n−1}(r) is given by

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

Thus the generating function c(x; r) of C_{n}(r) is given by

\frac{1}{\sqrt{1 − 2x(r + 2) + r^{2}x^{2}}} − \frac{(1 − rx + \sqrt{1 − 2x(r + 2) + r^{2}x^{2}})^{2}}{4x\sqrt{1 − 2x(r + 2) + r^{2}x^{2}}} ,

or

c(x; r) = \frac{1 − rx − \sqrt{1 − 2x(r + 2) + r^{2}x^{2}}}{2x} .

Corollary 2. We have

c(x; r) = \frac{1}{1 − rx}c (\frac{x}{(1 − rx)^{2}} ) .

Proof. Expansion shows that both forms are equal.

Corollary 3.

C_{n}(r) = ∑_{k=0}^{n} \binom{n + k}{2k}r^{n−k}C_{k}.  (3)

Proof. We have

c(x; r) = \frac{1}{1 − rx}c (\frac{x}{(1 − rx)^{2}} ) = (\frac{1}{1 − rx}, \frac{x}{(1 − rx)^{2}} ) · c(x).

The Riordan array (\frac{1}{1−rx}, \frac{x}{(1−rx)^{2}} ) has (n, k)-th term \binom{n+k}{2k}r^{n−k}, whence the result.

We note that the (large) Schroeder numbers \underline{A006318} S_{n} have the formula

S_{n} = ∑_{k=0}^{n} \binom{n + k}{2k}C_{k}.

Thus there is justification for calling our numbers generalized Schroeder numbers. Nevertheless, we shall continue to call them generalized Catalan numbers in this note (and consequently we regard the large Schroeder numbers as elements of this family, corresponding to r = 1). The numbers C_{n}(r) count the number of Schroeder paths of semi-length n where the level steps have r possible colors (see \underline{A006318}, \underline{A047891}, \underline{A082298}, \underline{A082301} and \underline{A082302}).

Corollary 4. We have that c(x; r) has the following continued fraction expansion.

c(x; r) = \frac{1}{1 − rx − \frac{x}{1 − rx − \frac{x}{1 − rx − ⋯}}}.

Proof. We solve the equation

u = \frac{1}{1 − rx − xu}

to find that u(x) = c(x; r).

Corollary 5. We have that c(x; r) has the following continued fraction expansion.

c(x; r) = \frac{1}{1 − \frac{x(r + 1)}{1 − \frac{x}{1 − \frac{x(r + 1)}{1 − \frac{x}{1 − ⋯}}}}}.

Proof. We solve the equation

u = \frac{1}{1 − \frac{x(r + 1)}{1 − xu}}

to find that u(x) = c(x; r). Corollary 6. We have

C_{n}(r) = ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{2n − k}{n}\binom{n}{k}r^{k}.  (4)

Proof. The number triangle \underline{A060693} with general element \frac{1}{n−k+1} \binom{2n−k}{n}\binom{n}{k} is equal to

[1, 1, 1, …] Δ [1, 0, 1, 0, …]

in the Deléham notation [6]. The result follows from the previous result. Corollary 7. Let

N_{n,k} = \frac{1}{n + 1}\binom{n + 1}{k}\binom{n − 1}{n − k} = 0^{n+k} + \frac{1}{n + 0^{nk}} \binom{n}{k}\binom{n}{k − 1}

denote the (n, k)-th element of the Narayana triangle that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 3 & 1 & 0 & 0 & 0 \\ 0 & 1 & 6 & 6 & 1 & 0 & 0 \\ 0 & 1 & 10 & 20 & 10 & 1 & 0 \\ 0 & 1 & 15 & 50 & 50 & 15 & 1 \end{matrix} ) .

Then we have

C_{n}(r) = ∑_{k=0} N_{n,k}(r + 1)^{k}.  (5)

Proof. In effect, the number triangle \underline{A060693} is the product of the Narayana triangle (N_{n,k}) and the binomial triangle. Proposition 8. We have

c(x; r) = \frac{1}{x}Rev (\frac{x(1 − x)}{1 + rx}) .

Proof. Solving the equation

\frac{u(1 − u)}{1 + ru} = x

we find that the branch with u(0) = 0 gives us

u(x) = Rev (\frac{x(1 − x)}{1 + rx}) = \frac{1 − rx − \sqrt{1 − 2x(r + 2) + r^{2}x^{2}}}{2} .

Corollary 9. We have

C_{n}(r) = \frac{1}{n + 1} ∑_{k=0}^{n} \binom{n + 1}{k}\binom{2n − k}{n}r^{k}.

Proof. We have

[x^{n}]\frac{1}{x}Rev (\frac{x(1 − x)}{1 + rx}) = [x^{n+1}]Rev (\frac{x(1 − x)}{1 + rx})

= \frac{1}{n + 1}[x^{n}] (\frac{1 + rx}{1 − x})^{n+1}

by Lagrange inversion. The result follows from this.

We note that since

\binom{n + 1}{k} = \frac{n + 1}{n − k + 1}\binom{n}{k},

we retrieve the result that

C_{n}(r) = ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{n}{k}\binom{2n − k}{n}r^{k}.  (6)

3 Orthogonal polynomials and generalized Catalan numbers

We recall that a family of polynomials P_{n}(x) = ∑_{k=0}^{n} p_{n,k}x^{k} is a family of orthogonal polynomials if it satisfies a three term recurrence

P_{n}(x) = (x − α_{n})P_{n−1} − β_{n}P_{n−2},

for suitable parameters α_{n} and β_{n}, and suitable initial conditions such as P_{−1}(x) = 0 and P_{0}(x) = 1, or P_{0}(x) = 1 and P_{1}(x) = x − a.

The coefficient array (p_{n,k}) will be a Riordan array [3] if and only if it is of the form

(\frac{1 − λx − μx}{1 + ax + bx^{2}} , \frac{x}{1 + ax + bx^{2}} ) ,

in which case we have

P_{n}(x) = (x − a)P_{n−1}(x) − bP_{n−2}(x),

with P_{0}(x) = 1, P_{1}(x) = x − a − λ, and P_{2}(x) = x^{2} − (2a + λ)x + a^{2} + aλ − b − μ. This is equivalent to saying that α_{n} is the sequence a + λ, a, a, a, … and β_{n} is the sequence 0, b + λ, b, b, b, …. Equivalently, this is the case if the coefficient array O = (p_{n,k}) satisfies the following. Letting M = O^{−1}, we require that the production matrix P = M^{−1}\overline{M} be of the form

( \begin{matrix}a + λ & 1 & 0 & 0 & 0 & 0 & 0 \\ b + μ & a & 1 & 0 & 0 & 0 & 0 \\ 0 & b & a & 1 & 0 & 0 & 0 \\ 0 & 0 & b & a & 1 & 0 & 0 \\ 0 & 0 & 0 & b & a & 1 & 0 \\ 0 & 0 & 0 & 0 & b & a & 1 \\ 0 & 0 & 0 & 0 & 0 & b & a \end{matrix} ) .

Here, \overline{M} is the matrix M with its first row removed.

If this is the case, we call M the moment matrix of the family of orthogonal polynomials P_{n}(x) with coefficient array O = (p_{n,k}). The elements of the first column of M are called the moments of the family of orthogonal polynomials P_{n}(x).

With these preliminaries dealt with, we can now give the following result.

Proposition 10. The generalized Catalan numbers C_{n}(r) are the moments of the family of orthogonal polynomials whose coefficient array is given by the Riordan array

(\frac{1 + x}{1 + (r + 2)x + (r + 1)x^{2}} , \frac{x}{1 + (r + 2)x + (r + 1)x^{2}} ) .

Proof. We find that

(\frac{1 + x}{1 + (r + 2)x + (r + 1)x^{2}} , \frac{x}{1 + (r + 2)x + (r + 1)x^{2}} )^{−1}

= (c(x; r), \frac{1 − x(r + 2) − \sqrt{1 − 2x(r + 2) + r^{2}x^{2}}}{2x(r + 1)} ) .

The production matrix of the moment matrix (\frac{1+x}{1+(r+2)x+(r+1)x^{2}} , \frac{x}{1+(r+2)x+(r+1)x^{2}} )^{−1} begins

( \begin{matrix}r + 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ r + 1 & r + 2 & 1 & 0 & 0 & 0 & 0 \\ 0 & r + 1 & r + 2 & 1 & 0 & 0 & 0 \\ 0 & 0 & r + 1 & r + 2 & 1 & 0 & 0 \\ 0 & 0 & 0 & r + 1 & r + 2 & 1 & 0 \\ 0 & 0 & 0 & 0 & r + 1 & r + 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & r + 1 & r + 2 \end{matrix} ) .

Corollary 11. The Hankel transform of the generalized Catalan numbers C_{n}(r) is given by

h_{n}(r) = (r + 1)^{\binom{n+1}{2}}.

Corollary 12. We have the following integral representation of C_{n}(r).

C_{n}(r) = \frac{1}{π} ∫_{r+2−2\sqrt{r+1}}^{r+2+2\sqrt{r+1}} x^{n}\sqrt{\frac{−x^{2} + 2x(r + 2) − r^{2}}{2x}} dx

= \frac{1}{π} ∫_{r+2−2\sqrt{r+1}}^{r+2+2\sqrt{r+1}} x^{n} \frac{−(x − 2 − r − 2\sqrt{r + 1})(x − 2 − r + 2\sqrt{r + 1})}{2x} dx

We note that the density is of Marčenko-Pastur type [17, 28].

Proof. We apply the Stieltjes-Perron transform [14] to the generating function c(x; r) of C_{n}(r).

Example 13. We find that for the Catalan numbers C_{n}, we have the following well-known result.

C_{n} = \frac{1}{π} ∫_{0}^{4} x^{n} \frac{\sqrt{x(4 − x)}}{2x} dx.

Example 14. We find that for the large Schroeder numbers S_{n} we have the following integral representation.

S_{n} = \frac{1}{π} ∫_{3−2\sqrt{2}}^{3+2\sqrt{2}} x^{n} \frac{\sqrt{−x^{2} + 6x − 1}}{2x} dx

= \frac{1}{π} ∫_{3−2\sqrt{2}}^{3+2\sqrt{2}} x^{n} \frac{−(x − 3 − 2\sqrt{2})(x − 3 + 2\sqrt{2})}{2x} dx.

4 C_{n}(r) as row sums

The following result exhibits the generalized Catalan numbers C_{n}(r) as the row sums of a Riordan array.

Proposition 15. The generalized Catalan numbers C_{n}(r) are the row sums of the Riordan array

(\frac{1}{1 + rx}, \frac{x(1 − x)}{1 + rx})^{−1} .

.

Proof. We have that

(\frac{1}{1 + rx}, \frac{x(1 − x)}{1 + rx})^{−1} = (1 + rxc(x; r), xc(x; r)).

Then the row sums of this matrix are given by

\frac{1 + rxc(x; r)}{1 − xc(x; r)} = c(x; r).

We note that the production matrix of the Riordan array (\frac{1}{1+rx}, \frac{x(1−x)}{1+rx})^{−1} begins

( \begin{matrix}r & 1 & 0 & 0 & 0 & 0 \\ r & r + 1 & 1 & 0 & 0 & 0 \\ r & r + 1 & r + 1 & 1 & 0 & 0 \\ r & r + 1 & r + 1 & r + 1 & 1 & 0 \\ r & r + 1 & r + 1 & r + 1 & r + 1 & 1 \\ r & r + 1 & r + 1 & r + 1 & r + 1 & r + 1 \end{matrix} ) .

The first column elements of (\frac{1}{1+rx}, \frac{x(1−x)}{1+rx})^{−1} are of interest. We have seen that their generating function is 1 + rxc(x; r). We can express this generating function as a continued fraction. We have the following result.

Proposition 16. The generating function 1 + rxc(x; r) is equal to the following continued fraction.

\frac{1}{1 − rx − \frac{rx^{2}}{1 − (r + 2)x − \frac{(r + 1)x^{2}}{1 − (r + 2)x − \frac{(r + 1)x^{2}}{1 − (r + 2)x − ⋯}}}}.

Proof. We solve the equation

u = \frac{1}{1 − (r + 2)x − (r + 1)x^{2}u},

and then we calculate the generating function

\frac{1}{1 − rx − rx^{2}u}.

This is found to be equal to 1 + rxc(x; r).

This proposition says that the initial column of (\frac{1}{1+rx}, \frac{x(1−x)}{1+rx})^{−1} is the moment family for a family of orthogonal polynomials. In fact, we have the following result.

Proposition 17. The initial column of (\frac{1}{1+rx}, \frac{x(1−x)}{1+rx})^{−1} is the moment sequence for a family of orthogonal polynomials whose coefficient array is given by

(\frac{(1 + x)^{2}}{1 + (r + 2)x + (r + 1)x^{2}} , \frac{x}{1 + (r + 2)x + (r + 1)x^{2}} ) .

.

Proof. This follows since we have the following equality of Riordan arrays.

(\frac{1}{1 + rx}, \frac{x(1 − x)}{1 + rx})^{−1} · (1, \frac{x}{1 − x})

= (\frac{(1 + x)^{2}}{1 + (r + 2)x + (r + 1)x^{2}} , \frac{x}{1 + (r + 2)x + (r + 1)x^{2}} )^{−1} .

The production matrix for this last Riordan array begins

( \begin{matrix}r & 1 & 0 & 0 & 0 & 0 & 0 \\ r & r + 2 & 1 & 0 & 0 & 0 & 0 \\ 0 & r + 1 & r + 2 & 1 & 0 & 0 & 0 \\ 0 & 0 & r + 1 & r + 2 & 1 & 0 & 0 \\ 0 & 0 & 0 & r + 1 & r + 2 & 1 & 0 \\ 0 & 0 & 0 & 0 & r + 1 & r + 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & r + 1 & r + 2 \end{matrix} ) .

The initial column sequence with generating function 1 + rxc(x; r) has general element

r ∑_{k=0}^{n−1} \binom{n + k − 1}{2k}r^{n−k−1}C_{k} = ∑_{k=0}^{n−1} \binom{n + k − 1}{2k}r^{n−k}C_{k}.

Corollary 18. The Hankel transform of the initial column sequence with g.f. 1 + rxc(x; r) is given by

h_{n} = r^{n}(r + 1)^{\binom{n}{2}}.

5 Generalizations

We have seen that the generating function of C_{n}(r) is given by

c(x; r) = (\frac{1}{1 + rx}, \frac{x(1 − x)}{1 + rx})^{−1} · \frac{1}{1 − x}.

A natural generalization is to consider the generating function

c(x; r, s, y) = (\frac{1}{1 + rx}, \frac{x(1 − sx)}{1 + rx})^{−1} · \frac{1}{1 − yx}.

We find that

c(x; r, s, y) = \frac{2s + r − y − rx(y + r) − (y + r)\sqrt{1 − 2x(r + 2s) + r^{2}x^{2}}}{2(xy(y + r) − y + s)} .

This expands to give the sequence that begins

1, y + r, (y + r)(y + r + s), (y + r)(y^{2} + 2y(r + s) + r^{2} + 3rs + 2s^{2}), ….

The generating function can be expressed as

c(x; r, s, y) = \frac{−(r + s)}{rx(y + r) + y − r − 2s}c (\frac{(r + s)(x(y + r) − y + s)}{(rx(y + r) + y − r − 2s)^{2}} ) ,

which exhibits a link to the standard Catalan numbers C_{n}. Using Lagrange inversion to find the general term of the inverse Riordan array (\frac{1}{1+rx}, \frac{x(1−sx)}{1+rx})^{−1}, we find that

C_{n}(r, s, y) = ∑_{k=0}^{n} ( \frac{k + 0^{n+k}}{n + 0^{n}} ∑_{i=0}^{n} \binom{n}{i}\binom{2n − k − i − 1}{n − k − i}r^{i}s^{n−k−i} + \frac{r(k + 1)}{n + 0^{n}} ∑_{i=0}^{n} \binom{n}{i}\binom{2n − k − i − 2}{n − k − i − 1}r^{i}s^{n−k−i−1}) y^{k},

where we have used the notation C_{n}(r, s, y) to denote the generalized Catalan numbers with generating function c(x; r, s, y). Note that when y = 0 (and thus we are considering the first column of (\frac{1}{1+rx}, \frac{x(1−sx)}{1+rx})^{−1}) we have

C_{n}(r, s, 0) = 0^{n} + \frac{r}{n + 0^{n}} ∑_{i=0}^{n} \binom{n}{i}\binom{2n − i − 2}{n − i − 1}r^{i}s^{n−i−1}  (7)
= 0^{n} + ∑_{k=0}^{n−1} \binom{n + k − 1}{2k}r^{n−k}s^{k}C_{k}  (8)
= ∑_{k=0}^{n} \binom{n + k − 1}{2k}r^{n−k}s^{k}C_{k}.  (9)

Example 19. The sequence C_{n}(2, 3, 0) = ∑_{k=0}^{n} \binom{n+k−1}{2k}2^{n−k}3^{k}C_{k} begins

1, 2, 10, 80, 790, 8720, 103060, 1275680, ….

This is \underline{A152600}. Its Hankel transform is given by

h_{n} = 6^{n}15^{\binom{n}{2}}.

We have the following result.

Proposition 20. The sequence C_{n}(r, s, y) with generating function c(x; r, s, y) is the moment sequence for the family of orthogonal polynomials that have coefficient array given by the Riordan array

(\frac{1 + (2s − y)x + s(s − y)x^{2}}{1 + (r + 2s)x + s(r + s)x^{2}} , \frac{x}{1 + (r + 2s)x + s(r + s)x^{2}} ) .

Corollary 21. The Hankel transform of the generalized Catalan numbers with generating function c(x; r, s, y) is given by

h_{n} = (s(y + r))^{n}(s(r + s))^{\binom{n}{2}}.

Proof. This follows since we can show that the generating function c(x; r, s, y) is expressible as the Jacobi continued fraction

\frac{1}{1 − (r + y)x − \frac{s(r + y)x^{2}}{1 − (r + 2s)x − \frac{s(r + s)x^{2}}{1 − (r + 2s)x − \frac{s(r + s)x^{2}}{1 − ⋯}}}}.

Corollary 22. The generating function c(x; r, s, y) can be represented as the Stieltjes continued fraction

\frac{1}{1 − \frac{(r + y)x}{1 − \frac{sx}{1 − \frac{(r + s)x}{1 − \frac{sx}{1 − \frac{(r + s)x}{1 − ⋯}}}}}}.

Example 23. We consider the generating function c(x; 2, 1, −1). Thus we have that c(x; 2, 1, −1) is equal to

\frac{1}{1 − \frac{x}{1 − \frac{x}{1 − \frac{3x}{1 − \frac{x}{1 − \frac{3x}{1 − \frac{x}{1 − ⋯}}}}}}},

or equivalently

\frac{1}{1 − x − \frac{x^{2}}{1 − 4x − \frac{3x^{2}}{1 − 4x − \frac{3x^{2}}{1 − 4x − ⋯}}}}.

This generating function expands to give the sequence that begins

1, 1, 2, 7, 32, 166, 926, ….

The sequence 1, 2, 7, 32, 166, … is \underline{A108524} and it counts the number of ordered rooted trees with n generators. Alternatively it counts the number of Schroeder paths of semi-length n − 1 in which the level steps that are not on the horizontal axis come in 2 colors (Deutsch). This latter sequence has generating function

\frac{1}{1 − x − \frac{x}{1 − 2x − \frac{x}{1 − 2x − ⋯}}}.

Proposition 24. The generating function c(x; r, s, y) is equal to the continued fraction

\frac{1}{1 − \frac{r(r+y)}{r+s}x − \frac{\frac{s(r+y)}{r+s}x}{1 − rx − \frac{sx}{1 − rx − \frac{sx}{1 − rx − ⋯}}}}.

Proof. We let

v = \frac{1}{1 − rx − sxv} .

Then the generating function defined by the continued fraction is given by

\frac{1}{1 − \frac{r(r+y)}{r+s}x − \frac{s(r+y)}{r+s}xv} .

This simplifies to give c(x; r, s, y). Example 25. The generating function c(x; 1, 2, 3) expands to give the sequence that begins

1, 4, 24, 168, 1272, 10104, 82920, 696840, ….

This sequence thus has generating function

\frac{1}{1 − \frac{4}{3}x − \frac{\frac{8}{3}x}{1 − x − \frac{2x}{1 − x − \frac{2x}{1 − x − ⋯}}}}.

Example 26. The generating function c(x; 2, 2, 0) expands to give the sequence that begins

1, 2, 8, 48, 352, 2880, 25216, 231168, ….

This sequence thus has generating function

\frac{1}{1 − \frac{2x}{1 − \frac{2x}{1 − \frac{4x}{1 − \frac{2x}{1 − \frac{4x}{1 − ⋯}}}}}},

or

\frac{1}{1 − x − \frac{x}{1 − 2x − \frac{2x}{1 − 2x − \frac{2x}{1 − 2x − ⋯}}}}.

Equivalently, this is equal to

\frac{1}{1 − 2x − \frac{4x^{2}}{1 − 6x − \frac{8x^{2}}{1 − 6x − \frac{8x^{2}}{1 − 6x − ⋯}}}}.

The sequence 1, 1, 2, 8, 48, 352, … is \underline{A054726}, which counts the number of ways of drawing non-crossing chords between n points on a circle. The generating function of this sequence can be expressed as the continued fractions

\frac{1}{1 − x − \frac{x^{2}}{1 − 5x − \frac{8x^{2}}{1 − 6x − \frac{8x^{2}}{1 − 6x − ⋯}}}},

\frac{1}{1 − \frac{x}{1 − \frac{2x}{1 − 2x − \frac{2x}{1 − 2x − ⋯}}}},

or

\frac{1}{1 − \frac{x}{1 − \frac{x}{1 − \frac{4x}{1 − \frac{2x}{1 − \frac{4x}{1 − \frac{2x}{1 − ⋯}}}}}}}.

Corollary 27. We have

C_{n}(r, s, s) = ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{2n − k}{n}\binom{n}{k}s^{n−k}r^{k}.  (10)

Proof. The number triangle \frac{1}{n−k+1} \binom{2n−k}{n}\binom{n}{k} \underline{A060693} is equal to

[1, 1, 1, …] Δ [1, 0, 1, 0, …].

This begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 5 & 10 & 6 & 1 & 0 & 0 \\ 14 & 35 & 30 & 10 & 1 & 0 \\ 42 & 126 & 140 & 70 & 15 & 1 \end{matrix} ) .

Then \frac{1}{n−k+1} \binom{2n−k}{n}\binom{n}{k}s^{n−k}r^{k} corresponds to

[s, s, s, …] Δ [r, 0, r, 0, …],

or the generating function

\frac{1}{1 − \frac{(s + r)x}{1 − \frac{sx}{1 − \frac{(s + r)x}{1 − \frac{sx}{1 − ⋯}}}}}.

This is c(x; r, s, s).

Equivalently, we have

C_{n}(r, s, s) = ∑_{k=0}^{n} \frac{1}{k + 1}\binom{n + k}{n}\binom{n}{k}r^{n−k}s^{k},  (11)

where the matrix (\frac{1}{k+1} \binom{n+k}{n}\binom{n}{k}) is \underline{A088617} which counts Schroeder paths of semi-length n with k up steps.

Corollary 28. We have

C_{n}(r, s, s) = ∑_{k=0}^{n} N_{n,k}(r + s)^{k}s^{n−k}.  (12)

Proof. This follows from the continued fraction expression above.

Corollary 29. We have that C_{n}(r, s, s) = ∑_{k=0}^{n} \binom{n+k}{2k}r^{n−k}s^{k}C_{k} is the moment sequence for the family of orthogonal polynomials with coefficient matrix given by the Riordan array

(\frac{1 + sx}{1 + (r + 2s)x + s(r + s)x^{2}} , \frac{x}{1 + (r + 2s)x + s(r + s)x^{2}} ) .

In similar fashion, we can establish the following with regard to C_{n}(r, s, s) = [x^{n}]c(x; r, s, s). We have

c(x; r, s, s) = \frac{1}{1 − rx}c (\frac{sx}{(1 − rx)^{2}} ) = \frac{1 − rx − \sqrt{1 − 2x(r + 2s) + r^{2}x^{2}}}{2sx} = \frac{1}{x}Rev\frac{x(1 − sx)}{1 + rx}.

We also have that C_{n}(r, s, s) are the row sums of the Riordan array

(\frac{1 − x(s + 1)}{(1 − x)(1 + (r − 1)x)}, \frac{x(1 − x(s + 1))}{(1 − x)(1 + (r − 1)x)})^{−1} .

Equivalently,

c(x; r, s, s) = (\frac{1 − x(s + 1)}{(1 − x)(1 + (r − 1)x)}, \frac{x(1 − x(s + 1))}{(1 − x)(1 + (r − 1)x)})^{−1} · \frac{1}{1 − x}.

The numbers C_{n}(r, s, s) count Schroeder paths of semi-length n with r possible colors for the level steps and s possible colors for the up steps [19]. For instance, \underline{A156017} is the sequence that begins

1, 4, 24, 176, 1440, 12608, 115584, 1095424, 10646016, …

with general term

∑_{k=0}^{n} \binom{n + k}{2k}2^{n−k}2^{k} = ∑_{k=0}^{n} N_{n,k}2^{n+k} = 2^{n}S_{n},

which counts Schroeder paths of semi-length n with 2 possible colors for the level steps and 2 possible colors for the up steps. Its generating function can by represented as the continued fraction

\frac{1}{1 − 2x − \frac{2x}{1 − 2x − \frac{2x}{1 − 2x − ⋯}}}.

(An alternative interpretation in terms of operads can be given: the sequence counts the number of recursively defined red-white trees [9]).

Example 30. The sequences C_{n}(1, s, s) = ∑_{k=0}^{n} \binom{n+k}{2k}s^{k}C_{k} count Schroeder paths of semilength n where the up steps can have s colors. For s = 1 … 4 we obtain sequences \underline{A006318}, \underline{A103210}, \underline{A103211}, and \underline{A133305}, which begin respectively,

1, 2, 6, 22, 90, 394, 1806, …,
1, 3, 15, 93, 645, 4791, 37275, …,
1, 4, 28, 244, 2380, 24868, 272188, …,

and

1, 5, 45, 505, 6345, 85405, 1204245, ….

The sequence 1, 5, 45, … then has generating function

\frac{1}{1 − \frac{5x}{1 − \frac{4x}{1 − \frac{5x}{1 − \frac{4x}{1 − ⋯}}}}},

Figure 1: The 15 Schroeder paths of semi-length 2 with 2 up-colors

or equivalently

\frac{1}{1 − 5x − \frac{20x^{2}}{1 − 9x − \frac{20x^{2}}{1 − 9x − ⋯}}}.

These sequences also count the first homogeneous components of the operad As(Q) [12], where Q is the trivial poset on the set [s + 1], and As is a functor from the category of finite posets to the category of nonsymmetric binary and quadratic operads defined in [12].

Proposition 31. The generating function c(x; r, s, s) can be expressed as the continued fraction

\frac{1}{1 − rx − \frac{sx}{1 − rx − \frac{sx}{1 − rx − ⋯}}}.

Proof. We have

c(x; r, s, y) = \frac{2s + r − y − rx(y + r) − (y + r)\sqrt{1 − 2x(r + 2s) + r^{2}x^{2}}}{2(xy(y + r) − y + s)} .

Thus

c(x; r, s, s) = \frac{1 − rx − \sqrt{1 − 2(r + 2s)x + r^{2}x^{2}}}{2sx} .

Solving the equation

u = \frac{1}{1 − rx − sxu}

shows that u(x) = c(x; r, s, s).

This type of continued fraction is a T -fraction, or Thron-fraction [19, 20].

We have the following integral representation for the moments C_{n}(r, s, s).

Proposition 32. We have

C_{n}(r, s, s) = \frac{1}{2π} ∫_{r+2s−2\sqrt{s(r+s)}}^{r+2s+2\sqrt{s(r+s)}} x^{n} \frac{\sqrt{−x^{2} + 2x(r + 2s) − r^{2}}}{x} dx.

Proof. We apply the Stieltjes-Perron transform to the generating function c(x; r, s, s).

Example 33. The sequence C_{n}(2, 3, 3) = ∑_{k=0}^{n} \binom{n+k}{2k}C_{k}2^{n−k}3^{k} = ∑_{k=0}^{n} N_{n,k}5^{k}3^{n−k} \underline{A152601}, which begins

1, 5, 40, 395, 4360, 51530, 637840, 8163095, …,

has integral representation

C_{n}(2, 3, 3) = \frac{1}{2π} ∫_{8−2\sqrt{15}}^{8+2\sqrt{15}} x^{n} \frac{\sqrt{4(4x − 1) − x^{2}}}{3x} dx.

The generating function of this sequence can be represented as the continued fraction

\frac{1}{1 − \frac{5x}{1 − \frac{3x}{1 − \frac{5x}{1 − \frac{3x}{1 − ⋯}}}}}.

We end this section by gathering all the expressions for the generalized Catalan numbers C_{n}(r, s, s). We have

C_{n}(r, s, s) = ∑_{k=0}^{n} N_{n,k}(r + s)^{k}s^{n−k}

= ∑_{k=0}^{n} N_{n,k}^{rev}(r + s)^{n−k}s^{k}

= ∑_{k=0}^{n} \binom{n + k}{2k}C_{k}r^{n−k}s^{k}

= ∑_{k=0}^{n} \binom{2n − k}{k}C_{n−k}r^{k}s^{n−k}

= ∑_{k=0}^{n} \frac{1}{k + 1}\binom{n + k}{n}\binom{n}{k}r^{n−k}s^{k}

= ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{2n − k}{n}\binom{n}{k}r^{k}s^{n−k}

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

= \frac{1}{n + 1} ∑_{k=0}^{n} \binom{n − 1}{n − k}\binom{n + k}{k}(r + s)^{k}(−s)^{n−k}.

For instance, the coefficient array for the last equality begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 & 0 & 0 & 0 \\ 0 & 1 & 5 & 5 & 0 & 0 & 0 \\ 0 & 1 & 9 & 21 & 14 & 0 & 0 \\ 0 & 1 & 14 & 56 & 84 & 42 & 0 \\ 0 & 1 & 20 & 120 & 300 & 330 & 132 \end{matrix} ) .

This is \underline{A086810}. The coefficient triangle N_{n,k}^{rev} is the reversal of the Narayana triangle N_{n,k}. We have

N^{rev}_{n,k} = 0^{n+k} + \frac{n − k}{(n + 0^{n})(k + 1)}\binom{n}{k}^{2}.

This is the triangle \underline{A131198}, which in the Deléham notation is

[1, 0, 1, 0, 1, 0, …] Δ [0, 1, 0, 1, 0, …].

Example 34. We have

∑_{k=0}^{n} \binom{n + k}{2k}(s + 1)^{n−k}(s − 1)^{k} = ∑_{k=0}^{n} N_{n,k}(2s)^{k}(s − 1)^{n−k}.

For s = 2, we get the sequence ∑_{k=0}^{n} \binom{n+k}{2k}C_{k}3^{n−k} = ∑_{k=0}^{n} N_{n,k}4^{k} which begins

1, 4, 20, 116, 740, 5028, 35700, 261780, 1967300, ….

This is \underline{A082298}, which counts Schroeder paths of semi-length n in which the level steps can have any of 3 colors. For s = 3, we obtain the sequence

∑_{k=0}^{n} \binom{n + k}{2k}C_{k}4^{n−k}2^{k} = ∑_{k=0}^{n} N_{n,k}6^{k}2^{n−k}

which begins

1, 6, 48, 456, 4800, 53952, 634368, ….

This sequence counts Schroeder paths of semi-length n in which the level steps can have any of 4 colors and the up steps have 2 colors.

We have remarked that

c(x; r, s, s) = \frac{1}{x}Rev (\frac{x(1 − sx)}{1 + rx}) .

This suggests the following generalization. We define č(x; r, s, t) to be the generating function

č(x; r, s, t) = \frac{1}{x}Rev (\frac{x(1 − sx)}{1 + rx + tx^{2}} ) .

We then define the sequence Č_{n}(r, s, t) = [x^{n}]č(x; r, s, t). This sequence begins

1, r + s, r^{2} + 3rs + 2s^{2} + t, r^{3} + 6r^{2}s + r(10s^{2} + 3t) + s(5s^{2} + 4t), ….

We have

[x^{n}]Rev (\frac{x(1 − sx)}{1 + rx + tx^{2}} ) = \frac{1}{n}[x^{n−1}] (\frac{1 + rx + tx^{2}}{1 − sx} )^{n} ,

which gives us the following expression for Č_{n}(r, s, t).

Proposition 35. We have

č(x; r, s, t) = \frac{1 − rx − \sqrt{1 − 2(r + 2s)x + (r^{2} − 4t)x^{2}}}{2(s + tx)} ,

and

Č_{n}(r, s, t) = \frac{1}{n + 1} ∑_{k=0}^{n+1} \binom{n + 1}{k} ∑_{j=0}^{k} \binom{k}{j}\binom{2n − k − j}{n − k − j}t^{j}r^{k−j}s^{n−k−j}.  (13)

Corollary 36. We have

č(x; r, s, t) = \frac{1}{1 − rx}c (\frac{x(s + tx)}{(1 − rx)^{2}}) ,

and

Č_{n}(r, s, t) = ∑_{k=0}^{n} ∑_{j=0}^{k} \binom{k}{j}\binom{n + k − j}{n − k − j}r^{n−k−j}t^{j}s^{k−j}C_{k}.  (14)

Proof. The equality of the two expressions for the generating function can be seen by expansion of the latter expression. We then use the expression for the general element of the Riordan array (\frac{1}{1−rx}, \frac{x(s+tx)}{(1−rx)^{2}}) to obtain the second expression for Č_{n}(r, s, t).

An immediate consequence of this corollary is that we have the following continued fraction expression for the generating function č(x; r, s, t).

\frac{1}{1 − rx − \frac{x(s + tx)}{1 − rx − \frac{x(s + tx)}{1 − rx − ⋯}}}.

Proposition 37. The generating function č(x; r, s, t) of the generalized Catalan numbers Č_{n}(r, s, t) can be expressed as the Jacobi continued fraction

\frac{1}{1 − (r + s)x − \frac{(s(r + s) + t)x^{2}}{1 − (r + 2s)x − \frac{(s(r + s) + t)x^{2}}{1 − (r + 2s)x − ⋯}}}.

Proof. We solve the equation

u = \frac{1}{1 − (r + 2s)x − (s(r + s) + t)x^{2}u},

and then we verify that č(x; r, s, t) = \frac{1}{1−(r+s)x−(s(r+s)+t)x^{2}u}.

Corollary 38. The Hankel transform of the generalized Catalan numbers Č_{n}(r, s, t) is given by

h_{n} = (s(r + s) + t)^{\binom{n+1}{2}}.

Proposition 39. The sequence Č_{n}(r, s, t) is the moment sequence of the family of orthogonal polynomials whose coefficient array is given by the Riordan array

(\frac{1 − sx}{1 + (r + 2s)x + (t + s(r + s))x^{2}} , \frac{x}{1 + (r + 2s)x + (t + s(r + s))x^{2}} ) .

Proof. Using the theory of Riordan arrays, it is direct to show that the initial column of the inverse matrix has generating function given by č(x; r, s, t). By its form, the above Riordan array is the coefficient array of a family of orthogonal polynomials.

We can use the generating function and the Stieltjes-Perron transform to find an integral representation of this moment sequence.

Proposition 40. We have the following integral representation for the sequence Č_{n}(r, s, t).

Č_{n}(r, s, t) = \frac{1}{π} ∫_{r+2s−2\sqrt{t+s(r+s)}}^{r+2s+2\sqrt{t+s(r+s)}} x^{n} \frac{\sqrt{−x^{2} + 2(r + 2s)x − r^{2} + 4t}}{2(sx + t)} dx.

Example 41. We have

Č_{n}(1, 1, 1) = \frac{1}{π} ∫_{3−2\sqrt{3}}^{2+2\sqrt{3}} x^{n} \frac{\sqrt{3(2x + 1) − x^{2}}}{2(x + 1)} dx.

This sequence \underline{A064641} begins

1, 2, 7, 29, 133, 650, 3319, 17498, 94525, ….

We have

Č_{n}(2, 2, 1) = \frac{1}{π} ∫_{0}^{12} x^{n} \frac{\sqrt{x(12 − x)}}{2(2x + 1)} dx.

This sequence \underline{A064063}(n + 1) begins

1, 4, 25, 190, 1606, 14506, 137089, 1338790, 13403950, ….

We have

C_{n}(r, s, s) = Č_{n}(r, s, 0).

The numbers

Č_{n}(r, 0, t) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k}r^{n−2k}t^{k}

count Motzkin paths where the level steps have r colors and the up steps have t colors.

6 The generalized Catalan numbers C̃_{n}(r, s, y).

In this section, we consider the generalized Catalan numbers C̃_{n}(r, s, y) whose generating function is given by

(\frac{1 − x(s + 1)}{(1 − x)(1 + (r − 1)x)}, \frac{x(1 − x(s + 1))}{(1 − x)(1 + (r − 1)x)})^{−1} · \frac{1}{1 − yx}.

These generalized Catalan numbers are the moments for the family of orthogonal polynomials whose coefficient matrix is given by

(\frac{1 + (1 + s − y)x}{1 + (r + 2s)x + s(r + s)x^{2}} , \frac{x}{1 + (r + 2s)x + s(r + s)x^{2}} ) .

Their generating function can be expressed as the Jacobi continued fraction

J (y + r + s − 1, r + 2s, r + 2s, …; s(r + s), s(r + s), …).

When y = s + 1, we obtain the generating function

J (r + 2s, r + 2s, r + 2s, …; s(r + s), s(r + s), …),

or u(x) where

u(x) = \frac{1}{1 + (r + 2s)x + s(r + s)x^{2}u}.

This gives us

u(x) = \frac{1 − (r + 2s)x − \sqrt{1 − 2(r + 2s)x + r^{2}x^{2}}}{2sx^{2}(r + s)} = \frac{1}{1 − (r + 2s)x}c (\frac{x^{2}s(r + s)}{(1 − (r + 2s)x)^{2}} ) .

From this we deduce that the generalized Catalan numbers of this section, for y = s + 1, are given by

C̃_{n}(r, s, s + 1) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}(r + 2s)^{n−2k}(s(r + s))^{k}C_{k}  (15)

= ∑_{k=0}^{n} \binom{n + 1}{k}\binom{2n − k + 2}{n − k}s^{n−k}r^{k}.  (16)

Note that when both r + 2s = 1 and s(r + s) = 1, we obtain the Motzkin numbers. This occurs when

r = 1 − 2s and s = \frac{1 ± i\sqrt{3}}{2}.

For instance, we have C̃_{n}(\sqrt{3}i, \frac{1}{2} − \frac{\sqrt{3}i}{2}, \frac{3}{2} − \frac{\sqrt{3}i}{2}) = M_{n}. We have the integral representation

C̃(r, s, s + 1) = \frac{1}{π} ∫_{r+2s−2\sqrt{s(r+s)}}^{r+2s+2\sqrt{s(r+s))}} x^{n} \frac{\sqrt{−x^{2} + 2(r + 2s)x − r^{2}}}{2s(r + s)} dx.

Example 42. The generalized Catalan sequence C̃_{n}(2, 3, 4), which begins

1, 8, 79, 872, 10306, 127568, 1632619, …

is given by

C̃(2, 3, 4) = \frac{1}{π} ∫_{8−2\sqrt{15}}^{8+\sqrt{15}} x^{n} \frac{\sqrt{4(4x − 1) − x^{2}}}{30} dx.

In the general case of C̃_{n}(r, s, y), we see that its generating function will be given by

\frac{1}{1 − (y + r + s − 1)x − s(r + s)x^{2}u(x)} = \frac{2}{1 − (2y + r − 2)x + \sqrt{1 − 2(r + 2s)x + r^{2}x^{2}}} .

This may be expressed as

\frac{1}{1 − (r + 2y − 2)x}c (\frac{x(1 + s − y + (1 − r + (r − 2)y + y^{2})x)}{(1 − (r + 2y − 2)x)^{2}}) .

Using the Stieltjes-Perron transform, we find that

C̃_{n}(r, s, y) = \frac{1}{π} ∫_{r+2s−2\sqrt{s(r+s)}}^{r+2s+2\sqrt{s(r+s)}} x^{n} \frac{\sqrt{−x^{2} + 2(r + 2s)x − r^{2}}}{2(1 − r + y(r − 2) + y^{2} + (1 + s − y)x)} dx.

Example 43. We consider the case of (r, s, y) = (1, 2, 3). Then C̃_{n}(1, 2, 3) is \underline{A269730} which begins

1, 5, 31, 215, 1597, 12425, 99955, 824675, 6939769, ….

Then

C̃_{n}(1, 2, 3) = \frac{1}{π} ∫_{5−2\sqrt{6}}^{5+2\sqrt{6}} x^{n} \frac{−x^{2} + 10x − 1}{12} dx.

Other expressions for C̃_{n}(1, 2, 3) are given by

C̃_{n}(1, 2, 3) = ∑_{k=0}^{n} \frac{1}{k + 1}\binom{n}{k}\binom{n + k + 2}{k}2^{k} = ∑_{k=0}^{n} Ñ_{n,k}2^{n−k}3^{k},

where Ñ_{n,k} = \frac{1}{k+1} \binom{n}{k}\binom{n+1}{k} are the (palindromic) Narayana numbers, and the coefficient array (\frac{1}{k+1} \binom{n}{k}\binom{n+k+2}{k}) is \underline{A033282}, which gives the number of diagonal dissections of a convex ngon into k + 1 regions. In this case, the sequence C̃_{n}(1, 2, 3) or \underline{A269730} gives the dimensions of the 2-polytridendriform operad TDendr_{2} [11]. We note that the generating function of this sequence is f(−x), where

f(x) = \frac{1}{x}Rev (\frac{1}{1 − 3x} − \frac{1}{1 − 2x}) ,

(remark by Gheorghe Coserea).

In terms of Riordan arrays, the generating function for this sequence is simply given by

(\frac{1}{1 − 5x}, \frac{6x^{2}}{(1 − 5x)^{2}} ) · c(x).

Thus we have

C̃_{n}(1, 2, 3) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}5^{n−2k}6^{k}C_{k} = ∑_{k=0}^{n} Ñ_{n,k}2^{k}3^{n−k}.

Example 44. We now look at (r, s, y) = (2, 2, 3). Then we find that C̃(2, 2, 3), which begins

1, 6, 44, 360, 3152, 28896, 273856, 2661504, 26380544, …

is \underline{A090442}. We have

C̃(2, 2, 3) = \frac{1}{π} ∫_{6−4\sqrt{2}}^{6+4\sqrt{2}} x^{n} \frac{\sqrt{4(3x − 1) − x^{2}}}{16} dx.

In terms of Riordan arrays, the generating function for this sequence is simply given by

(\frac{1}{1 − 6x}, \frac{8x^{2}}{(1 − 6x)^{2}} ) · c(x).

Thus we have

C̃_{n}(2, 2, 3) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}6^{n−2k}8^{k}C_{k} = ∑_{k=0}^{n} Ñ_{n,k}2^{k}4^{n−k}.

This sequence gives the row sums of the scaling \underline{A090452} of the \{3, 2\}-Stirling2 array \underline{A078740}.

Example 45. We have that C̃_{n}(−1, 4, 5) = C̃_{n}(1, 3, 4). This sequence begins

1, 7, 61, 595, 6217, 68047, 770149, …

with generating function

(\frac{1}{1 − 7x}, \frac{12x^{2}}{(1 − 7x)^{2}} ) · c(x),

and hence the general term is given by

C̃_{n}(1, 3, 4) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}7^{n−2k}12^{k}C_{k} = ∑_{k=0}^{n} Ñ_{n,k}3^{k}4^{n−k}.

This sequence is \underline{A269731}, which gives the dimensions of the 3-polytridendriform operad TDendr_{3} [11]. We note that the generating function of this sequence is f(−x), where

f(x) = \frac{1}{x}Rev (\frac{1}{1 − 4x} − \frac{1}{1 − 3x}) .

Lemma 46. We have

\frac{1}{x}Rev (\frac{1}{1 + rx} − \frac{1}{1 + (r + 1)x}) = (\frac{1}{1 − (2r + 1)x}, \frac{x^{2}r(r + 1)}{(1 − (2r + 1)x)^{2}} ) · c(x).

It follows that

[x^{n}]\frac{1}{x}Rev (\frac{1}{1 + rx} − \frac{1}{1 + (r + 1)x}) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}(r(r + 1))^{k}(2r + 1)^{n−2k}C_{k}

= ∑_{k=0}^{n} \frac{1}{k + 1}\binom{n}{k}\binom{n + k + 2}{k}r^{k}.

More generally, we have the following. Lemma 47.

[x^{n}]\frac{1}{x}Rev (\frac{1}{s − r} (\frac{1}{1 + rx} − \frac{1}{1 + sx})) = ∑_{k=0}^{n} Ñ_{n,k}s^{n−k}r^{k}.

Proof. We find that

\frac{1}{x}Rev (\frac{1}{s − r} (\frac{1}{1 + rx} − \frac{1}{1 + sx})) = \frac{1}{1 − (r + s)x}c (\frac{rsx^{2}}{(1 − (r + s)x)^{2}} ) .

This expands to give the sequence

∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}(rs)^{k}(r + s)^{n−2k}C_{k} = ∑_{k=0}^{n} Ñ_{n,k}s^{n−k}r^{k}.

We have seen that in the general case of C̃_{n}(r, s, y), its generating function will be given by

\frac{1}{1 − (y + r + s − 1)x − s(r + s)x^{2}u(x)} = \frac{2}{1 − (2y + r − 2)x + \sqrt{1 − 2(r + 2s)x + r^{2}x^{2}}} .

This may be expressed as

\frac{1}{1 − (r + 2y − 2)x}c (\frac{x(1 + s − y + (1 − r + (r − 2)y + y^{2})x)}{(1 − (r + 2y − 2)x)^{2}}) .

We now let y = s + 1. Then C̃_{n}(r, s, s + 1) will have as generating function

(\frac{1}{1 − (r + 2s)x}, \frac{x^{2}s(r + s)}{(1 − (r + 2s)x)^{2}} ) · c(x),

which means that

C̃_{n}(r, s, s + 1) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}(s(r + s))^{k}(r + 2s)^{n−2k}C_{k} = ∑_{k=0}^{n} Ñ_{n,k}s^{k}(r + s)^{n−k}.

As a consequence, we get the following result.

Proposition 48. We have

[x^{n}]\frac{1}{x}Rev (\frac{1}{s − r} (\frac{1}{1 + rx} − \frac{1}{1 + sx})) = C̃_{n}(s − r, r, r + 1).

Thus we have

C̃_{n}(s − r, r, r + 1) = ∑_{k=0}^{n} Ñ_{n,k}s^{n−k}r^{k}.

Example 49. In this example, we begin by noting that the generating function

\frac{1}{x}Rev (\frac{x}{1 + rx + sx^{2}} )

expands to give the sequence

∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k}r^{n−2k}s^{k}.

The generating function of this sequence can be represented by the continued fraction

\frac{1}{1 − rx − \frac{sx^{2}}{1 − rx − \frac{sx^{2}}{1 − rx − ⋯}}}.

We now substitute C_{n}(v, w, w) for C_{n} into this expression. Thus we consider the sequence ˜C̃_{n}(r, s, v, w) with general term

˜C̃_{n}(r, s, v, w) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k}(v, w, w)r^{n−2k}s^{k}.  (17)

This sequence depends on the four parameters r, s, v, w. We find that this sequence has a generating function given by

\frac{1 − rx}{1 − 2rx − x^{2}(sv − r^{2})}c (\frac{x^{2}sw(1 − rx)^{2}}{(1 − 2rx − x^{2}(sv − r^{2}))^{2}} ) .

Equivalently, this is given by the continued fraction

\frac{1}{1 − rx − \frac{s(v + w)x^{2}}{1 − rx − \frac{swx^{2}}{1 − rx − \frac{s(v + w)x^{2}}{1 − rx − \frac{swx^{2}}{1 − rx − ⋯}}}}}.

We find that

˜C̃_{n}(r, s, v, w) = ∑_{k=0}^{n} ∑_{j=0}^{2k+1} \binom{2k + 1}{j}(−r)^{j} ∑_{i=0}^{n−2k−j} \binom{2k + i}{i}\binom{i}{n − 2k − j − i}(sv − r^{2})^{n−2k−j−i}(2r)^{2i+2k+j−n}s^{k}w^{k}C_{k}.

The Hankel transform of this sequence is then given by

h_{n} = s^{\binom{n+1}{2}}(v + w)^{⌊ \frac{(n+1)^{2}}{4} ⌋}w^{⌊ \frac{n^{2}}{4} ⌋}.

We note that the reversion of

\frac{x(1 − rx)}{1 − 2rx − x^{2}(sv − r^{2})}c (\frac{x^{2}sw(1 − rx)^{2}}{(1 − 2rx − x^{2}(sv − r^{2}))^{2}} )

is given by

\frac{1 + 2rx + swx^{2} − \sqrt{1 + 2sx^{2}(2v + w) + s^{2}w^{2}x^{4}}}{2(r + x(r^{2} − sv) + rswx^{2})}

or equivalently by

\frac{x}{1 + 2rx + swx^{2}} c (\frac{x(r + (r^{2} − sv)x + rswx^{2})}{(1 + 2rx + swx^{2})^{2}}) .

This expands to give a sequence that begins 0, 1, −r, −sv + r^{2} − sw, r(2sv − r^{2} + 2sw), 2s^{2}v^{2} + 3sv(sw − r^{2}) + r^{4} − 3r^{2}sw + s^{2}w^{2} …. When v = 0 and w = 1, we obtain the expansion of

\frac{x}{1 + rx + sx^{2}} .

7 Generalized Catalan triangles

There are many triangles associated with the Catalan numbers which have been called by the term “Catalan triangle”. Two such matrices are the Riordan arrays

(1, xc(x)) and (c(x), xc(x)^{2}).

These number triangles are related according to

(c(x), xc(x)^{2}) = (1, xc(x)) · B,

where B = (\frac{1}{1−x}, \frac{x}{1−x}). This can be expressed as (c(x; 0), xc(x; 0)^{2}) = (1, xc(x; 0)) · (T_{n,k}(0)).

We generalize the above Catalan matrices in the following way.

(1, c(x)) ↦ (1 + rxc(x; r), xc(x; r)),

and

(c(x), xc(x)^{2}) ↦ (c(x; r), xc(x; r)^{2}).

We recall that the row sums of the matrix (1 + rxc(x; r), xc(x; r)) have generating function c(x; r). We then have the following result for these generalized Catalan triangles.

Proposition 50.

(c(x; r), xc(x; r)^{2}) = (1 + rxc(x; r), xc(x; r)) · (\frac{1}{1 − x}, \frac{x(1 + rx)}{1 − x}) .

Proof. Straight-forward evaluation shows that both sides are equal.

We have in fact that the elements of the generalized Catalan matrix (c(x; r), xc(x; r)^{2}) are equal to

T_{2n,n+k}(r) − T_{2n,n+k+1}(r).

This corresponds to the formula

\binom{2n}{n + k} − \binom{2n}{n + k + 1}

for the general element of the Catalan matrix (c(x), xc(x)^{2}). We find that the general (n, k)- th element of the generalized Catalan triangle (c(x; r), xc(x; r)^{2}) is equal to

∑_{j=0}^{n+k} \binom{n + k}{j}\binom{2n − j}{n − k − j}r^{j} − ∑_{j=0}^{n+k+1} \binom{n + k + 1}{j}\binom{2n − j}{n − k − j − 1}r^{j}.

This triangle begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ r + 1 & 1 & 0 & 0 & 0 \\ r^{2} + 3r + 2 & 3r + 3 & 1 & 0 & 0 \\ r^{3} + 6r^{2} + 10r + 5 & 6r^{2} + 15r + 9 & 5r + 5 & 1 & 0 \\ r^{4} + 10r^{3} + 30r^{2} + 35r + 14 & 10r^{3} + 45r^{2} + 63r + 28 & 15r^{2} + 35r + 20 & 7r + 7 & 1 \end{matrix} ) .

For the values r = 0 … 4, we obtain triangles that begin, respectively, as follows.

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 5 & 9 & 5 & 1 & 0 & 0 \\ 14 & 28 & 20 & 7 & 1 & 0 \\ 42 & 90 & 75 & 35 & 9 & 1 \end{matrix} ) ,

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 6 & 6 & 1 & 0 & 0 & 0 \\ 22 & 30 & 10 & 1 & 0 & 0 \\ 90 & 146 & 70 & 14 & 1 & 0 \\ 394 & 714 & 430 & 126 & 18 & 1 \end{matrix} ) ,

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 12 & 9 & 1 & 0 & 0 & 0 \\ 57 & 63 & 15 & 1 & 0 & 0 \\ 300 & 414 & 150 & 21 & 1 & 0 \\ 1686 & 2682 & 1275 & 273 & 27 & 1 \end{matrix} ) ,

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 \\ 20 & 12 & 1 & 0 & 0 & 0 \\ 116 & 108 & 20 & 1 & 0 & 0 \\ 740 & 892 & 260 & 28 & 1 & 0 \\ 5028 & 7164 & 2820 & 476 & 36 & 1 \end{matrix} ) ,

and

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 5 & 1 & 0 & 0 & 0 & 0 \\ 30 & 15 & 1 & 0 & 0 & 0 \\ 205 & 165 & 25 & 1 & 0 & 0 \\ 1530 & 1640 & 400 & 35 & 1 & 0 \\ 12130 & 15690 & 5275 & 735 & 45 & 1 \end{matrix} ) .

We note that for r = −1, we get the identity matrix. The corresponding matrices (1 + rxc(x; r), xc(x, r)) begin

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 2 & 2 & 1 & 0 & 0 \\ 0 & 5 & 5 & 3 & 1 & 0 \\ 0 & 14 & 14 & 9 & 4 & 1 \end{matrix} ) ,

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 6 & 10 & 5 & 1 & 0 & 0 \\ 22 & 38 & 22 & 7 & 1 & 0 \\ 90 & 158 & 98 & 38 & 9 & 1 \end{matrix} ) ,

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 6 & 5 & 1 & 0 & 0 & 0 \\ 24 & 24 & 8 & 1 & 0 & 0 \\ 114 & 123 & 51 & 11 & 1 & 0 \\ 600 & 672 & 312 & 87 & 14 & 1 \end{matrix} ) ,

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 12 & 7 & 1 & 0 & 0 & 0 \\ 60 & 44 & 11 & 1 & 0 & 0 \\ 348 & 284 & 92 & 15 & 1 & 0 \\ 2220 & 1916 & 716 & 156 & 19 & 1 \end{matrix} ) ,

and

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 \\ 20 & 9 & 1 & 0 & 0 & 0 \\ 120 & 70 & 14 & 1 & 0 & 0 \\ 820 & 545 & 145 & 19 & 1 & 0 \\ 6120 & 4370 & 1370 & 245 & 24 & 1 \end{matrix} ) .

The variant of the Catalan triangle given by (c(x), xc(x)) becomes the family of triangles (c(x; r), xc(x; r)). For r = 0 … 2, we obtain the triangles that begin

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 & 0 \\ 5 & 5 & 3 & 1 & 0 & 0 & 0 \\ 14 & 14 & 9 & 4 & 1 & 0 & 0 \\ 42 & 42 & 28 & 14 & 5 & 1 & 0 \\ 132 & 132 & 90 & 48 & 20 & 6 & 1 \end{matrix} ) , (\underline{A033184})

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 6 & 4 & 1 & 0 & 0 & 0 & 0 \\ 22 & 16 & 6 & 1 & 0 & 0 & 0 \\ 90 & 68 & 30 & 8 & 1 & 0 & 0 \\ 394 & 304 & 146 & 48 & 10 & 1 & 0 \\ 1806 & 1412 & 714 & 264 & 70 & 12 & 1 \end{matrix} ) , (\underline{A080247})

and

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 12 & 6 & 1 & 0 & 0 & 0 & 0 \\ 57 & 33 & 9 & 1 & 0 & 0 & 0 \\ 300 & 186 & 63 & 12 & 1 & 0 & 0 \\ 1686 & 1086 & 414 & 102 & 15 & 1 & 0 \\ 9912 & 6540 & 2682 & 768 & 150 & 18 & 1 \end{matrix} ) .

The production matrix of the generalized Catalan matrix (c(x; r), xc(x; r)) begins

( \begin{matrix}r + 1 & 1 & 0 & 0 & 0 & 0 \\ r + 1 & r + 1 & 1 & 0 & 0 & 0 \\ r + 1 & r + 1 & r + 1 & 1 & 0 & 0 \\ r + 1 & r + 1 & r + 1 & r + 1 & 1 & 0 \\ r + 1 & r + 1 & r + 1 & r + 1 & r + 1 & 1 \\ r + 1 & r + 1 & r + 1 & r + 1 & r + 1 & r + 1 \end{matrix} ) .

The Riordan array (g(x), f(x)) has \frac{g(x)}{1−yf(x)} as bivariate generating function. Equivalently, this can be seen as the generating function of the polynomial sequence ∑_{k=0}^{n} a_{n,k}y^{k} where the matrix (a_{n,k}) represents the Riordan array (g(x), f(x)). Thus the bivariate generating function of the generalized Catalan array (c(x; r), xc(x; r)) is given by

\frac{c(x; r)}{1 − yxc(x; r)} = \frac{1 − (r + 2y)x − \sqrt{1 − 2(r + 2)x + r^{2}x^{2}}}{2x(1 − y + y(y + r)x)} .

This is equal to

g(x, y) = \frac{1}{1 − x(2y + r)}c (\frac{x(xy(y + r) − y + 1)}{(1 − x(2y + r))^{2}}) .

We can express this generating function as the continued fraction

\frac{1}{1 − (y + r + 1)x − \frac{(r + 1)x^{2}}{1 − (r + 2)x − \frac{(r + 1)x^{2}}{1 − (r + 2)x − \frac{(r + 1)x^{2}}{1 − (r + 2)x − ⋯}}}}.

This gives us the following proposition.

Proposition 51. The matrix polynomials of the generalized Catalan array (c(x; r), xc(x; r)) are the moments of the family of orthogonal polynomials whose coefficient array is given by the Riordan array

(\frac{1 − (y − 1)x}{1 + (r + 2)x + (r + 1)x^{2}} , \frac{x}{1 + (r + 2)x + (r + 1)x^{2}} ) .

In the literature, it is more usual to call the reversal of the Riordan array (c(x), xc(x)) the Catalan matrix \underline{A009766}. Thus we consider the reversal of the generalized Catalan matrix (c(x; r), xc(x; r)). This will have bivariate generating function

g (xy, \frac{1}{y}) = \frac{1 − x(ry + 2) − \sqrt{1 − 2xy(r + 2) + r^{2}x^{2}y^{2}}}{2x(x(ry + 1) + y − 1)} .

This can be expressed as

\frac{1}{1 − x(ry + 2)}c (\frac{x(x(ry + 1) + y − 1)}{(1 − x(ry + 2))^{2}}) ,

or as the continued fraction

\frac{1}{1 − (y(r + 1) + 1)x − \frac{(r + 1)y^{2}x^{2}}{1 − y(r + 2)x − \frac{(r + 1)y^{2}x^{2}}{1 − y(r + 2)x − ⋯}}}.

We have the following proposition.

Proposition 52. The matrix polynomials of the reversal of the generalized Catalan array (c(x; r), xc(x; r)) are the moments of the family of orthogonal polynomials whose coefficient array is given by the Riordan array

(\frac{1 + (y − 1)x}{1 + y(r + 2)x + y^{2}(r + 1)x^{2}} , \frac{x}{1 + y(r + 2)x + y^{2}(r + 1)x^{2}} ) .

The Shapiro Catalan triangle \underline{A039598} [23] is the triangle given by

(c(x), xc(x)) · (\frac{1}{1 − x}, \frac{x}{1 − x}) .

We can generalize this to the generalized Shapiro Catalan triangle

(c(x; r), xc(x; r)) · (\frac{1}{1 − x}, \frac{x(1 + rx)}{1 − x}) .

For r = 0 … 2, we obtain the generalized Shapiro Catalan triangles that begin

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 5 & 4 & 1 & 0 & 0 & 0 & 0 \\ 14 & 14 & 6 & 1 & 0 & 0 & 0 \\ 42 & 48 & 27 & 8 & 1 & 0 & 0 \\ 132 & 165 & 110 & 44 & 10 & 1 & 0 \\ 429 & 572 & 429 & 208 & 65 & 12 & 1 \end{matrix} ) , (\underline{A039598})

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 11 & 7 & 1 & 0 & 0 & 0 & 0 \\ 45 & 39 & 11 & 1 & 0 & 0 & 0 \\ 197 & 205 & 83 & 15 & 1 & 0 & 0 \\ 903 & 1061 & 541 & 143 & 19 & 1 & 0 \\ 4279 & 5483 & 3285 & 1117 & 219 & 23 & 1 \end{matrix} ) ,

and

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 & 0 \\ 19 & 10 & 1 & 0 & 0 & 0 & 0 \\ 100 & 76 & 16 & 1 & 0 & 0 & 0 \\ 562 & 532 & 169 & 22 & 1 & 0 & 0 \\ 3304 & 3619 & 1504 & 298 & 28 & 1 & 0 \\ 20071 & 24394 & 12265 & 3232 & 463 & 34 & 1 \end{matrix} ) .

The case r = 0 is the Shapiro Catalan triangle.

The triangle

(c(x; r), xc(x; r)) · (\frac{1}{1 − x}, \frac{x(1 + rx)}{1 − x})

is given explicitly by

( \frac{1 − (r + 2)x − \sqrt{1 − 2(r + 2)x + r^{2}x^{2}}}{2(r + 1)x^{2}} , \frac{1 − 2(r + 1)x + r^{2}x^{2} − (1 − rx)\sqrt{1 − 2(r + 2)x + r^{2}x^{2}}}{2x} ) ,

which can be expressed as

(\frac{1}{1 − (r + 2)x}c (\frac{x^{2}(r + 1)}{(1 − (r + 2)x)^{2}} ) , \frac{x}{1 − 2(r + 1)x + r^{2}x^{2}} c (\frac{x^{2}}{(1 − 2(r + 1)x + r^{2}x^{2})^{2}} )) .

The first element of this, given by

\frac{1 − (r + 2)x − \sqrt{1 − 2(r + 2)x + r^{2}x^{2}}}{2(r + 1)x^{2}} = \frac{1}{1 − (r + 2)x}c (\frac{x^{2}(r + 1)}{(1 − (r + 2)x)^{2}} ) ,

expands to give the sequence with general term

∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k}(r + 1)^{k}(r + 2)^{n−2k} = \frac{1}{n + 1} ∑_{k=0}^{n} \binom{n + 1}{k}\binom{2n + 2 − k}{n + 2}r^{k}.

This sequence has generating function expressible as the continued fraction

\frac{1}{1 − (r + 2)x − \frac{(r + 1)x^{2}}{1 − (r + 2)x − \frac{(r + 1)x^{2}}{1 − (r + 2)x − ⋯}}}.

The term \frac{1}{n+1} \binom{n+1}{k}\binom{2n+2−k}{n+2} is the general element of the number triangle \underline{A126216}, which counts the number of Schroeder paths of semi-length n containing exactly k peaks but no peaks at level one.

The second term, divided by x, gives \frac{1}{1−2(r+1)x+r^{2}x^{2}} c (\frac{x^{2}}{(1−2(r+1)x+r^{2}x^{2})^{2}} ). This expands to give a sequence which begins

1, 2(r + 1), 3r^{2} + 8r + 5, 2(r + 1)(2r^{2} + 8r + 7), 5r^{4} + 40r^{3} + 105r^{2} + 112r + 42, ….

This polynomial sequence in r has a coefficient array that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 0 & 0 & 0 & 0 & 0 \\ 5 & 8 & 3 & 0 & 0 & 0 & 0 \\ 14 & 30 & 20 & 4 & 0 & 0 & 0 \\ 42 & 112 & 105 & 40 & 5 & 0 & 0 \\ 132 & 420 & 504 & 280 & 70 & 6 & 0 \\ 429 & 1584 & 2310 & 1680 & 630 & 112 & 7 \end{matrix} ) .

Multiplying this on the right by the inverse binomial matrix B^{−1}, we obtain the matrix that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 3 & 0 & 0 & 0 & 0 \\ 0 & 2 & 8 & 4 & 0 & 0 & 0 \\ 0 & 2 & 15 & 20 & 5 & 0 & 0 \\ 0 & 2 & 24 & 60 & 40 & 6 & 0 \\ 0 & 2 & 35 & 140 & 175 & 70 & 7 \end{matrix} ) .

This is \underline{A281260}, the triangle of generalized Narayana numbers [8]

N_{2}(n, k) = \frac{2}{n + 2}\binom{n + 2}{k}\binom{n − 1}{n − k}.

Thus the above sequence has general term

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

The bivariate generating function of the generalized Shapiro Catalan triangle can be expressed as

\frac{(rxy + 1)\sqrt{1 − 2(r + 2)x + r^{2}x^{2}} − r^{2}x^{2}y + x(r + 2)(y + 1) − 1}{2x(r + 1)(r^{2}x^{2}y − x(y^{2} + 2y(r + 1) + 1) + y)}.

Only in the classical case of r = 0 does this admit a “nice” Jacobi continued fraction expression, which is then given by

\frac{1}{1 − (y + 2)x − \frac{x^{2}}{1 − 2x − \frac{x^{2}}{1 − 2x − \frac{x^{2}}{1 − 2x − ⋯}}}}.

8 Generalized Motzkin numbers

We have the formula

M_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k},

where M_{n} denotes the Motzkin numbers \underline{A001006}. Writing

C_{n}(r, s) = ∑_{k=0}^{n} \binom{n + k}{2k}r^{n−k}s^{k}C_{k},  (18)

we can define generalized Motzkin numbers

M_{n}(r, s) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k}(r, s).  (19)

We have M_{n} = M_{n}(0, 1). The sequence M_{n}(r, s) begins

1, 1, r + s + 1, 3r + 3s + 1, r^{2} + r(3Δs + 6) + 2s^{2} + 6s + 1, ….

Proposition 53. The generating function of M_{n}(r, s) is given by the continued fraction

\frac{1}{1 − x − \frac{(r + s)x^{2}}{1 − x − \frac{sx^{2}}{1 − x − \frac{(r + s)x^{2}}{1 − x − \frac{sx^{2}}{1 − x − ⋯}}}}}.

A consequence of this is that the generating function of M_{n}(r, s) is given by

\frac{1 − x}{1 − 2x − (r − 1)x^{2}} c (\frac{sx^{2}(1 − x)^{2}}{(1 − 2x − (r − 1)x^{2})^{2}} )

= \frac{1 − 2x − (r − 1)x^{2} − \sqrt{1 − 4x − 2(r + 2s − 3)x^{2} + 4(r + 2s − 1)x^{3} + (r^{2} − 2r − 4s + 1)x^{4}}}{2sx^{2}(1 − x)} .

We can also form the generalized Motzkin number

M_{n}(r, s, y) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k}(r, s, y).

We find that the generating function of M_{n}(r, s, y) has the continued fraction form

\frac{1}{1 − x − \frac{(r + y)x^{2}}{1 − x − \frac{sx^{2}}{1 − x − \frac{(r + s)x^{2}}{1 − x − \frac{sx^{2}}{1 − x − ⋯}}}}}.

In particular, the sequence M_{n}(r, s, y) has its Hankel transform given by

h_{n} = (r + y)^{n}s^{⌊ \frac{n^{2}}{4} ⌋}(r + s)^{⌊ \frac{(n−1)^{2}}{4} ⌋}.

In particular, we have that the Hankel transform of M_{n}(r, s) is given by

h_{n} = s^{⌊ \frac{n^{2}}{4} ⌋}(r + s)^{⌊ \frac{(n+1)^{2}}{4} ⌋}.

Example 54. We consider M_{n}(s + 1, s − 1) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k} ∑_{j=0}^{k} \binom{k+j}{2j}(s + 1)^{k−j}(s − 1)^{j}. The generating function of this sequence is given by

\frac{1}{1 − x − \frac{2sx^{2}}{1 − x − \frac{(s − 1)x^{2}}{1 − x − \frac{2sx^{2}}{1 − x − \frac{(s − 1)x^{2}}{1 − x − ⋯}}}}}.

For s = 2 we obtain the sequence M_{n}(3, 1) that begins

1, 1, 5, 13, 45, 141, 477, 1597, 5501, ….

This is the binomial transform of the aeration of the sequence

∑_{k=0}^{n} N_{n,k}4^{k} = ∑_{k=0}^{n} \binom{n + k}{2k}C_{k}3^{n−k}

\underline{A082298}, which counts Schroeder paths of semi-length n where the level steps can have 3 colors.

Another family of generalized Motzkin numbers can be formed as follows. We recall that the Narayana triangle with general term

N_{n,k} = \frac{1}{n + 1}\binom{n + 1}{k}\binom{n − 1}{n − k} = 0^{n+k} + \frac{1}{n + 0^{nk}} \binom{n}{k}\binom{n}{k − 1}

has the Catalan numbers as its row sums.

We form the alternative generalized Motzkin numbers

M̃_{n}(r, s) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k} ∑_{i=0}^{k} N_{k,i}r^{i}s^{k−i}.  (20)

This sequence begins

1, 1, r + 1, 3r + 1, r^{2} + r(s + 6) + 1, 5r^{2} + 5r(s + 2) + 1, ….

We find that these generalized Motzkin numbers have generating function given by the continued fraction

\frac{1}{1 − x − \frac{rx^{2}}{1 − x − \frac{sx^{2}}{1 − x − \frac{rx^{2}}{1 − x − \frac{sx^{2}}{1 − x − ⋯}}}}}.

This is equivalent to

\frac{1 − x}{1 − 2x − (r − s − 1)x^{2}} c (\frac{sx^{2}(1 − x)^{2}}{(1 − 2x − (r − s − 1)x^{2})^{2}} ) .

In particular, the Hankel transform of the sequence M̃_{n}(r, s) is given by

h_{n} = r^{⌊ \frac{(n+1)^{2}}{4} ⌋}s^{⌊ \frac{n^{2}}{4} ⌋}.

By construction, M̃_{n}(r, s) represents the first binomial transform of the aeration of the generalized Catalan numbers given by ∑_{k=0}^{n} N_{n,k}s^{n−k}r^{k} [6]. The sequence ∑_{k=0}^{n} N_{n,k}s^{n−k}r^{k} has generating function given by

\frac{1}{1 − \frac{rx}{1 − \frac{sx}{1 − \frac{rx}{1 − ⋯}}}},

or

\frac{1}{1 − (r − s)x}c (\frac{sx}{(1 − (r − s)x)^{2}} ) .

We have that ∑_{k=0}^{n} N_{n,k}s^{n−k}r^{k} = C_{n}(r − s, s, s). Thus

M̃_{n}(r, s) = ∑_{k=0}^{n} \binom{n}{k}C_{\frac{k}{2}} (r − s, s, s)\frac{1 + (−1)^{k}}{2} .  (21)

9 The T transform of the generalized Catalan numbers

C_{n}(r, s, s)

We recall that the generating function of the generalized Catalan numbers C_{n}(r, s, s) = ∑_{k=0}^{n} \binom{n+k}{2k}r^{n−k}s^{k}C_{k} can be expressed as the continued fraction

\frac{1}{1 − (r + s)x − \frac{s(r + s)x^{2}}{1 − (r + 2s)x − \frac{s(r + s)x^{2}}{1 − (r + 2s)x − ⋯}}}.

Taking the T transform [2] of this, we obtain the generating function

\frac{1}{1 − (r + s)x − \frac{s(r + s)x^{2}}{1 − (2r + 3s)x − \frac{4s(r + s)x^{2}}{1 − (3r + 5s)x − \frac{9s(r + s)x^{2}}{1 − (4r + 7s)x − \frac{16s(r + s)x^{2}}{1 − (5r + 9s)x − ⋯}}}}}.

This expands to give the bivariate polynomial that begins

1, r + s, (r + s)(r + 2s), (r + s)(r^{2} + 6rs + 6s^{2}), (r + s)(r^{3} + 14r^{2}s + 36rs^{2} + 24s^{3}), …. Expressed as a polynomial in r, this has a coefficient array that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ s & 1 & 0 & 0 & 0 & 0 & 0 \\ 2s^{2} & 3s & 1 & 0 & 0 & 0 & 0 \\ 6s^{3} & 12s^{2} & 7s & 1 & 0 & 0 & 0 \\ 24s^{4} & 60s^{3} & 50s^{2} & 15s & 1 & 0 & 0 \\ 120s^{5} & 360s^{4} & 390s^{3} & 180s^{2} & 31s & 1 & 0 \\ 720s^{6} & 2520s^{5} & 3360s^{4} & 2100s^{3} & 602s^{2} & 63s & 1 \end{matrix} ) .

We now recall that the Eulerian number triangle E_{2} with generating function

\frac{(1 − z)e^{zx}}{e^{zx} − ze^{x}}

which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 4 & 1 & 0 & 0 & 0 \\ 0 & 1 & 11 & 11 & 1 & 0 & 0 \\ 0 & 1 & 26 & 66 & 26 & 1 & 0 \\ 0 & 1 & 57 & 302 & 302 & 57 & 1 \end{matrix} )

satisfies

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 4 & 1 & 0 & 0 & 0 \\ 0 & 1 & 11 & 11 & 1 & 0 & 0 \\ 0 & 1 & 26 & 66 & 26 & 1 & 0 \\ 0 & 1 & 57 & 302 & 302 & 57 & 1 \end{matrix} ) · B

= ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 & 0 \\ 6 & 12 & 7 & 1 & 0 & 0 & 0 \\ 24 & 60 & 50 & 15 & 1 & 0 & 0 \\ 120 & 360 & 390 & 180 & 31 & 1 & 0 \\ 720 & 2520 & 3360 & 2100 & 602 & 63 & 1 \end{matrix} ) .

This last triangle then has generating function

\frac{(1 − (z + 1))e^{(z+1)x}}{e^{(z+1)x} − (z + 1)e^{x}} = \frac{ze^{(z+1)x}}{(z + 1)e^{x} − e^{(z+1)x}} .

The general element of this matrix is thus

∑_{i=0}^{n} E_{2}(n, i)\binom{i}{k}.

We have the following result. Proposition 55. The T transform of the generalized Catalan number

C_{n}(r, s, s) = ∑_{k=0}^{n} \binom{n + k}{2k}r^{n−k}s^{k}

is given by the generalized Eulerian number

∑_{k=0}^{n} (∑_{i=0}^{n} E_{2}(n, i)\binom{i}{k}) s^{n−k}r^{k}.

10 Conclusions

We have shown that starting with the family of Pascal-like triangles defined by the Riordan arrays (\frac{1}{1−x}, \frac{x(1+rx)}{1−x}), we can define various generalized Catalan numbers. These numbers (or polynomials, since they depend polynomially on parameters r, s, …) are essentially linked to colored Schroeder paths. With the aid of the generating functions c(x; r) we have been able to generalize three notions of Catalan triangle in a natural way. We can furthermore use these generalized Catalan numbers to define generalized Motzkin numbers, where again the parameters can be interpreted as colors. Finally we have shown that a link exists between the generalized Catalan numbers C_{n}(r, s, s) and certain generalized Eulerian numbers via the T transform.

11 Acknowledgments

The author would like to thank the reviewer for their careful reading of the paper and for their constructive remarks.

This paper was completed while the author was a guest at the Applied Algebra and Optimization Research Centre (AORC) of Sungkyunkwan University, Suwon, South Korea, to which he expresses his appreciation.

12 Appendix

We provide a summary of information on the generalized Catalan numbers considered in this paper.

C_{n}(r) = T_{2n,n}(r) − T_{2n,n−1}(r) = ∑_{k=0}^{n} \binom{n + k}{2k}r^{n−k}C_{k}.

The generating function of C_{n}(r) is

c(x; r) = \frac{1}{1 − rx}c (\frac{x}{(1 − rx)^{2}} ) = \frac{1}{x}Rev (\frac{x(1 − x)}{1 + rx}) .

These numbers are the moments for the orthogonal polynomials whose coefficient array is given by

(\frac{1 + x}{1 + (r + 2)x + (r + 1)x^{2}} , \frac{x}{1 + (r + 2)x + (r + 1)x^{2}} ) .

They are the row sums of the Riordan array (\frac{1}{1+rx}, \frac{x(1−x)}{1+rx})^{−1}.

The numbers C_{n}(r, s, y) have generating function

(\frac{1}{1 + rx}, \frac{x(1 − sx)}{1 + rx})^{−1} · \frac{1}{1 − yx}.

These numbers are the moments for the family of orthogonal polynomials with coefficient array given by

(\frac{1 + (2s − y)x + s(s − y)x^{2}}{1 + (r + 2s)x + s(r + s)x^{2}} , \frac{x}{1 + (r + 2s)x + s(r + s)x^{2}} ) .

We have

C_{n}(r, s, s) = ∑_{k=0}^{n} \frac{1}{k + 1}\binom{n + k}{k}\binom{n}{k}r^{n−k}s^{k} = ∑_{k=0}^{n} \frac{1}{n − k + 1}\binom{2n − k}{n}\binom{n}{k}s^{n−k}r^{k}.

The generating function c(x; r, s, s) of C_{n}(r, s, s) is given by

c(x; r, s, s) = \frac{1}{x}Rev (\frac{x(1 − sx)}{1 + rx}) .

We have

c(x; r, s, s) = \frac{1}{1 − rx − \frac{sx}{1 − rx − \frac{sx}{1 − rx − ⋯}}}.

The numbers C_{n}(r, s, s) are the moments of the family of orthogonal polynomials with coefficient array

(\frac{1 + sx}{1 + (r + 2s)x + s(r + s)x^{2}} , \frac{x}{1 + (r + 2s)x + s(r + s)x^{2}} ) .

The numbers Č_{n}(r, s, t) have the generating function

č(x; r, s, t) = \frac{1}{1 − rx}c (\frac{x(s + tx)}{(1 − rx)^{2}}) = \frac{1}{x}Rev (\frac{x(1 − sx)}{1 + rx + tx^{2}} ) .

They are the moments of the family of orthogonal polynomials whose coefficient array is given by

(\frac{1 − sx}{1 + (r + 2s)x + (t + s(r + s))x^{2}} , \frac{x}{1 + (r + 2s)x + (t + s(r + s))x^{2}} ) .

The numbers C̃_{n}(r, s, y) have their generating function given by

(\frac{1 − x(s + 1)}{(1 − x)(1 + (r − 1)x)}, \frac{x(1 − x(s + 1))}{(1 − x)(1 + (r − 1)x)})^{−1} · \frac{1}{1 − yx}.

These generalized Catalan numbers are the moments for the family of orthogonal polynomials whose coefficient matrix is given by

(\frac{1 + (1 + s − y)x}{1 + (r + 2s)x + s(r + s)x^{2}} , \frac{x}{1 + (r + 2s)x + s(r + s)x^{2}} ) .

The numbers ˜ C̃_{n}(r, s, v, w) have their generating function given by

\frac{1 − rx}{1 − 2rx − x^{2}(sv − r^{2})}c (\frac{x^{2}sw(1 − rx)^{2}}{(1 − 2rx − x^{2}(sv − r^{2}))^{2}} ) .

Equivalently, this is given by the continued fraction

\frac{1}{1 − rx − \frac{s(v + w)x^{2}}{1 − rx − \frac{swx^{2}}{1 − rx − \frac{s(v + w)x^{2}}{1 − rx − \frac{swx^{2}}{1 − rx − ⋯}}}}}.

References

[1] M. Aigner, Catalan-like numbers and determinants, J. Combin. Theory Ser. A, 87 (1999), 33–51.

[2] P. Barry, On a transformation of Riordan moment sequences, J. Integer Sequences, 21 (2018), Article 18.7.1.

[3] P. Barry, Classical and semi-classical orthogonal polynomials defined by Riordan arrays, and their moment sequences, J. Integer Sequences, 21 (2018), Article 18.1.5.

[4] P. Barry, Riordan Arrays: A Primer, Logic Press, 2017.

[5] P. Barry, On the central coefficients of Riordan matrices, J. Integer Sequences, 16 (2013), Article 13.5.1.

[6] P. Barry, Continued fractions and transformations of integer sequences, J. Integer Sequences, 12 (2009), Article 09.7.6.

[7] P. Barry, On integer-sequence-based constructions of generalized Pascal triangles, J. Integer Sequences, 9 (2006), Aricle 06.2.4.

[8] D. Callan, Generalized Narayana numbers, http://oeis.org/A281260/a281260.pdf.

[9] F. Chapoton, F. Hivert, and J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, J. Algebra, 465 (2016), 322–355.

[10] A. W. F. Edwards, Pascal’s Arithmetical Triangle: the Story of a Mathematical Idea, Johns Hopkins University Press, 2002.

[11] S. Giraudo, Pluriassociative algebras II: The polydendriform operad and related operads, Adv. Appl. Math., 77 (2016), 3–85.

[12] S. Giraudo, Operads from posets and Koszul duality, preprint, 2016. Available at

https://arxiv.org/abs/1504.04529.

[13] T.-X. He, Parametric Catalan numbers and Catalan triangles, Linear Algebra Appl., 438 (2013), 1467–1484.

[14] P. Henrici, Applied and Computational Complex Analysis, Vol. 3, John Wiley & Sons, 1993.

[15] C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl., 411 (2005), 68–166.

[16] J. W. Layman, The Hankel transform and some of its properties, J. Integer Sequences, 4 (2001), Article 01.1.5.

[17] V. A. Marčenko and L. A. Pastur, Distribution of eigenvalues for some sets of random matrices, Sb. Math., 1 (1967), 457–483.

[18] D. Merlini, R. Sprugnoli, and M. C. Verri, Lagrange inversion: when and how, Acta Appl. Math., 94 (2006), 233–249.

[19] M. Pétréolle, A. D. Sokal, and B.-X. Zhu, Lattice paths and branched continued fractions: an infinite sequence of generalizations of the Stieltjes-Rogers and Thron-Rogers polynomials, with coefficientwise Hankel-total positivity, preprint, 2018. Available at

https://arxiv.org/abs/1807.03271.

[20] E. Roblet and X. G. Viennot, Théorie combinatoire des T-fractions et approximants de Padé en deux points, Discrete Math., 153 (1996), 271–288.

[21] L. Shapiro, A survey of the Riordan group, Center for Combinatorics, Nankai Uni-

versity, 2018. Available electronically at http://www.combinatorics.cn/activities/
Riordan%20Group.pdf .

[22] L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson, The Riordan group, Discr. Appl. Math. 34 (1991), 229–239.

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

[24] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electroni-

    cally at https://oeis.org, 2018.

[25] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices Amer. Math. Soc., 50 (2003), 912–915.

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

[27] H. S. Wall, Analytic Theory of Continued Fractions, AMS Chelsea Publishing, 2001.

[28] P. Yaskov, A short proof of the Marchenko-Pastur theorem, preprint, 2015. Available

    at https://arxiv.org/abs/1506.04922.

2010 Mathematics Subject Classification: Primary 15B36; Secondary 05A10, 05A15, 11C20, 11B83, 42C05. Keywords: Pascal-like triangle, Riordan array, Catalan number, Catalan triangle, Motzkin number, generating function, continued fraction, orthogonal polynomial, moment.

(Concerned with sequences \underline{A000108}, \underline{A000984}, \underline{A001006}, \underline{A006318}, \underline{A007318}, \underline{A008288}, \underline{A009766}, \underline{A033184}, \underline{A033282}, \underline{A039598}, \underline{A047891}, \underline{A054726}, \underline{A060693}, \underline{A064063}, \underline{A064641}, \underline{A078740}, \underline{A080247}, \underline{A082298}, \underline{A082301}, \underline{A082298}, \underline{A082302}, \underline{A086810}, \underline{A088617}, \underline{A090442}, \underline{A090452}, \underline{A103210}, \underline{A103211}, \underline{A108524}, \underline{A126216}, \underline{A131198}, \underline{A133305}, \underline{A152600}, \underline{A152601}, \underline{A269730}, \underline{A269731}, and \underline{A281260}.)

Received December 20 2018; revised version received June 27 2019. Published in Journal of Integer Sequences, August 24 2019.

Return to Journal of Integer Sequences home page.