A Matrix Approach to Generalized Delannoy and Schröder Arrays

Luis Verde-Star Department of Mathematics Universidad Autónoma Metropolitana Apartado 55–534, CdMx, 09340 Mexico

                      verde@xanum.uam.mx

Abstract

We construct a set of Pascal-like infinite matrices that contains the generalized Delannoy arrays associated with weighted lattice paths. From each of our Delannoy matrices we obtain several Schröder arrays. We construct the matrices combining two Pascal translation matrices and a diagonal matrix, and we find explicit formulas for the entries of the matrices, and recurrence relations and generating functions for the central generalized Delannoy and Schröder numbers. We also express the entries of all the generalized Delannoy matrices in terms of Jacobi polynomials.

1 Introduction

The Pascal triangle is the oldest and most studied two-dimensional array of integers. Its origin is in elementary algebra, but it has numerous properties of interest in combinatorics and number theory. The representation of the Pascal triangle as an infinite lower triangular matrix makes it a linear transformation on the vector space of formal power series. During the last 40 years numerous generalizations of Pascal matrices have been studied from diverse points of view. One of the connections of Pascal matrices with combinatorics comes from the problems of counting diverse types of paths on lattices. From some of these problems come some interesting arrays of integers, for example the Delannoy and the Schröder arrays, that have been extensively studied by numerous authors. The entries for the Delannoy array \underline{A008288} and the Schröder array \underline{A033877} in Sloane’s On-line Encyclopedia of Integer Sequences [10] contain hundreds of references and useful links.

Several authors have used Riordan matrices to construct matrices that are useful to study diverse aspects of the Delannoy and Schröder arrays and their generalizations. Among them we can mention Barry [3], Cheon, Kim, and Shapiro [5], Ramírez and Sirvent [8], Schröder [9], L. Yang et al. [13], and S.-L. Yang et al. [14]. Other relevant references about Delannoy numbers are the papers by Banderier and Schwer [1] and Sulanke [11]. Dziemiańczuk [6] studied weighted lattice paths with weight functions that depend on the position on the lattice.

In the present paper, we construct Pascal-like matrices by generalizing the Pascal triangle represented as a symmetric infinite matrix T = [t_{n,k}] with t_{n,k} = \binom{n+k}{k} for n ≥ 0 and k ≥ 0. Let P be the lower triangular matrix with entries p_{n,k} = \binom{n}{k}. Then it is easy to see that P P^{T} = T. This is the construction of the symmetric matrix representation of the Pascal triangle that we generalize as follows. We extend first the lower triangular P to P (z) = [\binom{n}{k}z^{n−k}], where z is a complex number. The matrix P (z) represents a translation operator. Then we take an infinite diagonal matrix E, with nonzero entries in the diagonal, and construct a matrix A = P (z)EP^{T}(x), where z and x are complex numbers. The matrix A is a generalization of T and depends on the parameters z and x and also on the entries of E. Choosing suitable diagonal matrices E we obtain matrices with interesting combinatorial identities. When the entries of E are the terms of a geometric sequence 1, u, u^{2}, u^{3}, …, the corresponding matrix A is a generalized Delannoy matrix, associated with weighted lattice paths with weights z, x and u − zx.

Using shift matrices we combine a generalized Delannoy matrix D with a scalar multiple of a shifted D and obtain a generalized Schröder matrix G. We also show that G can be obtained as P (z)MP^{T}(x), where M is a simple Riordan matrix, and also as DU, where U is an upper triangular invertible Toeplitz matrix associated with a rational function.

In our matrices the central generalized Delannoy or Schröder numbers appear in the main diagonal, in the same way as the central binomial coefficients appear in the symmetric Pascal matrix T. Something similar can be observed in the approach of Woan [12], who uses Hankel matrices.

Our approach seems to be an alternative to the Riordan matrix approach to the construction of generalized Pascal-like matrices. Replacing the Pascal matrices P (z) with Stirling matrices or q-Pascal matrices we can develop theories analogous to the one presented here.

2 Pascal-like infinite matrices

In this section we use Pascal and diagonal matrices to construct a set of Pascal-like infinite matrices whose elements satisfy certain simple two dimensional recurrence relations, and that contains the generalized Delannoy matrices.

We consider infinite matrices A = [a_{n,k}] with complex entries and non-negative indices n and k. If A and B are infinite matrices the usual matrix multiplication AB is not well defined whenever ∑_{j=0}^{∞} a_{n,j}b_{j,k} is divergent for some pair (n, k). If A is a lower triangular or a lower m-Hessenberg matrix, then AB is well defined for every infinite matrix B. Similarly, if A is an upper triangular or an upper m-Hessenberg matrix, then BA is well defined for every infinite matrix B.

For z in the complex numbers we define the Pascal matrix P (z) as the lower triangular infinite matrix whose (n, k) entry is \binom{n}{k}z^{n−k}, for n ≥ k ≥ 0, and it is zero if k > n. That is,

