On One-Parameter Catalan Arrays

José Agapito ^{1}, Ângela Mestre ^{2}, and Maria M. Torres Centro de Análise Funcional, Estruturas Lineares e Aplicações Grupo de Estruturas Algébricas, Lineares e Combinatórias

Departamento de Matemática Faculdade de Ciências, Universidade de Lisboa 1749-016 Lisboa Portugal

           jose.agapito@gmail.com
              amestre@fc.ul.pt
              mmtorres@fc.ul.pt

Pasquale Petrullo Dipartimento di Matematica e Informatica Università degli Studi della Basilicata Potenza Italy

            p.petrullo@gmail.com

Abstract

We present a parametric family of Riordan arrays, which are obtained by multiplying any Riordan array with a generalized Pascal array. In particular, we focus on some interesting properties of one-parameter Catalan triangles. We obtain several combinatorial identities that involve two special Catalan matrices, the Chebyshev polynomials of the second kind, some periodic sequences, and the Fibonacci numbers.

1 Corresponding author.

2 Work performed within the activities of Centro de Análise Funcional, Estruturas Lineares e Aplicações (Faculdade de Ciências, Universidade de Lisboa) and supported by the fellowship SFRH/BPD/48223/2008 provided by the Portuguese Foundation for Science and Technology (FCT).

1 Introduction

There are two infinite lower triangular matrices in the mathematical literature, that are both called Catalan triangles. Let us denote them by C and B, respectively. By way of illustration, their first rows are shown below:

