On the Central Coefficients of Bell Matrices

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract We use the Lagrange inversion theorem to characterize the central coefficients of matrices in the Bell subgroup of the Riordan group of matrices. We give examples of how by using different means of calculating these coefficients we can deduce the generating functions of interesting sequences.

1 Introduction

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

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

By the central coefficients of this matrix we understand the terms T_{2n,n}. In this case, we have

T_{2n,n} = \binom{2n}{n} = [x^{n}]\frac{1}{\sqrt{1 − 4x}}.

A natural question to ask is how does the defining element

\frac{1}{1 − x}

of B relate to \frac{1}{\sqrt{1−4x}} ? The answer is in fact quite simple. In this case, we form the associated Bell matrix

(1 − x, x(1 − x))

and take its inverse. This is

(c(x), xc(x)),

where c(x) = \frac{1−\sqrt{1−4x}}{2x} is the generating function of the Catalan numbers. Then we have

\binom{2n}{n} = (n + 1)[x^{n}]c(x),

or equivalently,

[x^{n}]c(x) = \frac{1}{n + 1}\binom{2n}{n} = \frac{1}{n + 1}T_{2n,n}.

We now note that

xc(x) = \overline{x(1 − x)}(x) = \overline{( \frac{x}{\frac{1}{1−x}} )}(x),

where ¯ denotes the reversion or compositional inverse. Finally, we have

T_{2n,n} = \binom{2n}{n} = (n + 1)[x^{n}]\frac{1}{x}\overline{( \frac{x}{\frac{1}{1−x}} )}(x).

The above result can be generalized to all elements of the Bell subgroup of the Riordan group of matrices. We have the following theorem, which we shall prove in section 3. Theorem 3. Let (g(x), xg(x)) be an element of the Bell subgroup of the Riordan group of matrices R. If T_{n,k} denotes the n, k-th element of this matrix, then we have

T_{2n,n} = (n + 1)[x^{n}]\frac{1}{x}\overline{(\frac{x}{g(x)})}(x).

Many interesting examples of sequences and Riordan arrays can be found in Neil Sloane’s On-Line Encyclopedia of Integer Sequences (OEIS), [8, 9]. Sequences are frequently referred to by their Annnnnn OEIS number. In the next section, we will review known results concerning integer sequences, Riordan arrays and the Bell subgroup of the group of Riordan arrays.

2 Preliminaries on integer sequences, Riordan arrays and the Bell subgroup

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

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

The Riordan group [2, 7, 10], is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions g(x) = 1 + g_{1}x + g_{2}x^{2} + … and f(x) = f_{1}x + f_{2}x^{2} + … where f_{1} ≠ 0 [10]. The corresponding matrix is the matrix whose i-th column is generated by g(x)f(x)^{i} (the first column being indexed by 0). The matrix corresponding to the pair g, f is denoted by (g, f). The group law, which corresponds to matrix multiplication, is then given by

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

The identity for this law is I = (1, x) and the inverse of (g, f) is (g, f)^{−1} = (1/(g ∘ f̄), f̄) where f̄ is the compositional inverse of f. We denote by R the group of Riordan matrices. If M is the matrix (g, f), and a = (a_{0}, a_{1}, …)′ is an integer sequence with ordinary generating function A(x), then the sequence Ma has ordinary generating function g(x)A(f(x)). The (infinite) matrix (g, f) 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 ℤ[[x]] by

(g, f) : A(x) ↦ (g, f) · A(x) = g(x)A(f(x)).

Example 2. The so-called binomial matrix B \underline{A007318} is the element (\frac{1}{1−x}, \frac{x}{1−x}) 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−mx}, \frac{x}{1−mx}) of the Riordan group, with general term \binom{n}{k}m^{n−k}. It is easy to show that the inverse B^{−m} of B^{m} is given by (\frac{1}{1+mx}, \frac{x}{1+mx}).

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

(g(x), xg(x)).

Note that

(g(x), xg(x))^{−1} = (\frac{\overline{xg}}{x} , \overline{xg}) .

We shall call a member of the Bell subgroup of R a Bell matrix. An interesting sequence characterization of Bell matrices may be found in [3].

