On the Central Coefficients of Riordan Matrices

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract

We use the Lagrange-Bürmann inversion theorem to characterize the generating function of the central coefficients of the elements of the Riordan group of matrices. We apply this result to calculate the generating function of the central elements of a number of explicit Riordan arrays, defined by rational expressions, and in two cases we use the generating functions thus found to calculate the Hankel transforms of the central elements, which are themselves expressible as combinatorial polynomials. We finally look at two cases of Riordan arrays defined by non-rational expressions. The last example uses our methods to calculate the generating function of \binom{3n}{n}.

1 Introduction

The central coefficients of many common (ordinary) Riordan arrays play an important role in combinatorics. For instance, the central terms of the Pascal triangle, defined by the Riordan array (\frac{1}{1−t}, \frac{t}{1−t}), are the central binomial coefficients \binom{2n}{n} \underline{A000984}, with a multitude of combinatorial interpretations. Similarly, the central elements of the Delannoy triangle, (\frac{1}{1−t}, \frac{t(1+t)}{1−t}) are the central Delannoy numbers ∑_{k=0}^{n} \binom{n}{k}^{2}2^{k} \underline{A001850}, again with many combinatorial interpretations. It is interesting therefore to be able to give the generating function of such central terms in a systematic way. In two recent papers [2, 6], it has been shown how to find the generating function of the central elements of elements of the Bell subgroup of the Riordan group. For instance, the Pascal triangle (\frac{1}{1−t}, \frac{t}{1−t}) is an element of this subgroup. In this note, we shall extend this result to arbitrary elements of the Riordan group. We first recall the result concerning the Bell subgroup that we wish to extend. We use the notation f̄(t) to denote the compositional inverse of the power series f (where f(0) = 0). This is the unique function such that f(f̄(t)) = f̄(f(t)) = t.

Theorem 1. Let (d(t), td(t)) be an element of the Bell subgroup of the Riordan group of matrices R. If d_{n,k} denotes the (n, k)-th element of this matrix, then we have

d_{2n,n} = (n + 1)[t^{n}]\frac{1}{t}\overline{(\frac{t}{d(t)})}(t).

Corollary 2. If d_{n,k} denotes the general term of the Bell matrix (d(t), td(t)), then the generating function of the central terms d_{2n,n} is given by

\frac{d}{dt}\overline{(\frac{t}{d(t)})}.

Example 3. The most well-known example of a Bell matrix (see later) is the Binomial matrix B with general element d_{n,k} = \binom{n}{k}. As a member of the Riordan group of matrices, this is

B = (\frac{1}{1 − t}, \frac{t}{1 − t}) .

Then the generating function of d_{2n,n} = \binom{2n}{n} is given by

\frac{d}{dt}\overline{t(1 − t)} = \frac{d}{dt} \frac{1 − \sqrt{1 − 4t}}{2} = \frac{1}{\sqrt{1 − 4t}}.

The next section provides a brief review of integer sequences, the Lagrange-Bürmann inversion theorem, and Riordan arrays, and may be skipped by those familiar with these notions. We then announce and prove our general result, and finally we look at some examples.

Many interesting examples of sequences and Riordan arrays can be found in Neil Sloane’s On-Line Encyclopedia of Integer Sequences (OEIS), [12, 13]. Sequences are frequently referred to by their A-number in the OEIS.

2 Integer sequences, Lagrange Inversion and Riordan arrays

For an integer sequence a_{n}, that is, an element of ℤ^{ℕ}, the power series f(t) = ∑_{k=0}^{∞} a_{k}t^{k} is called the ordinary generating function or g.f. of the sequence. a_{n} is thus the coefficient of t^{n} in this series. We denote this by a_{n} = [t^{n}]f(t). For instance, F_{n} = [t^{n}]\frac{t}{1−t−t^{2}} is the n-th Fibonacci number \underline{A000045}, while C_{n} = [t^{n}]\frac{1−\sqrt{1−4t}}{2t} is the n-th Catalan number \underline{A000108}. The properties and examples of use of the notation [t^{n}] can be found in [9].

For a power series f(t) = ∑_{n=0}^{∞} a_{n}t^{n} with f(0) = 0 and f′(0) ≠ 0 we define the reversion or compositional inverse of f to be the power series f̄(t) (also written as f^{[−1]}(t)) such that f(f̄(t)) = t. We sometimes write f̄ = Revf.

The following is the version of Lagrange inversion that we shall need [8, 15].

Theorem 4. (Lagrange-Bürmann Inversion). Suppose that a formal power series w = w(t) is implicitly defined by the relation w = tϕ(w), where ϕ(t) is a formal power series such that ϕ(0) ≠ 0. Then, for any formal power series F (t),