C = (\begin{matrix}1 \\ 1 & 1 \\ 2 & 2 & 1 \\ 5 & 5 & 3 & 1 \\ 14 & 14 & 9 & 4 & 1 \\ 42 & 42 & 28 & 14 & 5 & 1 \\ 132 & 132 & 90 & 48 & 20 & 6 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) , B = (\begin{matrix}1 \\ 2 & 1 \\ 5 & 4 & 1 \\ 14 & 14 & 6 & 1 \\ 42 & 48 & 27 & 8 & 1 \\ 132 & 165 & 110 & 44 & 10 & 1 \\ 429 & 572 & 429 & 208 & 65 & 12 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Note that the 0^{th} column of C is given by the sequence of Catalan numbers (C_{n})_{n≥0}, where C_{n} = \frac{1}{n+1} \binom{2n}{n}. In turn, the 0^{th} column of B is given by (C_{n+1})_{n≥0}. This similarity explains why they are called Catalan triangles.

According to the online encyclopedia of integer sequences (OEIS) [11], the non-zero entries of C (sequence \underline{A033184}) are given by the formula C_{n,k} = \frac{k+1}{n+1} \binom{2n−k}{n}, for n ≥ k ≥ 0. They are known as the (ordinary) ballot numbers. Aigner [2] used these numbers (and generalizations of them) to enumerate various combinatorial instances. Furthermore, Ferrari and Pinzani [8] gave an interpretation of C, using the ECO method, and a suitable change of basis in the vector space of one-variable polynomials. On the other hand, the non-zero entries of B (\underline{A039598}) are given by the formula B_{n,k} = \frac{k+1}{n+1} \binom{2n+2}{n−k}, for n ≥ k ≥ 0. The numbers B_{n,k} first appeared in the work of Shapiro [17, 19], in problems connected with non-intersecting paths, random walks, Eulerian numbers, runs, slides, and moments.^{3} We will refer from now on to C as the Aigner array, and to B as the Shapiro array.

The aim of this paper is to discuss some interesting features regarding the product matrix R(r) = RP (r), where R is a given Riordan array, and the parameter r is any real or complex number. The notation P (r) stands for a generalized Pascal array, such that P (0) = I is the identity matrix, and P (1) = P is the classical Pascal array of binomial numbers, that comes arranged as a lower triangular matrix. We elaborate, in particular, on the product matrix C(r) = CP (r). Clearly, we have C(0) = C. It turns out that C(1) = B. The factorization B = CP resembles Barry’s definition [3, see Sections 6.3 and 6.5] of the generalized ballot array given by Bal = Cat · Bin; where Bin = P, and Cat = diag(1, C).

Recently, Yang [23] introduced a generalized Catalan matrix, given by

C[a, b; r] = ((\frac{1 − \sqrt{1 − 4rz}}{2rz} )^{a}, z(\frac{1 − \sqrt{1 − 4rz}}{2rz} )^{b}) ,

3Actually, Shapiro used the formula B_{n,k} = \frac{k}{n} \binom{2n}{n+k}, for n, k ≥ 1. His formula is just a shifted version of the formula shown previously for B_{n,k}.

where a, b are integer numbers, and r is an arbitrary parameter. Such a generalization provides a unified way of presenting the matrices C and B, along with many other matrices related to Catalan numbers. One can check that the 0^{th} column of C[a, b; r] forms a sequence of degree n monomials in r, whose coefficients are polynomials in a and b, that have rational coefficients. The one-parameter Catalan triangles that we will study are instead given by

C(r) = (\frac{1 − 2rz − \sqrt{1 − 4z}}{2z(1 − r + r^{2}z)} , \frac{1 − 2rz − \sqrt{1 − 4z}}{2(1 − r + r^{2}z)} ) .

We shall show explicitly that the 0^{th} column of C(r) forms a sequence (C(r)_{n,0})_{n≥0} of degree n monic polynomials in r. These polynomials have positive integer coefficients. In particular, the constant term of C(r)_{n,0} is the Catalan number C_{n}. For this reason, we shall refer to C(r) as a Catalan triangle too.

It is also worth mentioning that He [9] introduced recently, a family of Catalan triangles which depend on two parameters. His (c, r)-Catalan triangles are based on the sequence characterization of Bell-type Riordan arrays. We emphasize that they are also different from the Catalan triangles C(r). One way to see this difference is to compare, once again, the 0^{th} column of both types of matrices. On the one hand, one can check that the 0^{th} column of a (c, r)-Catalan triangle forms a sequence of degree n homogeneous polynomials in c and r, whose coefficients are the well-known Narayana numbers. On the other hand, the 0^{th} column of a Catalan triangle C(r) forms a sequence of one-variable polynomials of degree n, whose coefficients are the ordinary ballot numbers. Recall that both the Narayana and the ballot numbers are known to refine the Catalan numbers.

The fundamental theorem of Riordan arrays, and the isomorphism between Riordan arrays and Sheffer polynomials (the former being the coefficient matrices for the latter), allow us to interpret C(r) as a change of basis matrix in the space of polynomials in one variable. Thus, for instance, the Shapiro array B is seen as the change of basis between the Chebyshev polynomials of the second kind, and the standard polynomial sequence of powers of one variable. In this way, by specifying values for the one-variable of the corresponding polynomials, several formulas related to periodic sequences, the sequence of natural numbers, and the sequence of Fibonacci numbers, can be stated and generalized.

2 General setting

The literature on Riordan arrays is vast and constantly growing (see, for instance, [1, 4, 5, 7, 9, 10, 12, 13, 14, 15, 16, 18, 20, 21, 22]). In this section we recall the fundamental theorem of Riordan arrays, and discuss some general facts regarding the generalized Sheffer polynomial sequence associated with any Riordan array. Then we define a one-parameter family of Riordan arrays, and focus our attention on Catalan arrays in Section 3.

2.1 Riordan Arrays

Let d(z) = d_{0} + d_{1}z + d_{2}z^{2} + ⋯, and let h(z) = h_{0} + h_{1}z + h_{2}z^{2} + ⋯ be two formal power series in z with coefficients in a given integral domain R, with unit 1. Assume that d_{0} = d(0) ≠ 0, and h_{0} = h(0) = 0. A Riordan array R is an infinite lower triangular matrix, whose entries are given by

R_{n,k} = [z^{n}]d(z)h(z)^{k}.  (1)

The operator [z^{n}] acts on a formal power series f(z) = ∑_{k≥0} f_{k}z^{k} by extracting its n^{th} coefficient; that is, we have [z^{n}]f(z) = f_{n}. It is customary to denote R = (d(z), h(z)). In addition, the set of Riordan arrays for which h′(0) ≠ 0, and that is equipped with the multiplication given by

(d_{1}(z), h_{1}(z))(d_{2}(z), h_{2}(z)) = (d_{1}(z)d_{2}(h_{1}(z)), h_{2}(h_{1}(z))),  (2)

forms a group. We denote this group by ℜ𝔦𝔬. The group identity is the usual identity matrix I = (1, z). Furthermore, for any R ∈ ℜ𝔦𝔬, its inverse is given by R^{−1} = (1/d(h̄(z)), h̄(z)), where h̄(z) denotes the compositional inverse of h(z).

The order of a formal power series g(z) = ∑_{k≥0} g_{k}z^{k} is the minimal index k such that g_{k} ≠ 0. Since R[[z]] denotes the ring of formal power series in z with coefficients in R, we will write R_{r}[[z]] to denote the set of formal power series of order r. Therefore, if R = (d(z), h(z)) ∈ ℜ𝔦𝔬, then d(z) ∈ R_{0}[[z]], and h(z) ∈ R_{1}[[z]]. For simplicity, and without loss of generality, we further assume that d_{0} = 1, and h_{1} = h′(0) = 1, so that R_{n,n} = h_{1}^{n} = 1, for all n ≥ 0.

Now, let us define an action ∗ of the group ℜ𝔦𝔬 on R_{0}[[z]] by

(d(z), h(z)) ∗ g(z) = d(z)g(h(z)).  (3)

Formula (3) represents the traditional matrix-column multiplication. Therefore, it is also equivalent to saying that, for any n ≥ 0, the following identity holds

∑_{k=0}^{n} R_{n,k}g_{k} = [z^{n}]d(z)g(h(z)).  (4)

Equation (4) is known as the fundamental theorem of Riordan arrays. It is usually used to deal with sums and combinatorial identities. In particular, let g(z) = 1 + xz + x^{2}z^{2} + ⋯ = \frac{1}{1−xz}. We write

p_{n}^{R}(x) = ∑_{k=0}^{n} R_{n,k}x^{k} = [z^{n}]\frac{d(z)}{1 − xh(z)}.  (5)

We call (p_{n}^{R}(x))_{n≥0} the Sheffer polynomial sequence associated with R. Formula (5) implies that the generating function of p_{n}^{R}(x) is given by

∑_{n≥0} p_{n}^{R}(x)z^{n} = \frac{d(z)}{1 − xh(z)}.  (6)

Likewise, the generating function for the Sheffer polynomial associated with the inverse array R^{−1} = (1/d(h̄(z)), h̄(z)) is

∑_{n≥0} p_{n}^{R^{−1}}(x)z^{n} = \frac{1}{d(h̄(z))} \frac{1}{1 − xh̄(z)}.  (7)

Since R is invertible, and the sequence (x^{n})_{n≥0} is a basis for the linear space ℂ[x], the sequence (p_{n}^{R}(x))_{n≥0} is also a basis for ℂ[x]. Therefore, any R ∈ ℜ𝔦𝔬 can be interpreted as the change of basis matrix between the standard basis (x^{n})_{n≥0}, and the basis of polynomials (p_{n}^{R}(x))_{n≥0}. Hence, we have

∑_{k=0}^{n} R_{n,k}p_{k}^{R^{−1}}(x) = x^{n}.  (8)

We will use Equation (8) in Section 4 to deduce some interesting combinatorial identities involving the Riordan arrays C and B.

2.2 One-parameter Riordan arrays

The classical Pascal array P of binomial numbers \binom{n}{k} is a Riordan array, since we can write P = (p(z), zp(z)), where p(z) = \frac{1}{1−z}. Given any real number r, the Riordan array P (r) = (p(rz), zp(rz)) = (\frac{1}{1−rz}, \frac{z}{1−rz}) is known as the generalized Pascal array of parameter r. Its entries are given by P (r)_{n,k} = \binom{n}{k}r^{n−k}.

Definition 1. Let R be in ℜ𝔦𝔬. The r-Riordan array R(r) is defined by R(r) = RP (r).

Set R = (d(z), h(z)). Then, by Equation (2), we have R(r) = (\frac{d(z)}{1−rh(z)}, \frac{h(z)}{1−rh(z)}). Using Equation (1), it is easy to check that the entries of R(r) are given by

R(r)_{n,k} = [z^{n}]\frac{d(z)}{1 − rh(z)} (\frac{h(z)}{1 − rh(z)})^{k} = [z^{n}]\frac{d(z)h(z)^{k}}{(1 − rh(z))^{k+1}} .

Lemma 2. For any real number r, the Sheffer polynomial sequence (p_{n}^{R(r)}(x))_{n≥0} satisfies the identity

p_{n}^{R(r)}(x) = p_{n}^{R}(x + r).

Proof. By Equation (5), we have

p_{n}^{R(r)}(x) = ∑_{k=0}^{n} R(r)_{n,k}x^{k} = [z^{n}]\frac{\frac{d(z)}{1 − rh(z)}}{1 − x\frac{h(z)}{1 − rh(z)}} = [z^{n}]\frac{d(z)}{1 − (x + r)h(z)} = p_{n}^{R}(x + r).

Corollary 3. Let n be a non-negative integer. The constant term and the sum of coefficients of p_{n}^{R(r)}(x) are given by

p_{n}^{R(r)}(0) = R(r)_{n,0} = ∑_{k=0}^{n} R_{n,k}r^{k}.  (9)

p_{n}^{R(r)}(1) = ∑_{k=0}^{n} R(r)_{n,k} = R(r + 1)_{n,0}.  (10)

3 r-Catalan triangles

Let us recall that the generating function for the well-known Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} is c(z) = \frac{1−\sqrt{1−4z}}{2z}. We apply Definition 1 to the Riordan array C = (c(z), zc(z)).