3 Proof of the theorem

We restate the theorem and prove it in this section.

Theorem 3. Let (g(x), xg(x)) be an element of the Bell subgroup of the Riordan group of matrices R. If T_{n,k} denotes the n, k-th element of this matrix, then we have

T_{2n,n} = (n + 1)[x^{n}]\frac{1}{x}\overline{(\frac{x}{g(x)})}(x).

Proof. We let T_{n,k} denote the general element of the Bell matrix (g(x), xg(x)). Then we have

T_{2n,n} = [x^{2n}]g(x)(xg(x))^{n}
= [x^{2n}]x^{n}g(x)^{n+1}
= [x^{n}]g(x)^{n+1}
= (n + 1)\frac{1}{n + 1}[x^{n}]g(x)^{n+1}.

We now recall the Lagrange inversion theorem [5]. This says that if we have

h(w) = \frac{w}{g(w)}, g(0) ≠ 0,

then

[x^{n}]h̄(x) = \frac{1}{n}[w^{n−1}]g(w)^{n}.

Letting n → n + 1 gives

[x^{n+1}]\overline{(\frac{x}{g(x)})}(x) = \frac{1}{n + 1}[w^{n}]g(w)^{n+1},

or

[x^{n}]\frac{1}{x}\overline{(\frac{x}{g(x)})}(x) = \frac{1}{n + 1}[w^{n}]g(w)^{n+1}.

Thus we deduce that

T_{2n,n} = (n + 1)\frac{1}{n + 1}[x^{n}]g(x)^{n+1} = (n + 1)[x^{n}]\frac{1}{x}\overline{(\frac{x}{g(x)})}(x).

Corollary 4. The central coefficients T_{2n,n} of the Bell matrix (g(x), xg(x)) are given by (n + 1) times the elements of the first column of the Bell matrix

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

Proof. By the theory of the Bell subgroup, we have

(\frac{1}{g(x)}, \frac{x}{g(x)})^{−1} = (\frac{1}{x}\overline{(\frac{x}{g(x)})}, \overline{(\frac{x}{g(x)})}) .

Since T_{2n,n} = (n + 1)[x^{n}]\frac{1}{x} \overline{(\frac{x}{g(x)})} by the Theorem, the result follows.

4 Examples

In this section, we show how, by calculating T_{2n,n} in different ways, we can show that certain sequences of interest have a generating function of a given form. Normally these sequences will have the form \frac{1}{n+1}T_{2n,n}. We start with the best-known example, the Catalan numbers.

Example 5. The Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n}.

For this example, we consider, as in the introduction, the Riordan array

(\frac{1}{1 − x}, \frac{x}{1 − x}) .

We can calculate T_{2n,n} directly as follows.

T_{2n,n} = [x^{2n}]\frac{1}{1 − x} \frac{x^{n}}{(1 − x)^{n}}
= [x^{n}](1 − x)^{−n−1}
= [x^{n}] ∑_{k=0}^{∞} \binom{−n − 1}{k}(−1)^{k}x^{k}

= [x^{n}] ∑_{k=0} \binom{n + k}{k}x^{k}

= \binom{2n}{n},

as expected. Now by the theorem, we look at the first column of the matrix (1−x, x(1−x))^{−1}. We obtain

T_{2n,n} = (n + 1)[x^{n}]\frac{1}{x}\overline{( \frac{x}{\frac{1}{1−x}} )} = (n + 1)[x^{n}]\frac{1}{x} \overline{x(1 − x)}(x).

To carry out the reversion we solve u(1 − u) = x to obtain the result (with u(0) = 0) given by

u = \frac{1 − \sqrt{1 − 4x}}{2}.

Thus

T_{2n,n} = (n + 1)[x^{n}]\frac{1 − \sqrt{1 − 4x}}{2x}.

Since T_{2n,n} = \binom{2n}{n}, we obtain

C_{n} = \frac{1}{n + 1}\binom{2n}{n} = [x^{n}]\frac{1 − \sqrt{1 − 4x}}{2x}.

Example 6. The generalized Catalan numbers \frac{1}{2n+1} \binom{3n}{n}. We wish to prove the following result about the generating function of \frac{1}{2n+1} \binom{3n}{n}:

\frac{1}{2n + 1}\binom{3n}{n} = [x^{n}]\frac{2}{\sqrt{3x}} sin (\frac{arcsin (\sqrt{\frac{27x}{4}})}{3}) .

In order to do this, we calculate the central coefficients T_{2n,n} of the Catalan triangle (c(x), xc(x)) \underline{A033184} in two ways. First of all, by the theorem, they are given by (n + 1) times the first column of

(1/c(x), x/c(x))^{−1}.

Thus

T_{2n,n} = (n + 1)[x^{n}]\frac{1}{x}\overline{(\frac{x}{c(x)})}(x)

= (n + 1)[x^{n}]\frac{1}{x}\overline{(\frac{x(1 + \sqrt{1 − 4x})}{2})}(x).

Taking the solution

u = \frac{2\sqrt{x}}{\sqrt{3}} sin (\frac{arcsin (\sqrt{\frac{27x}{4}})}{3})

of the equation

\frac{u(1 + \sqrt{1 − 4u})}{2} = x,

we obtain

T_{2n,n} = (n + 1)[x^{n}]\frac{2}{\sqrt{3x}} sin (\frac{arcsin (\sqrt{\frac{27x}{4}})}{3}) .

Secondly, we now note that directly, we have

T_{2n,n} = [x^{2n}]c(x)(xc(x))^{n} = [x^{n}]c(x)^{n+1}.

Then by Formula (2.4) of [5], used backwards, we obtain

T_{2n,n} = \frac{n + 1}{n + 1 + 2n}\binom{n + 1 + 2n}{n} = \frac{n + 1}{3n + 1} \frac{(3n + 1)(3n)!}{(2n + 1)(2n)!n!} = \frac{n + 1}{2n + 1}\binom{3n}{n}.

The result follows immediately by comparing the two expressions for T_{2n,n}. Example 7. We wish to show that the sequence \underline{A001002} with general term

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

has g.f. given by

\frac{1}{3x} (4 sin (\frac{arcsin (\frac{27x+11}{6})}{3}) − 1) .

To this end, we consider the central coefficients of the Riordan array

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

By the theorem, T_{2n,n} for this array is given by (n + 1) times the first column of

((1 − x − x^{2}), x(1 − x − x^{2}))^{−1}.

Thus

T_{2n,n} = (n + 1)[x^{n}]\frac{1}{x}\overline{(x(1 − x − x^{2}))}(x)
= (n + 1)[x^{n}]\frac{1}{x} \frac{1}{3} (4 sin (\frac{arcsin (\frac{27x+11}{6})}{3}) − 1) .

On the other hand, we have

T_{2n,n} = [x^{2n}]\frac{1}{1 − x − x^{2}} \frac{x^{n}}{(1 − x − x^{2})^{n}}
= [x^{n}]\frac{1}{(1 − x − x^{2})^{n+1}}
= [x^{n}] ∑_{k=0} \binom{−n − 1}{k}(−x)^{k}(1 + x)^{k}
= [x^{n}] ∑_{k=0} \binom{n + k}{k}x^{k} ∑_{j=0}^{k} \binom{k}{j}x^{j}
= ∑_{k=0} \binom{n + k}{k}\binom{k}{n − k}.

This is \underline{A038112}. A comparison of both expressions for T_{2n,n} now yields the result. Example 8. For our next example, we will use the following result. Lemma 9. Let f(x) = \frac{x}{1+ax^{2}+bx^{2}} . Then

1.

f̄(x) = \frac{1 − ax − \sqrt{1 − 2ax + (a^{2} − 4b)x^{2}}}{2bx} ,

2.

[x^{n}]f̄(x) = ∑_{k=0} \binom{n − 1}{2k}C_{k}a^{n−2k−1}b^{k}.

Proof. The first result follows by solving the equation

\frac{u}{1 + au + bu^{2}} = x

and taking the determination for which u(0) = 0. The second result is a direct application of Lagrange inversion. We have

[x^{n}]f̄ = \frac{1}{n}[x^{n−1}](1 + ax + bx^{2})^{n}.

Expansion of the binomial now gives the result [1].

We note that this implies that