[t^{n}]F (w(t)) = \frac{1}{n}[t^{n−1}]F′(t)(ϕ(t))^{n}.

In the sequel, we shall be interested in the Hankel transform of the central terms that we shall meet. The Hankel transform [5, 7] 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 of the form

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

then the Hankel transform of a_{n} is given by [5]

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

The Riordan group [3, 11, 14], is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions d(t) = 1 + d_{1}t + d_{2}t^{2} + … and h(t) = h_{1}t + h_{2}t^{2} + … where h_{1} ≠ 0 [14]. The corresponding matrix is the matrix whose i-th column is generated by d(t)h(t)^{i} (the first column being indexed by 0). The matrix corresponding to the pair d, h is denoted by (d, h). The group law, which corresponds to matrix multiplication, is then given by

(d, h) · (f, g) = (d, h)(f, g) = (d(f ∘ h), g ∘ h).

The identity for this law is I = (1, t) and the inverse of (d, h) is

(d, h)^{−1} = (1/(d ∘ h̄), h̄),

where h̄ is the compositional inverse of h. We denote by R the group of Riordan matrices. If M is the matrix (d, h), and a = (a_{0}, a_{1}, …)^{T} is an integer sequence with ordinary generating function A(t), then the sequence Ma has ordinary generating function d(t)A(h(t)). The (infinite) matrix (d, h) can thus be considered to act on the ring of integer sequences ℤ^{ℕ} by multiplication, where a sequence is regarded as a (infinite) column vector. We can extend this action to the ring of power series ℤ[[t]] by

(d, h) : A(t) ↦ (d, h) · A(t) = d(t)A(h(t)).

Example 5. The so-called binomial matrix B \underline{A007318} is the element (\frac{1}{1−t}, \frac{t}{1−t}) of the Riordan group. It has general element \binom{n}{k}, and hence as an array coincides with Pascal’s triangle. More generally, B^{m} is the element (\frac{1}{1−mt}, \frac{t}{1−mt}) of the Riordan group, with general term \binom{n}{k}m^{n−k}. We find that the inverse B^{−m} of B^{m} is given by (\frac{1}{1+mt}, \frac{t}{1+mt}).

The Bell subgroup of R is the set of matrices of the form

(d(t), td(t)).

Note that

(d(t), td(t))^{−1} = (\frac{\overline{td}}{t}, \overline{td}) .

An interesting sequence characterization of Bell matrices may be found in [4].

3 The main result

The main result of this note is the following.

Theorem 6. Let (d(t), h(t)) = (d(t), tf(t)) be an element of the Riordan group of matrices R (with f(0) ≠ 0). Let d_{n,k} denote the (n, k)-th element of this matrix, and let v(t) denote the power series (with v(0) = 0)

v(t) = \overline{(\frac{t}{f(t)})}.

Then the generating function of the central term sequence d_{2n,n} is given by

\frac{d(v(t))}{f(v(t))} \frac{d}{dt}v(t).

Proof. We let d_{n,k} denote the general element of the Riordan array (d(t), tf(t)). Then we have

d_{2n,n} = [t^{2n}]d(t)(tf(t))^{n}
= [t^{2n}]t^{n}d(t)f(t)^{n}
= [t^{n}]\frac{d(t)}{f(t)}f(t)^{n+1}
= (n + 1)\frac{1}{n + 1}[t^{n}]F′(t)f(t)^{n+1},

where F′(t) = \frac{d(t)}{f(t)}. Applying the Lagrange-Bürmann inversion theorem, we obtain

d_{2n,n} = (n + 1)[t^{n+1}]F (v(t))
= [t^{n}]F′(v(t))v′(t)
= [t^{n}]\frac{d(v(t))}{f(v(t))} \frac{d}{dt}v(t).

4 Examples

Example 7. We look at the matrix

(\frac{1}{1 − 2t}, \frac{t(1 − 2t)}{1 − 3t}) .

The central elements of this matrix begin 1, 3, 15, 90, 579, 3858, . . .. In this case, we have

v(t) = \overline{(\frac{t}{f(t)})} = \overline{(\frac{t(1 − 3t)}{1 − 2t})}.

Thus v(t) is the appropriate solution (with v(0) = 0) of the equation

\frac{v(1 − 3v)}{1 − 2v} = t.

We find that

v(t) = \frac{1 + 2t − \sqrt{1 − 8t + 4t^{2}}}{6} .

We also have that

\frac{d(t)}{f(t)} = \frac{1 − 3t}{(1 − 2t)^{2}} .

The generating function of d_{2n,n} is thus given by

\frac{d(v(t))}{f(v(t))} \frac{d}{dt}v(t) = \frac{1 + 4t + \sqrt{1 − 8t + 4t^{2}}}{2\sqrt{1 − 8t + 4t^{2}}} .