P (z) = [\begin{matrix}1 & 0 & 0 & 0 & 0 & … \\ z & 1 & 0 & 0 & 0 & … \\ z^{2} & 2z & 1 & 0 & 0 & … \\ z^{3} & 3z^{2} & 3z & 1 & 0 & … \\ z^{4} & 4z^{3} & 6z^{2} & 4z & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

It is well-known that the set {P (z) : z ∈ ℂ} is a group under matrix multiplication which is isomorphic to the additive group of complex numbers, and is also isomorphic to the group of translation operators on the vector space of polynomials in one complex variable.

Define the matrix A = [a_{n,k}] by

A = P (z)P^{T}(x) = [\begin{matrix}1 & x & x^{2} & x^{3} & x^{4} & … \\ z & 2zx & 3zx^{2} & 4zx^{3} & 5zx^{4} & … \\ z^{2} & 3z^{2}x & 6z^{2}x^{2} & 10z^{2}x^{3} & 15z^{2}x^{4} & … \\ z^{3} & 4z^{3}x & 10z^{3}x^{2} & 20z^{3}x^{3} & 35z^{3}x^{4} & … \\ z^{4} & 5z^{4}x & 15z^{4}x^{2} & 35z^{4}x^{3} & 70z^{4}x^{4} & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Then we have a_{n,k} = \binom{n+k}{k}z^{n}x^{k}, which can be interpreted as the sum of all the products of the form b_{1}b_{2}b_{3} ⋯ b_{n+k}, where n of the b_{i} are equal to z and the rest are equal to x. Notice that the recurrence relation a_{n,k} = xa_{n,k−1} + za_{n−1,k} holds for all n ≥ 1 and k ≥ 1. For m ≥ 0 the entries a_{n,k} with indices that satisfy n + k = m are the coefficients of (z + x)^{m}.

The product P^{T}(x)P (z) is not defined for all pairs (x, z). The convergence of the series involved in the multiplication requires some conditions on x and z.

If we take z = x = 1 then A becomes the classical Pascal triangle written as a symmetric matrix whose entries in the main diagonal are the central binomial coefficients. Notice that P (1) is the Pascal triangle written as a lower triangular matrix.

We describe next a simple way to generalize the matrix A introducing a diagonal matrix as a factor. Let c_{0}, c_{1}, c_{2}, … be a sequence of complex numbers and let E = Diag(c_{0}, c_{1}, c_{2}, …), that is,

E = [\begin{matrix}c_{0} & 0 & 0 & 0 & 0 & … \\ 0 & c_{1} & 0 & 0 & 0 & … \\ 0 & 0 & c_{2} & 0 & 0 & … \\ 0 & 0 & 0 & c_{3} & 0 & … \\ 0 & 0 & 0 & 0 & c_{4} & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Let B = P (z)EP^{T}(x). Then we have

B = [\begin{matrix}c_{0} & c_{0}x & c_{0}x^{2} & c_{0}x^{3} & … \\ c_{0}z & c_{0}zx + c_{1} & c_{0}zx^{2} + 2c_{1}x & c_{0}zx^{3} + 3c_{1}x^{2} & … \\ c_{0}z^{2} & c_{0}z^{2}x + 2c_{1}z & c_{0}z^{2}x^{2} + 4c_{1}zx + c_{2} & c_{0}z^{2}x^{3} + 6c_{1}zx^{2} + 3c_{2} & … \\ c_{0}z^{3} & c_{0}z^{3}x + 3c_{1}z^{2} & c_{0}z^{3}x^{2} + 6c_{1}z^{2}x + 3c_{2}z & c_{0}z^{3}x^{3} + 9c_{1}z^{2}x^{2} + 9c_{2}zx + c_{3} & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

The definition of B gives us

b_{n,k} = ∑_{j=0}^{min(n,k)} \binom{n}{j}\binom{k}{j}c_{j}z^{n−j}x^{k−j}.  (1)

Let us note that b_{n,n} = c_{n} plus a function that depends only on c_{0}, c_{1}, …, c_{n−1}, z, x. This fact clearly implies that for any pair (z, x) and any given sequence r_{0}, r_{1}, r_{2}, … we can find a unique sequence c_{0}, c_{1}, c_{2}, … such that b_{n,n} = r_{n} for n ≥ 0.

Let D_{z} and D_{x} denote the operators of differentiation with respect to z and x, respectively. Then equation (1) can be written as

b_{n,k} = ∑_{j≥0} c_{j} \frac{D_{z}^{j}}{j!} \frac{D_{x}^{j}}{j!} z^{n} x^{k}.

Using the Leibniz rule we obtain the equations

\frac{D_{z}^{j−1}}{(j − 1)!}z^{n−1} = \frac{D_{z}^{j}}{j!} z^{n} − z \frac{D_{z}^{j}}{j!} z^{n−1}, \frac{D_{x}^{j−1}}{(j − 1)!}x^{k−1} = \frac{D_{x}^{j}}{j!} x^{k} − x\frac{D_{x}^{j}}{j!} x^{k−1}.

Multiplying these equations we obtain

\frac{D_{z}^{j−1}D_{x}^{j−1}}{((j − 1)!)^{2}} z^{n−1}x^{k−1} = \frac{D_{z}^{j}}{j!} \frac{D_{x}^{j}}{j!} z^{n}x^{k} + zx\frac{D_{z}^{j}}{j!} \frac{D_{x}^{j}}{j!} z^{n−1}x^{k−1} − z \frac{D_{z}^{j}}{j!} \frac{D_{x}^{j}}{j!} z^{n−1}x^{k} − x\frac{D_{z}^{j}}{j!} \frac{D_{x}^{j}}{j!} z^{n}x^{k−1}.

This equation gives us the recurrence relation

b_{n,k} = b̂_{n−1,k−1} + zb_{n−1,k} + xb_{n,k−1} − zxb_{n−1,k−1},  n ≥ 1, k ≥ 1,  (2)

where

b̂_{n,k} = ∑_{j≥0} c_{j+1}\binom{n}{j}\binom{k}{j}z^{n−j}x^{k−j}.

Compare this equation with (1) and note the shift in the indices of the c_{i}. This means that the numbers b̂_{n,k} are the entries of B̂ = P (z)Diag(c_{1}, c_{2}, c_{3}, …)P^{T}(x).

The definition of B also gives us P^{−1}(z)B = EP^{T}(x) and B(P^{T}(x))^{−1} = P (x)E. Notice that all the matrix products in both equations are well defined. Since P^{−1}(z) = P (−z), the first equation yields

∑_{j=0}^{n} \binom{n}{j}(−z)^{n−j}b_{j,k} = c_{n}\binom{k}{n}x^{k−n}.

In particular, if k = n we get the relation

b_{n,n} = c_{n} − ∑_{j=0}^{n−1} \binom{n}{j}(−z)^{n−j}b_{j,n},  (3)

which expresses b_{n,n} in terms of the preceding entries in the n-th column of B. From the equation B(P^{T}(x))^{−1} = P (x)E we obtain an analogous result.

For m ≥ 1 let B_{m} denote the initial m × m section of B, that is, B_{m} = [b_{n,k}], where 0 ≤ n ≤ m − 1 and 0 ≤ k ≤ m − 1. Since B_{m} is the product of the initial m × m sections of P (z), E, and P^{T}(x), it is clear that det(B_{m}) = det(E_{m}) = c_{0}c_{1} ⋯ c_{m−1}. Note that det(B_{m}) is independent of z and x.

For certain sequences c_{0}, c_{1}, c_{2}, … and pairs (z, x) the corresponding matrices B have interesting combinatorial properties. For example, if z = x = 1 and c_{k} = k! then the matrix B is

B = [\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & … \\ 1 & 2 & 3 & 4 & 5 & 6 & … \\ 1 & 3 & 7 & 13 & 21 & 31 & … \\ 1 & 4 & 13 & 34 & 73 & 136 & … \\ 1 & 5 & 21 & 73 & 209 & 501 & … \\ 1 & 6 & 31 & 136 & 501 & 1546 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

The sequences on the diagonals of B, starting with the main diagonal, correspond to the sequences \underline{A002720}, \underline{A000262}, \underline{A052852}, \underline{A062147}, and \underline{A062266} of Sloane’s On-line Encyclopedia of Integer Sequences [10]. The recurrence relation (2) yields connections among those sequences.

If we take z = x = 1 and c_{k} = k + 1 for k ≥ 0 the matrix B is

[\begin{matrix}1 & 1 & 1 & 1 & 1 & … \\ 1 & 3 & 5 & 7 & 9 & … \\ 1 & 5 & 12 & 22 & 35 & … \\ 1 & 7 & 22 & 50 & 95 & … \\ 1 & 9 & 35 & 95 & 210 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}]

The sequence (b_{2,k}) is \underline{A000326}, called pentagonal numbers. The sequence (b_{3,k}) is \underline{A002412}, called hexagonal pyramidal numbers. The sequence (b_{4,k}) is \underline{A002418}, called 4dim figurate numbers, and the sequence (b_{5,k}) is \underline{A051843}.

We obtain another interesting example when we take z = x = 1 and c_{k} equal to the k-th Fibonacci number. In Section 3, we take c_{k} = u^{k} for k ≥ 0, where u is a nonzero complex number, and we obtain the generalized Delannoy arrays.

3 Generalized Delannoy matrices

In this section we study the family of generalized Delannoy matrices that we obtain using the construction presented in Section 2. The generalized Delannoy matrices have been studied by several authors using the Riordan matrix approach, or considering combinatorial problems related with weighted lattice paths.

We consider now sequences (c_{k})_{k≥0} that are geometric progressions of the form c_{k} = u^{k}, for k ≥ 0, where u is a nonzero number. For u ≠ 0 let E(u) = Diag(1, u, u^{2}, u^{3}, …). Then uE(u) = Diag(u, u^{2}, u^{3}, …).

Let us define the matrix

D(z, u, x) = P (z)E(u)P^{T}(x), z, x, u ∈ ℂ, u ≠ 0.

The matrix D(z, u, x) is called generalized Delannoy matrix. It is a particular case of the matrices studied in Section 2. Note that D(z, u, x) = D^{T}(x, u, z) and also that D(1, 1, 0) is the classic Pascal lower triangular matrix, D(z, 1, 0) = P (z), and D(1, 1, 1) is the symmetric Pascal matrix.

The three factors P (z), E(u), and P^{T}(x) are invertible infinite matrices, but in general, D(z, u, x) is not invertible, because the product P^{T}(−x)E(1/u)P (−z) may not be defined. However, if we compute the product P^{T}(−x)(E(1/u)(P (−z)D(z, u, x))), in the order indicated by the parenthesis, then we obtain the infinite identity matrix.

In order to simplify the notation we will denote the entries of D(z, u, x) just by d_{n,k}. The matrix D̂(z, u, x) that corresponds to the shifted sequence u, u^{2}, u^{3}, … is equal to uD(z, u, x), and therefore the recurrence relation (2) becomes in this case

d_{n,k} = zd_{n−1,k} + xd_{n,k−1} + (u − zx)d_{n−1,k−1},  n, k ≥ 1.  (4)

This is the recurrence satisfied by the weighted Delannoy paths from (0, 0) to (n, k) on the lattice ℕ × ℕ, that are constructed using the steps (1, 0), with weight z, (0, 1), with weight x, and (1, 1), with weight u − xz. Several authors have studied such weighted paths. See, for example, the papers by Cheon, Kim, and Shapiro [5], and Ramírez and Sirvent [8].

The explicit formula (1) becomes

d_{n,k} = ∑_{j=0}^{k} \binom{n}{j}\binom{k}{j}u^{j}z^{n−j}x^{k−j}.  (5)

Compare this formula with the formula for the entries of the lower triangular Pascal-like matrices constructed by Barry [3, Sec. 2] using Riordan matrices with one parameter.

Using (3) and (5) we obtain

d_{n,n} = u^{n} − ∑_{j=0}^{n−1} \binom{n}{j}(−z)^{n−j}d_{j,n} = ∑_{j=0}^{n} \binom{n}{j}^{2}u^{j}(zx)^{n−j}, n ≥ 1.

The first sum gives the n-th central generalized Delannoy number in terms of the preceding terms in the n-th column. The second sum is an explicit formula for d_{n,n} in terms of the parameters z, u, x.

It is easy to verify that, if y ≠ 0, then the main diagonals of the matrices D(z, u, x), D(y, zx, u/y), and D(y, u, zx/y) coincide.

The classical Delannoy matrix \underline{A008288} is

D(1, 2, 1) = [\begin{matrix}1 & 1 & 1 & 1 & 1 & … \\ 1 & 3 & 5 & 7 & 9 & … \\ 1 & 5 & 13 & 25 & 41 & … \\ 1 & 7 & 25 & 63 & 129 & … \\ 1 & 9 & 41 & 129 & 321 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .  (6)

For any nonzero y the matrices D(y, 1, 2/y) and D(y, 2, 1/y) have the same main diagonal as D(1, 2, 1).

It is well-known that the entries in the main diagonal of D(1, 2, 1), usually called central Delannoy numbers, are values of the Legendre polynomials at 3. Hetyei [7] found expressions in terms of Jacobi polynomials for the entries of a matrix that he calls asymmetric Delannoy matrix. Such matrix is just D(1, 1, 2), has the same central entries as D(1, 2, 1), and is essentially the same as the array \underline{A049600}. We show next that the entries of all the generalized Delannoy matrices D(z, u, x) can be expressed in terms of Jacobi polynomials.

The Jacobi polynomials with parameters α and β have the explicit formula

p_{n}^{(α,β)}(t) = ∑_{j=0}^{n} \binom{n + α + β + j}{j}\binom{n + α}{n − j} (\frac{t − 1}{2})^{j} ,  n ≥ 0.  (7)

Theorem 1. If u − zx is not zero let a = (u + zx)/(u − zx). Then

d_{n,k} = z^{n−k}(u − zx)^{k}p_{k}^{(n−k,0)}(a),  n ≥ k ≥ 0.  (8)

If u = zx let r(n, k) be the leading coefficient of p_{k}^{(n−k,0)}(t). Then

d_{n,k} = z^{n}(2x)^{k}r(n, k),  n ≥ k ≥ 0.  (9)

Proof. From (7) we obtain

p_{k}^{(n−k,0)}(a) = ∑_{j=0}^{k} \binom{k}{j}\binom{n + j}{k} (\frac{zx}{u − zx})^{j} ,

and therefore

z^{n−k}(u − zx)^{k}p_{k}^{(n−k,0)}(a) = z^{n}x^{k} ∑_{j=0}^{k} \binom{k}{j}\binom{n + j}{k} (\frac{u}{zx} − 1)^{k−j} .  (10)

On the other hand

d_{n,k} = z^{n}x^{k} ∑_{j=0}^{k} \binom{k}{j}\binom{n}{j} (\frac{u}{zx})^{j} .  (11)

Let v = \frac{u}{zx} − 1. Then

(\frac{u}{zx})^{j} = (v + 1)^{j} = ∑_{i=0}^{j} \binom{j}{i}v^{i}.

Substitution of this expression in (11) gives

d_{n,k} = z^{n}x^{k} ∑_{j=0}^{k} ∑_{i=0}^{j} \binom{k}{j}\binom{n}{j}\binom{j}{i}v^{i}.  (12)

Changing the summation order and using the identity

\binom{k}{j}\binom{j}{i} = \binom{k}{i}\binom{k − i}{k − j},

we obtain from (12)

d_{n,k} = z^{n}x^{k} ∑_{i=0}^{k} \binom{k}{i} (∑_{j=i}^{k} \binom{n}{j}\binom{k − i}{k − j}) v^{i}.

By the Vandermonde identity the second sum is equal to \binom{n+k−i}{k}. Therefore d_{n,k} is equal to the expression in the right-hand side of (10), with j replaced by k − i. This completes the proof of (8).

In order to prove (9) we write (8) in the form

d_{n,k} = z^{n−k}(u + zx)^{k}a^{−k}p_{k}^{(n−k,0)}(a) = z^{n−k}(u + zx)^{k}p̂_{k}^{(n−k,0)}(1/a),

where p̂_{k}^{(n−k,0)} is the reversed polynomial of p_{k}^{(n−k,0)}. If u goes to zx then a goes to infinity and 1/a goes to zero. The constant term of p̂_{k}^{(n−k,0)} is equal to the leading coefficient of p_{k}^{(n−k,0)}.

Let d_{n,k} denote the entries of D(z, u, x), and let a = (u + zx)/(u − zx). We define the series

g(t) = ∑_{n=0}^{∞} d_{n,n}t^{n} = ∑_{n=0}^{∞}(u − zx)^{n}p_{n}^{(0,0)}(a)t^{n}.

The polynomials p_{n}^{(0,0)} are the Legendre polynomials and have the generating function

\frac{1}{\sqrt{1 − 2wv + v^{2}}} = ∑_{n=0}^{∞} p_{n}^{(0,0)}(w)v^{n}.

Taking v = (u − zx)t and w = a we obtain

g(t) = \frac{1}{\sqrt{1 − 2(u + zx)t + (u − zx)^{2}t^{2}}} ,

which is the generating function of the central generalized Delannoy numbers d_{n,n} with parameters z, u, x.

The sums of the entries on the anti-diagonals of D(z, u, x) are

s_{n} = ∑_{k=0}^{n} d_{n−k,k}, n ≥ 0.

Let h(t) be the generating function of the sequence (s_{n})_{n≥0}, that is,

h(t) = ∑_{n=0}^{∞} s_{n}t^{n}.

Using the explicit formula for the entries d_{n−k,k} it is easy to see that

h(t)(1 − (z + x)t + (zx − u)t^{2}) = 1,

and therefore h(t) is

h(t) = \frac{1}{1 − (z + x)t + (zx − u)t^{2}} = ∑_{n=0}^{∞} s_{n}t^{n}.

Notice that h(t) is a rational function of t with quadratic denominator and coefficients that depend on the parameters z, u, x. There are many sequences of numbers and polynomials that have generating functions that are rational functions with quadratic denominator, for example, the Chebyshev polynomials. Therefore, replacing the parameters z, u, x by suitable polynomials we can construct matrices D(z, u, x) whose sums s_{n} are some known polynomial sequences. Cheon, Kim, and Shapiro [5] present several examples of such polynomial sequences.

4 Generalized Schröder matrices

Define the shift matrix S by

S = [\begin{matrix}0 & 0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & … \\ 0 & 0 & 1 & 0 & 0 & … \\ 0 & 0 & 0 & 1 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] ,

and let R = S^{T}. Note that RS = I, the infinite identity matrix, but SR is not the identity since its (0, 0) entry is zero. All the other entries on the main diagonal of SR are equal to 1. If A is an infinite matrix then multiplication of A by S or R, either on the left or on the right, produces a shift of A of one step in one of the four directions. That is, SA is A moved one step downwards and with the 0-th row equal to zero; AS moves A one step to the left and the 0-th column disappears; RA moves A one step upwards and the 0-th row disappears; and AR is A moved one step to the right and with the 0-th column equal to zero.

The matrices D(z, u, x) satisfy the recurrence relation (4). Using the shift matrices S and R we can write the recurrence relation (4) as the matrix equation

RD(z, u, x)S = xRD(z, u, x) + zD(z, u, x)S + (u − xz)D(z, u, x).

The generalized Delannoy matrix D(z, u, x) satisfies the recurrence relation (4) and the entries of D(z, u, x) in the 0-th row and the 0-th column are the boundary values. It is clear that any matrix obtained by applying some of the shifts described above to D(z, u, x) must also satisfy the recurrence relation (4), and so does any linear combination of such shifted matrices. Let us consider next a simple example.

For z ≠ 0 we define G(z, u, x) = D(z, u, x) − (x/z)RD(z, u, x)R. Let g_{n,k} denote the entries of G(z, u, x). Then we have g_{n,k} = d_{n,k} − (x/z)d_{n+1,k−1} and

G(z, u, x) = [\begin{matrix}1 & 0 & −ux/z & −2ux^{2}/z & … \\ z & u & 0 & −xu(zx_{u})/z & … \\ z^{2} & 2uz & u(zx + u) & 0 & … \\ z^{3} & 3uz^{2} & zu(2xz + 3u) & u(x^{2}z^{2} + 3uxz + u^{2}) & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

The lower triangular part of G(z, u, x) satisfies (4) with boundary values equal to zero on the diagonal entries with indices (n, n + 1), for n ≥ 0, and the values 1, z, z^{2}, … in the 0-th column. The upper triangular part also satisfies (4) with boundary values equal to zero in the positions (n, n + 1) and the values −ux/z, −2ux^{2}/z, … in the 0-th row.

The particular case

G(1, 2, 1) = [\begin{matrix}1 & 0 & −2 & −4 & −6 & … \\ 1 & 2 & 0 & −6 & −16 & … \\ 1 & 4 & 6 & 0 & −22 & … \\ 1 & 6 & 16 & 22 & 0 & … \\ 1 & 8 & 30 & 68 & 90 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] ,  (13)

obtained from the classical Delannoy matrix D(1, 2, 1), displayed in (6), has the classical Schröder matrix \underline{A033877} as its lower triangular part. Because of the symmetry of the Delannoy matrix D(1, 2, 1) the upper triangular part of G(1, 2, 1) is the negative of the transpose of G(1, 2, 1), shifted one step upwards.

The matrices G(z, u, x) satisfy the recurrence (4) and include the classical Schröder matrix. We call the matrices G(z, u, x) generalized Schröder matrices.

Let us consider another example.

G(2, 3, 1/2) = [\begin{matrix}1 & 0 & −3/4 & −3/4 & −9/16 & … \\ 2 & 3 & 0 & −3 & −33/8 & … \\ 4 & 12 & 12 & 0 & −57/4 & … \\ 8 & 36 & 66 & 57 & 0 & … \\ 16 & 96 & 252 & 372 & 300 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

The sequence in the main diagonal of G(2, 3, 1/2) is \underline{A047891}. Note that all the entries in the lower triangular part are integers.

Two different generalized Schröder matrices can coincide in the main diagonal. For example, G(1, 2, 2) and G(2, 2, 1) have the sequence \underline{A151374} as the main diagonal, and G(1, 3, 2) and G(2, 3, 1) have \underline{A103210} as the main diagonal.

We can see from the definition of G(z, u, x) that its entries can be expressed in terms of Jacobi polynomials.

We will use next certain commutation properties of the Pascal matrices P (z) to obtain other matrix expressions for the generalized Schröder matrices.

The Pascal matrices satisfy

RP (z) = P (z)(zI + R)

and

P^{T}(x)R = R(I + xR)^{−1}P^{T}(x).

Therefore

\frac{x}{z}RD(z, u, x)R = \frac{x}{z}P (z)(zI + R)E(u)R(I + xR)^{−1}P^{T}(x),

and after some simplifications we obtain

G(z, u, x) = P (z)E(u) (I − \frac{ux}{z}R^{2}) (I + xR)^{−1}P^{T}(x).  (14)

The matrix (I − \frac{ux}{z}R^{2})(I + xR)^{−1} is an upper triangular invertible Toeplitz matrix and represents a multiplication operator on the space of formal power series. The matrix E(u) = Diag(1, u, u^{2}, …) corresponds to the substitution operator t → ut. Therefore the product E(u)(I − \frac{ux}{z}R^{2})(I + xR)^{−1} is a Riordan matrix and (14) describes its connection with the generalized Schröder matrix G(z, u, x). The construction of G(z, u, x) in (14) can be generalized as follows. Let M(f, g) be a Riordan matrix and let z and x be complex numbers. Then P (z)M(f, g)P^{T}(x) can be considered as a more general Schröder matrix. We do not study such generalization in the present paper.

Using commutation properties of the Pascal matrices with functions of R we obtain another construction for G(z, u, x) as follows. Let

U(z, u, x) = I − xR − \frac{ux}{z}R^{2}(I − xR)^{−1}.  (15)

U(z, u, x) is an upper triangular invertible Toeplitz matrix and satisfies

(I − \frac{ux}{z}R^{2}) (I + xR)^{−1}P^{T}(x) = P^{T}(x)U(z, u, x).

Therefore, from (14) and the definition of D(z, u, x) we get

G(z, u, x) = D(z, u, x)U(z, u, x).  (16)

We can also determine U(z, u, x) by computing P^{T}(−x)(E(1/u)(P (−z)G(z, u, x))) in the order determined by the parenthesis. This is equivalent to the multiplication of G(z, u, x) on the left by the “inverse” of D(z, u, x).

If u ≠ 0 then every finite initial section of D(z, u, x) is invertible and thus so is every finite initial section of G(z, u, x). Since the determinants of all the finite sections of U(z, u, x) are equal to 1, it is clear that the determinants of corresponding initial sections of D(z, u, x) and G(z, u, x) are equal.

We present next some simple examples. From (15) we obtain

U(1, 2, 1) = [\begin{matrix}1 & −1 & −2 & −2 & −2 & … \\ 0 & 1 & −1 & −2 & −2 & … \\ 0 & 0 & 1 & −1 & −2 & … \\ 0 & 0 & 0 & 1 & −1 & … \\ 0 & 0 & 0 & 0 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] ,

and multiplying the classical Delannoy matrix D(1, 2, 1) of (6) on the right by U(1, 2, 1) we obtain the Schröder matrix G(1, 2, 1) that appears in (13).

Another simple example of a generalized Schröder matrix is

D(1, 1, 1)U(1, 1, 1) = [\begin{matrix}1 & 0 & −1 & −2 & −3 & … \\ 1 & 1 & 0 & −2 & −5 & … \\ 1 & 2 & 2 & 0 & −5 & … \\ 1 & 3 & 5 & 5 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

The lower triangular part of this matrix is the classical Catalan triangle \underline{A009766}. The Delannoy matrix D(1, 1, 1) is the symmetric classical Pascal triangle and

U(1, 1, 1) = [\begin{matrix}1 & −1 & −1 & −1 & … \\ 0 & 1 & −1 & −1 & … \\ 0 & 0 & 1 & −1 & … \\ 0 & 0 & 0 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Using the explicit formula (5) for the entries of D(z, u, x) and the definition of G(z, u, x), or alternatively, using (16) and the easily obtained explicit expression for the entries of U(z, u, x), we obtain the explicit formula for the entries g_{n,k} of G(z, u, x). It is

g_{n,k} = \frac{n − k + 1}{n + 1} ∑_{j=1}^{k−1} \binom{n + 1}{j}\binom{k − 1}{j − 1}z^{n−j}x^{k−j}u^{j} + \binom{n}{k}z^{n−k}u^{k}.  (17)

We can see from (17) that the central generalized Schröder numbers are given by

g_{n,n} = \frac{1}{n} ∑_{j=1}^{n} \binom{n}{j}\binom{n}{j − 1}z^{n−j}x^{n−j}u^{j}.

It is easy to verify that g_{n,n} is equal to the coefficient of t^{n−1} in the expression as a linear combination of powers of t of the polynomial

\frac{1}{nzx}(t + u)^{n}(t + zx)^{n}.

Using the well-known expression for the central Catalan numbers C_{n} we see that, if u = zx and u ≠ 0 then g_{n,n} = C_{n}u^{n}. The generating function of the central Catalan numbers is

h_{c}(t) = ∑_{n=0}^{∞} C_{n}t^{n} = \frac{1 − \sqrt{1 − 4t}}{2t},

and satisfies

\frac{1}{h_{c}(t)} + t h_{c}(t) = 1.  (18)

Let h(t) be the generating function of the central generalized Schröder numbers, that is,

h(t) = ∑_{n=0}^{∞} g_{n,n}t^{n}.

We will show that h(t) satisfies an equation analogous to (18). Let ĥ(t) = ∑_{n=0}^{∞} e_{n}t^{n} be the reciprocal of h(t). Then, since g_{0,0} = 1, we have e_{0} = 1, and

∑_{k=0}^{n} g_{k,k} e_{n−k} = 0, n ≥ 1,

and thus

e_{n} = − ∑_{k=1}^{n} g_{k,k} e_{n−k}, n ≥ 1.

This recurrence relation gives

e_{1} = −g_{1,1}, e_{2} = −zxg_{1,1}, e_{3} = −zxg_{2,2}, …, e_{n} = −zxg_{n−1,n−1}, …

and therefore

zxt h(t) + ĥ(t) = 1 − (u − zx)t.

Multiplying by h(t) both sides of this equation we obtain

zxt h^{2}(t) − (1 − (u − zx)t)h(t) + 1 = 0.  (19)

Solving this quadratic equation we obtain the generating function of the central generalized Schröder numbers

h(t) = \frac{1 − (u − zx)t − \sqrt{1 − 2(u + zx)t + (u − zx)^{2}t^{2}}}{2zxt} .  (20)

The minus sign just before the square root in (20) is the correct choice to obtain h(t). If we take u = zx in the previous equation then h(t) becomes

h(t) = \frac{1 − \sqrt{1 − 4zxt}}{2zxt},

which is the generating function of the central generalized Catalan numbers C_{n}z^{n}x^{n}.

Since the right-hand side of (19) is zero, the coefficient of t^{n+1} in the left-hand side of (19) is zero for n ≥ 0. Therefore

zx ∑_{k=0}^{n} g_{k,k}g_{n−k,n−k} − g_{n+1,n+1} + (u − zx)g_{n,n} = 0,

and this equation gives us the recurrence relation

g_{n+1,n+1} = (u − zx)g_{n,n} + zx ∑_{k=0}^{n} g_{k,k}g_{n−k,n−k}.

This formula gives every central generalized Schröder number in terms of the preceding ones. It is an extension of a result obtained by Brualdi and Kirkland [4, Lemma 4.2] using combinatorial methods.

If z is not zero then G_{2} = D(z, u, x) − (x/z)^{2}R^{2}D(z, u, x)R^{2} is well defined and satisfies the recurrence relation (4). Furthermore, the entries of G_{2} in the diagonal with indices (n, n + 2), for n ≥ 0, are all equal to zero. If D(z, u, x) is the classical Delannoy matrix then

G_{2} = [\begin{matrix}1 & 1 & 0 & −4 & −12 & … \\ 1 & 3 & 4 & 0 & −16 & … \\ 1 & 5 & 12 & 16 & 0 & … \\ 1 & 7 & 24 & 52 & 68 & … \\ 1 & 9 & 40 & 116 & 236 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

The part of this matrix to the left of the diagonal of zeros is a Hessenberg matrix. The sequence 1, 4, 16, 68, … in the diagonal to the right of the main diagonal is the sequence \underline{A006319}, called royal paths in a lattice. The sequence in the main diagonal is \underline{A268208}, and the sequence in the diagonal below the main one is \underline{A110190}.

The construction of G_{2} is generalized as follows. For k ≥ 1 let

G_{k} = D(z, u, x) − (x/z)^{k}R^{k}D(z, u, x)R^{k}.

The matrix G_{k} satisfies the recurrence (4) and all its entries in the diagonal with indices (n, n + k), for n ≥ 0, are equal to zero. Such matrices can be seen as the solutions of the recurrence relation (4) with boundary values equal to zero on some diagonal to the right of the main diagonal. The rest of the boundary is the union of the 0-th column and the first k − 1 positions of the 0-th row.

There are other ways to construct matrices with interesting properties using the generalized Delannoy matrices and the Toeplitz matrices U(x, u, z). For example, forming products of the form D(z, u, x)U(t, v, w), with (z, u, x) ≠ (t, v, w), or differences such as D(z, u, x) − D(t, v, w), or G(z, u, x) − G(t, v, w).

5 Conclusions

We studied some Pascal-like infinite matrices that contain all the generalized Delannoy and Schröder matrices. We described the structure of the matrices and how we obtain Schröder matrices from Delannoy matrices. We also obtained expressions for the entries of the Delannoy matrices in terms of Jacobi polynomials, and explicit formulas and generating functions for the central generalized Delannoy and Schröder numbers. We described a connection of our construction with certain simple Riordan matrices and a possible way to construct more general matrices using other Riordan matrices. Transforming our matrices to the lower triangular form we obtain a set of matrices that contains the Pascal-like matrices introduced recently by Barry [3].

References

[1] C. Banderier and S. Schwer, Why Delannoy numbers?, J. Statist. Plann. Inference 135 (2005), 40–54.

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

[3] P. Barry, The central coefficients of a family of Pascal-like triangles and colored lattice paths, J. Integer Sequences 22 (2019), Article 19.1.3.

[4] R. Brualdi and S. Kirkland, Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers, J. Combin. Theory Ser. B 94 (2005), 334–351.

[5] G.-S. Cheon, H. Kim, and L. W. Shapiro, A generalization of Lucas polynomial sequence, Discrete Appl. Math. 157 (2009), 920–927.

[6] M. Dziemiańczuk, Generalizing Delannoy numbers via counting weighted lattice paths, Integers 13 (2013), Article A54.

[7] G. Hetyei, Central Delannoy numbers and balanced Cohen-Macauley complexes, Ann. Combin. 10 (2006), 443–462.

[8] J. L. Ramírez and V. F. Sirvent, Generalized Schröder matrix and its combinatorial interpretation, Linear Multilinear Algebra 66 (2018), 418–433.

[9] J. Schröder, Generalized Schröder numbers and the rotation principle, J. Integer Sequences 10 (2007), Article 07.7.7.

[10] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, Published elec-

tronically at https://oeis.org.

[11] R. A. Sulanke, Objects counted by the central Delannoy numbers, J. Integer Sequences 6 (2003), Article 03.1.5.

[12] W.-J. Woan, Hankel matrices and lattice paths, J. Integer Sequences 4 (2001), Article 01.1.2.

[13] L. Yang, S.-L. Yang, and T.-X. He, Generalized Schröder matrices arising from enumeration of lattice paths, Czechoslovak Math. J. 70 (145) (2020), 411–433.

[14] S.-L. Yang, S.-N. Zheng, S.-P. Yuan, and T.-X. He, Schröder matrix as inverse of Delannoy matrix, Linear Algebra Appl. 439 (2013), 3605–3614.

2020 Mathematics Subject Classification: Primary 15B36; Secondary 05A10, 05a15, 11B37, 11B83, 33c45. Keywords: Delannoy array, Schröder array, recurrence relation, generating function, lattice path, Jacobi polynomial.

(Concerned with sequences \underline{A000262}, \underline{A000326}, \underline{A002412}, \underline{A002418}, \underline{A002720}, \underline{A006319}, \underline{A008288}, \underline{A009766}, \underline{A033877}, \underline{A047891}, \underline{A049600}, \underline{A051843}, \underline{A052852}, \underline{A062147}, \underline{A062266}, \underline{A103210}, \underline{A110190}, \underline{A151374}, and \underline{A268208}.)

Received August 15 2020; revised version received March 4 2021; March 5 2021; March 6 2021; March 12 2021. Published in Journal of Integer Sequences, March 12 2021.

Return to Journal of Integer Sequences home page.