Definition 4. The r-Catalan triangle C(r) is given by C(r) = CP (r). Then

C(r) = (\frac{c(z)}{1 − rzc(z)}, \frac{zc(z)}{1 − rzc(z)}) = (\frac{1 − 2rz − \sqrt{1 − 4z}}{2z(1 − r + r^{2}z)} , \frac{1 − 2rz − \sqrt{1 − 4z}}{2(1 − r + r^{2}z)} ) . (11)

In particular, we have C(0) = C. Moreover, since the identity c(z) = 1 + zc(z)^{2} holds, it follows that C(1) = CP (1) = (\frac{c(z)}{1−zc(z)}, \frac{zc(z)}{1−zc(z)}) = (c(z)^{2}, zc(z)^{2}) = B.

The next formula follows from Definition 4.

Lemma 5. The entries of C(r) are given by

C(r)_{n,k} = [z^{n−k}] (\frac{c(z)}{1 − rzc(z)})^{k+1} = ∑_{i=0}^{n−k} \frac{i + k + 1}{n + 1}\binom{2n − i − k}{n}\binom{i + k}{k}r^{i}. (12)

The matrix C(r) is an array of polynomials in r. By way of illustration, the first entries of C(r) are

C(r) = (\begin{matrix}1 \\ 1 + r & 1 \\ 2 + 2r + r^{2} & 2 + 2r & 1 \\ 5 + 5r + 3r^{2} + r^{3} & 5 + 6r + 3r^{2} & 3 + 3r & 1 \\ 14 + 14r + 9r^{2} + 4r^{3} + r^{4} & 14 + 18r + 12r^{2} + 4r^{3} & 9 + 12r + 6r^{2} & 4 + 4r & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

For every k ≥ 1, column k of C(r) is the (k + 1)-fold convolution of column 0. Thus, for example, the first columns of C(2) are given by the following sequences:

C(2) = (\underline{A001700} \underline{A008549} \underline{A045720} \underline{A045894} \underline{A035330} ⋯) .

The 0^{th} column of C(r) forms a sequence (C(r)_{n,0})_{n≥0} of monic polynomials, which are given by the matrix-column product C[1, r, r^{2}, …]^{T}, as observed in Equation (9). We can obtain some known sequences by assigning values to the parameter r. For instance, we have (C(3)_{n,0})_{n≥0} = \underline{A049027} and (C(4)_{n,0})_{n≥0} = \underline{A076025}. Observe that, by Equation (12), the constant term of each polynomial in the sequence (C(r)_{n,0})_{n≥0} is equal to the Catalan number C_{n}. Moreover, we also have

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

This is a well-known result. In this sense, we say that the polynomial sequence (C(r)_{n,0})_{n≥0} is a refinement of the shifted Catalan sequence (C_{n+1})_{n≥0}.

Now, set h(z) = zc(z). We have z = h̄(z)c(h̄(z)). It is easy to check that h̄(z) = z − z^{2}. Hence, we have C^{−1} = (^{1}/c(\overline{zc(z)}), \overline{zc(z)}) = (1 − z, z − z^{2}). Since C(r)^{−1} = P (r)^{−1}C^{−1}, it follows that

C(r)^{−1} = (\frac{1}{1 + rz} , \frac{z}{1 + rz} ) (1 − z, z − z^{2}) = (\frac{1 + (r − 1)z}{(1 + rz)^{2}} , \frac{z + (r − 1)z^{2}}{(1 + rz)^{2}} ) .  (13)

Lemma 6. The entries of C(r)^{−1} are given by

C(r)n,k^{−1} = [z^{n−k}] (\frac{1 + (r − 1)z}{(1 + rz)^{2}} )^{k+1} = (−1)^{n−k} ∑_{i=0}^{n−k} \binom{i + k + 1}{n − i − k}\binom{i + k}{k}r^{i}. (14)

Lemma 5 and Lemma 6 show that both C(r)_{n,k} and (−1)^{n−k}C(r)n,k^{−1} are polynomials in r with positive integer coefficients. In addition, note that the polynomial C(r)_{n+1,1} is of degree n, has constant term C_{n+1}, and its leading coefficient is n + 1. Both lemmas are useful to deduce several formulas and combinatorial identities. For instance, letting r = 0 in Equation (14), we obtain

Cn,k^{−1} = [z^{n−k}](1 − z)^{k+1} = \binom{n − 2k − 2}{n − k} = (−1)^{n−k}\binom{k + 1}{n − k}.

Similarly, letting r = 1 in Equation (14), we get

\begin{aligned}Bn,k^{−1} = [z^{n−k}] (\frac{1}{(1+z)^{2}} )^{k+1} & = & (−1)^{n−k}\binom{n + k + 1}{n − k} \\ & = & (−1)^{n−k} ∑_{i=0}^{n−k} \binom{i + k + 1}{n − i − k}\binom{i + k}{k}. \end{aligned}  (15)

Thus, the following formula is immediate.

Lemma 7.

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

The next non-trivial combinatorial identity follows directly from Equation (10) and Equation (12).

Lemma 8.

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

As for the generating functions for the Sheffer polynomials associated with C(r) and C(r)^{−1}, the next formulas are straightforward consequences of Equation (6) and Equation (7), using Formula (11) and Formula (13), respectively.

Proposition 9.

∑_{n≥0} p_{n}^{C(r)}(x)z^{n} = \frac{c(z)}{1 − (x + r)zc(z)}

∑_{n≥0} p_{n}^{C(r)^{−1}}(x)z^{n} = \frac{1 + (r − 1)z}{1 + (2r − x)z + (r^{2} − (r − 1)x)z^{2}}  (16)

In Section 4, we will use Proposition 9 to obtain more combinatorial identities.

4 Special identities

4.1 Identities involving the Aigner array

Set r = 0 and x = −1 in Equation (16). We obtain

1 + ∑_{n≥1} p_{n}^{C^{−1}}(−1)(−z)^{n} = \frac{1 + z}{1 − z − z^{2}}

= 1 + 2z + 3z^{2} + 5z^{3} + 8z^{4} + 13z^{5} + 21z^{6} + 34z^{7} + 55z^{8} + ⋯

= F_{2} + F_{3}z + F_{4}z^{2} + F_{5}z^{3} + ⋯,

where F_{n} is the n^{th} Fibonacci number, for n ≥ 2. Hence, for n ≥ 0, it holds that

(−1)^{n}p_{n}^{C^{−1}}(−1) = F_{n+2}.

Since p_{n}^{C^{−1}}(x) = ∑_{k=0}^{n} Cn,k^{−1}x^{k}, we have

C^{−1} ( 1 ; −1 ; 1 ; −1 ; ⋮) = ( F_{2} ; −F_{3} ; F_{4} ; −F_{5} ; ⋮) , or equivalently, C ( F_{2} ; −F_{3} ; F_{4} ; −F_{5} ; ⋮) = ( 1 ; −1 ; 1 ; −1 ; ⋮) .

Then

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

4.2 Identities involving the Shapiro array

Set r = 1 in Equation (16). Shapiro, Woan, and Getu [19] observed that the Catalan triangle B verified the following interesting identity:

B ( 1 2 3 4 5 ⋮ ) = ( 1 4 4^{2} 4^{3} 4^{4} ⋮ ) .  (17)

The problem of finding a matrix identity that extends the sequence (1, 4, 4^{2}, 4^{3}, …) to the sequence (1, k, k^{2}, k^{3}, …) in Equation (17), was studied by Chen, Li, Shapiro and Yan [5]. They generalized the following known recurrence relation for B; namely,

B_{n,k} = B_{n−1,k−1} + 2B_{n−1,k} + B_{n−1,k+1},

by constructing a matrix M that satisfies the identity

M ( 1 ; 1 + t ; 1 + t + t^{2} ; 1 + t + t^{2} + t^{3} ; ⋮ ) = ( 1 ; k ; k^{2} ; k^{3} ; ⋮ ) .

The first column of M (that is, its 0^{th} column) was then interpreted in terms of weighted partial Motzkin paths. Here, we approach the problem of extending the sequence (1, 4, 4^{2}, 4^{3}, …) to the sequence (1, k, k^{2}, k^{3}, …), by keeping C(1) = B fixed, and using Sheffer sequences. More explicitly, by Equation (16), we have

1 + ∑_{n≥1} p_{n}^{B^{−1}}(x)z^{n} = \frac{1}{1 − (x − 2)z + z^{2}} .

Furthermore, by Equation (8), we also have

B ( 1 ; p_{1}^{B^{−1}}(x) ; p_{2}^{B^{−1}}(x) ; ⋮) = ( 1 ; x ; x^{2} ; ⋮) , or equivalently, B^{−1} ( 1 ; x ; x^{2} ; ⋮) = ( 1 ; p_{1}^{B^{−1}}(x) ; p_{2}^{B^{−1}}(x) ; ⋮) .  (18)

By Identity (15), the polynomial p_{n}^{B^{−1}}(x) is given by

p_{n}^{B^{−1}}(x) = ∑_{k=0}^{n} Bn,k^{−1}x^{k} = ∑_{k=0}^{n}(−1)^{n−k}\binom{n + k + 1}{n − k}x^{k}.  (19)

Note that p_{n}^{B^{−1}}(x) = U_{n} (\frac{x−2}{2}), where (U_{n}(x))_{n≥0} denotes the sequence of Chebyshev

polynomials of the second kind [6]. Moreover, the sequence (p_{n}^{B^{−1}}(x))_{n≥0} satisfies the threeterm recursion

p_{n}^{B^{−1}}(x) = (x − 2)p_{n−1}^{B^{−1}}(x) − p_{n−2}^{B^{−1}}(x), n ≥ 2,

with initial values p_{0}^{B^{−1}}(x) = 1 and p_{1}^{B^{−1}}(x) = x−2. Whenever x ∈ ℤ, the polynomial sequence (p_{n}^{B^{−1}}(x))_{n≥0} reduces to an integer sequence. By specifying the values of x in Equation (18), we obtain many interesting relations.

Example 10 (Periodic sequences). When x = 2, the recursion p_{n}^{B^{−1}}(2) = −p_{n−2}^{B^{−1}}(2), with initial values p_{0}^{B^{−1}}(2) = 1 and p_{1}^{B^{−1}}(2) = 0, is solved by the period-4 sequence 1, 0, −1, 0. Hence, we have

( \begin{matrix}1 \\ 2 & 1 \\ 5 & 4 & 1 \\ 14 & 14 & 6 & 1 \\ 42 & 48 & 27 & 8 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 ; 0 ; −1 ; 0 ; 1 ; ⋮ ) = ( 1 2 2^{2} 2^{3} 2^{4} ⋮ ) .

When x = 3, the recursion p_{n}^{B^{−1}}(3) = p_{n−1}^{B^{−1}}(3) − p_{n−2}^{B^{−1}}(3), satisfying the initial conditions p_{0}^{B^{−1}}(3) = p_{1}^{B^{−1}}(3) = 1, is solved by the period-6 sequence 1, 1, 0, −1, −1, 0. Thus, we have

( \begin{matrix}1 \\ 2 & 1 \\ 5 & 4 & 1 \\ 14 & 14 & 6 & 1 \\ 42 & 48 & 27 & 8 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 ; 1 ; 0 ; −1 ; −1 ; ⋮ ) = ( 1 3 3^{2} 3^{3} 3^{4} ⋮ ) .

These two cases are better understood by recalling that U_{n}(cos y) = \frac{sin(n+1)y}{sin y}. Hence, we have

p_{n}^{B^{−1}}(2) = U_{n} (cos \frac{π}{2}) and p_{n}^{B^{−1}}(3) = U_{n} (cos \frac{π}{3}). These identities explain why we obtained periodic sequences.

Example 11 (Natural numbers). When x = 4, the recursion p_{n}^{B^{−1}}(4) = 2p_{n−1}^{B^{−1}}(4) − p_{n−2}^{B^{−1}}(4), with initial values p_{0}^{B^{−1}}(4) = 1, p_{1}^{B^{−1}}(4) = 2, is solved by the sequence (p_{n}^{B^{−1}}(4))_{n≥0} = (n + 1)_{n≥0}. Thus, we obtain the Identity (17):

( \begin{matrix}1 \\ 2 & 1 \\ 5 & 4 & 1 \\ 14 & 14 & 6 & 1 \\ 42 & 48 & 27 & 8 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 2 3 4 5 ⋮ ) = ( 1 4 4^{2} 4^{3} 4^{4} ⋮ ) .

The previous matrix identity is equivalent to Chen’s combinatorial formula [5]:

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

Example 12 (Fibonacci numbers). When x = 5, the recursion p_{n}^{B^{−1}}(5) = 3p_{n−1}^{B^{−1}}(5)−p_{n−2}^{B^{−1}}(5), with initial conditions p_{0}^{B^{−1}}(5) = 1 and p_{1}^{B^{−1}}(5) = 3, is solved by the subsequence of Fibonacci numbers (p_{n}^{B^{−1}}(5))_{n≥0} = (F_{2n+2})_{n≥0}. Thus, Shapiro’s triangle B, and the Fibonacci numbers of even index, are related by the following identity:

( \begin{matrix}1 \\ 2 & 1 \\ 5 & 4 & 1 \\ 14 & 14 & 6 & 1 \\ 42 & 48 & 27 & 8 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( 1 3 8 21 55 ⋮ ) = ( 1 5 5^{2} 5^{3} 5^{4} ⋮ ) .

Equivalently, we have

∑_{k=0}^{n} \frac{k + 1}{n + 1}\binom{2n + 2}{n − k}F_{2k+2} = 5^{n}.  (20)

Using the well-known binomial recurrence relation \binom{n}{k} = \binom{n−1}{k−1} + \binom{n−1}{k} in Equation (19), and then inverting Formula (20), we obtain

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

Moreover, seeing as F_{2n+3} = F_{2(n+1)+2} − F_{2n+2}, we can deduce an analogous formula for the Fibonacci numbers of odd index; that is

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

5 Acknowledgements

The authors wish to thank the editor and the referee for their helpful comments.

References

[1] J. Agapito, Â. Mestre, P. Petrullo, and M. M. Torres, A symbolic treatment of Riordan arrays, Linear Algebra Appl. 439 (2013), 1700–1715.

[2] M. Aigner, Enumeration via ballot numbers, Discrete Math. 308 (2008), 2544–2563.

[3] P. Barry, A study of integer sequences, Riordan arrays, Pascal-like arrays and Hankel transforms, PhD thesis, University College Cork, 2009.

[4] E. H. M. Brietzke, An identity of Andrews and a new method for the Riordan array proof of combinatorial identities, Discrete Math. 308 (2008), 4246–4262.

[5] W. Y. C. Chen, N. Y. Li, L. W. Shapiro, and S. H. F. Yan, Matrix identities on weighted partial Motzkin paths, European J. Combin. 28 (2007), 1196–1207.

[6] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Riedel, Dordrecht, 1974.

[7] G. della Riccia, Riordan arrays, Sheffer sequences and orthogonal polynomials, J. Integer Seq. 11 (2008), Article 08.5.3.

[8] L. Ferrari and R. Pinzani, Catalan-like numbers and succesion rules, Pure Math. Appl. 16 (2005), 229–250.

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

[10] T.-X. He, L. C. Hsu, and P. J.-S. Shiue, The Sheffer group and the Riordan group, Discrete Appl. Math. 155 (2007), 1895–1909.

[11] O.E.I.S. Foundation Inc., The Online Encyclopedia of Integer Sequences.

http://oeis.org, 2011.

[12] A. Luzón, D. Merlini, M. A. Morón, and R. Sprugnoli, Identities induced by Riordan arrays, Linear Algebra Appl. 436 (2012), 631–647.

[13] A. Luzón and M. A. Morón, Recurrence relations for polynomial sequences via Riordan matrices, Linear Algebra Appl. 433 (2010), 1422–1446.

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

[15] D. Merlini and R. Sprugnoli, Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern, Theor. Comput. Sci. 412 (2011), 2988–3001.

[16] D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978), 301–310.

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

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

[19] L. W. Shapiro, W. Woan, and S. Getu, Runs, slides and moments, SIAM J. Alg. Disc. Math. 4 (1983), 459–466.

[20] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[21] R. Sprugnoli, Riordan arrays and the Abel-Gould identity, Discrete Math. 142 (1995), 213–233.

[22] W. Wang and T. Wang, Generalized Riordan arrays, Discrete Math. 308 (2008), 6466– 6500.

[23] S.-L. Yang, Some inverse relations determined by Catalan matrices, Int. J. Comb. (2013), Art. ID 528584.

2010 Mathematics Subject Classification: Primary 15B; Secondary 05A19, 11B37, 11B83, 11C. Keywords: Riordan array, Pascal array, Catalan triangle, Sheffer polynomial, combinatorial identity, recurrence, Chebyshev polynomial, Fibonacci number.

(Concerned with sequences \underline{A001700}, \underline{A008549}, \underline{A033184}, \underline{A035330}, \underline{A039598}, \underline{A045720}, \underline{A045894}, \underline{A049027}, and \underline{A076025}.)

Received January 27 2015; revised versions received February 17 2015; March 3 2015. Published in Journal of Integer Sequences, May 17 2015.

Return to Journal of Integer Sequences home page.