We can generalize this result to the case of the Riordan array

(\frac{1}{1 − rt}, \frac{t(1 − rt)}{1 − (r + 1)t}) .

We find in this case that the central term sequence d_{2n,n} is generated by

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

The general element of (\frac{1}{1−rt}, \frac{t(1−rt)}{1−(r+1)t}) is given by

d_{n,k} = [t^{n}]\frac{1}{1 − rt} (\frac{t(1 − rt)}{1 − (r + 1)t})^{k} ,

which gives us the expression

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

The bivariate generating function

\frac{1 + rt + \sqrt{1 − 2(y + 2)t + y^{2}t^{2}}}{2\sqrt{1 − 2(y + 2)t + y^{2}t^{2}}}

is the generating function of the lower-triangular matrix with general element

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

and so we also have

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

We note that this matrix begins

( \begin{matrix}1 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & ⋯ \\ 3 & 4 & 1 & 0 & ⋯ \\ 10 & 18 & 9 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We finish this example by offering the following conjecture for the form of the Hankel transform h_{n} of d_{2n,n} [7].

h_{n} = (r + 1)^{⌈ \frac{n^{2}}{2} ⌉} ∑_{k=0}^{⌊ \frac{n}{2} ⌋} 4^{k}r^{k} ∑_{j=0}^{n−2k} \binom{2k + j + 1}{j}\binom{n − j − 1}{n − 2k − j}.

Example 8. In this example, we start with the Riordan array

(\frac{1}{1 − 2t}, \frac{t(1 − 3t)}{1 − 2t}) .

Then

\frac{v(1 − 2v)}{1 − 3v} = t

gives us

v(t) = \frac{1 − 3t − \sqrt{1 − 14t + 9t^{2}}}{4} ,

while in this case we have

\frac{d(t)}{f(t)} = \frac{1}{1 + 3t}.

We obtain that the sequence of central terms d_{2n,n}, which begins

1, 7, 69, 763, 8881, 106407, 1298949, 16065483, …,

has generating function

\frac{1}{\sqrt{1 − 14t + 9t^{2}}} .

This sequence is \underline{A084774}. It corresponds to the central coefficients of (1 + 7t + 10t^{2})^{n}. We now look at the general case of the matrix

(\frac{1}{1 − rt}, \frac{t(1 − (r + 1)t}{1 − rt}) .

We obtain

v(t) = \frac{1 − (1 + r)t − \sqrt{1 − 2(1 + 3r)t + (r + 1)^{2}t^{2}}}{2r} ,

and

\frac{d(t)}{f(t)} = \frac{1}{1 + (1 + r)t}.

We find that the central term sequence d_{2n,n} is generated by

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

We can then show [10] that

d_{2n,n} = [t^{n}](1 + (3r + 1)t + r(r + 1)t^{2})^{n},

and

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

We have

\frac{1}{\sqrt{1 − 2(3r + 1)t + (r + 1)^{2}t^{2}}} = \frac{1}{1 − (3r + 1)t − \frac{2r(r + 1)t^{2}}{1 − (3r + 1)t − \frac{r(r + 1)t^{2}}{1 − (3r + 1)t − ⋯}}}.

This shows that the Hankel transform of d_{2n,n} in this instance is given by

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

Example 9. We finish this section by looking at the Pascal-like triangles [1] given by

(\frac{1}{1 − t}, \frac{t(1 + rt)}{1 − t}) .

We have

\frac{v(1 − v)}{1 + rv} = t,

and hence

v(t) = \frac{1 − rt + \sqrt{1 − 2(r + 2)t + r^{2}t^{2}}}{2} ,

and

\frac{d(t)}{f(t)} = \frac{1}{1 + rt}.

We find that the generating function of d_{2n,n} is given by

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

which [10] shows that

d_{2n,n} = [t^{n}](1 + (r + 2)t + (r + 1)t^{n})^{n},

with

d_{2n,n} = ∑_{k=0}^{n} \binom{n}{k}\binom{2n − k}{n}r^{k}.

We have

\frac{1}{\sqrt{1 − 2(r + 2)t + r^{2}t^{2}}} = \frac{1}{1 − (r + 2)t − \frac{2(r + 1)t^{2}}{1 − (r + 2)t − \frac{(r + 1)t^{2}}{1 − (r + 2)t − ⋯}}}.

This shows that the Hankel transform of d_{2n,n} in this instance is given by

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

5 Non-rational terms

In this section, we look at two simple examples of Riordan arrays defined by non-rational terms. In the first, the generating function of the central terms is elementary, while this is not the case for the central elements of the second array.

Example 10. We consider the Riordan array

(\frac{1}{\sqrt{1 − 4t}}, \frac{t}{c(t)}) ,

where

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

is the generating function of the Catalan numbers \underline{A000108}. This matrix begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 2 & 1 & 0 & 0 & 0 & 0 & … \\ 6 & 1 & 1 & 0 & 0 & 0 & … \\ 20 & 3 & 0 & 1 & 0 & 0 & … \\ 70 & 10 & 1 & −1 & 1 & 0 & … \\ 252 & 35 & 4 & 0 & −2 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We have

vc(v) = t,

and hence

v(t) = t(1 − t).

We have

\frac{d(t)}{f(t)} = \frac{1 − \sqrt{1 − 4t}}{2t\sqrt{1 − 4t}}.

We find that

\frac{d(v(t))}{f(v(t))} = \frac{1}{(1 − t)(1 − 2t)}.

But

(t(1 − t))′ = 1 − 2t,

and so we find that the generating function of d_{2n,n} in this case is \frac{1}{1−t}. Thus the central terms of the Riordan array (\frac{1}{\sqrt{1−4t}}, \frac{t}{c(t)}) are all equal to 1.

Example 11. For this example, we look at the array

(\frac{1}{\sqrt{1 − 4t}}, tc(t)) .

This is the matrix \underline{A092392} with general element

d_{n,k} = \binom{2n − k}{n}.

Thus we have

d_{2n,n} = \binom{3n}{2n} = \binom{3n}{n},

which begins

1, 3, 15, 84, 495, 3003, 18564, 116280, ….

This is \underline{A005809}. Solving the equation

\frac{v}{c(v)} = t,

we find that

v(t) = \frac{2}{\sqrt{3}}\sqrt{t} sin (\frac{1}{3} arcsin (\frac{1}{2}\sqrt{27t})) .

This is the g.f. of the sequence that begins

0, 1, 1, 3, 12, 55, 273, 1428, …,

or the sequence \frac{1}{2n+1} \binom{3n}{n} with a 0 at the beginning. Thus v′(t) is the g.f. of \frac{n+1}{2n+1} \binom{3n}{n}, \underline{A174687}. We have

\frac{d(t)}{f(t)} = \frac{1}{\sqrt{1 − 4t}} \frac{1}{c(t)} = \frac{1 − \sqrt{1 − 4t}}{2t\sqrt{1 − 4t}},

from which it follows that we have

\frac{d(v(t))}{f(v(t))} = \frac{1}{2} (1 + \frac{3^{1/4}}{\sqrt{\sqrt{3} − 8\sqrt{t} sin (\frac{1}{3} arcsin (\frac{\sqrt{27t}}{2}))}}) .

Thus the generating function of the central elements \binom{3n}{n} of the Riordan array

(\frac{1}{\sqrt{1 − 4t}}, tc(t))

is given by

\frac{1}{\sqrt{3}} (1 + \frac{3^{1/4}}{\sqrt{\sqrt{3} − 8\sqrt{t} sin (\frac{1}{3} arcsin (\frac{\sqrt{27t}}{2}))}}) \frac{d}{dt}\sqrt{t} sin (\frac{1}{3} arcsin (\frac{1}{2}\sqrt{27t})) .

We see that even in the case of this relatively simply defined Riordan array, the generating function of the central terms is far from elementary.

References

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

[2] P. Barry, On the central coefficients of Bell matrices, J. Integer Seq., 14 (2011), Article 11.4.3.

[3] C. Corsani, D. Merlini, and R. Sprugnoli, Left-inversion of combinatorial sums, Discrete Math., 180 (1998), 107–122.

[4] Sung-Tae Jin, A characterization of the Riordan Bell subgroup by C-sequences, Korean J. Math., 17 (2009), 147–154.

[5] C. Krattenthaler, Advanced determinant calculus: a complement, Lin. Alg. Appl., 411 (2005), 68–166.

[6] D. Kruchinin and V. Kruchinin, A method for obtaining generating functions for central coefficients of triangles, J. Integer Seq., 15 (2012), Article 12.9.3.

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

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

[9] D. Merlini, R. Sprugnoli, and M. C. Verri, The method of coefficients, Amer. Math. Monthly, 114 (2007), 40–57.

[10] T. D. Noe, On the divisibility of generalized central trinomial coefficients, J. Integer Seq., 9 (2006), Article 06.2.7.

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

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

   cally at http://oeis.org, 2013.

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

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

[15] R. P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge University Press, 2001.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 05A15, 11C20, 15B36. Keywords: Integer sequence, central coefficients, Riordan group, Lagrange inversion, Hankel transform.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A000984}, \underline{A001850}, \underline{A005809}, \underline{A007318}, \underline{A084774}, \underline{A092392}, and \underline{A174687}.)

Received January 2 2013; revised version received May 2 2013. Published in Journal of Integer Sequences, May 8 2013.

Return to Journal of Integer Sequences home page.