[x^{n}]\frac{1}{x} f̄(x) = ∑_{k=0} \binom{n}{2k}C_{k}a^{n−2k}b^{k}.

We now wish to study the sequence \underline{A007440} with general term

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

For this, we consider the matrix

(1 − x − x^{2}, x(1 − x − x^{2})).

For this matrix, T_{2n,n} is given by (n + 1) times the first column of

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

Equivalently

T_{2n,n} = (n + 1)[x^{n}]\frac{1}{x}\overline{(\frac{x}{1 − x − x^{2}} )}(x).

We obtain

T_{2n,n} = (n + 1)[x^{n}]\frac{\sqrt{1 + 2x + 5x^{2}} − x − 1}{2x^{2}} = [x^{n}]\frac{\sqrt{1 + 2x + 5x^{2}} − x − 1}{2x^{2}\sqrt{1 + 2x + 5x^{2}}}.

By the lemma, we also have

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

This is essentially \underline{A104506}. We now calculate T_{2n,n} directly.

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

Thus

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

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

This is the shifted reversion of the Fibonacci numbers. We remark in passing that the Hankel transform [4] of the Fibonacci reversion is −(−1)^{\binom{n+1}{2}} F (n). It is also noteworthy that the exponential generating function of T_{2n,n} = ∑_{k=0} \binom{n+1}{k}\binom{k}{n−k}(−1)^{k} is given by

\frac{d}{dx}e^{−x}I_{1}(2ix)/i, i = \sqrt{−1}.

The Hankel transform of T_{2n,n} begins

1, −4, −4, 11, 11, −29, −29, 76, 76, −199, −199, ...

where the sequence \underline{A002878} that begins 1, 4, 11, 29, 76, .... has general term L_{2n+1}.

Example 10. In our last example we wish to show that the sequence \underline{A078531} with general term

\frac{4^{n}}{n + 1}\binom{\frac{3n−1}{2}}{n}

has g.f. given by

\frac{1}{x} (\frac{1}{12} + \frac{1}{6} sin (\frac{arcsin(216x^{2} − 1)}{3})) .

To this end we consider the central coefficients of the Riordan array

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

The central coefficients T_{2n,n} of this matrix will then be given by the first column of the Riordan array

(\sqrt{1 − 4x}, x\sqrt{1 − 4x})^{−1} .

We find that

T_{2n,n} = (n + 1)[x^{n}]\frac{1}{x} (\frac{1}{12} + \frac{1}{6} sin (\frac{arcsin(216x^{2} − 1)}{3})) .

Now we can also calculate T_{2n,n} directly as:

T_{2n,n} = [x^{2n}]\frac{1}{\sqrt{1 − 4x}} \frac{x^{n}}{\sqrt{1 − 4x}^{n}}
= [x^{n}](1 − 4x)^{− \frac{n+1}{2}}
= [x^{n}] ∑_{k=0} \binom{−\frac{n+1}{2}}{k}(−1)^{k}4^{k}x^{k}

= [x^{n}] ∑_{k=0} \binom{\frac{n+1}{2} + k − 1}{k}4^{k}x^{k}

= \binom{\frac{3n−1}{2}}{n}4^{n}.

Comparison of the expressions for T_{2n,n} now gives the result.

Note that T_{2n,n} = (n + 1)\underline{A078531}(n) =\underline{A091527}(n).

5 Acknowledgements

I am grateful to an anonymous referee whose careful reading of this manuscript, along with cogent remarks, has hopefully improved the readability and usefulness of this paper.

References

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

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

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

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

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

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

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

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org, 2011.

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

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

2010 Mathematics Subject Classification: Primary 11B83; Secondary 05A15, 11C20, 15B36. Keywords: integer sequence, central coefficients, Riordan group, Bell subgroup, Bell matrix.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A001002}, \underline{A002878}, \underline{A007318}, \underline{A007440}, \underline{A033184}, \underline{A038112}, \underline{A078531}, \underline{A091527}, \underline{A104506}, and \underline{A174687}.)

Received June 29 2010; revised version received November 11 2010; March 22 2011. Published in Journal of Integer Sequences, March 26 2011.

Return to Journal of Integer Sequences home page.