Generating Functions via Hankel and Stieltjes Matrices

Paul Peart and Wen-Jin Woan

Department of Mathematics Howard University Washington D.C. 20059

Email address: pp@scs.howard.edu

Abstract

When the Hankel matrix formed from the sequence 1, a_{1}, a_{2}, ... has an LDL^{T} decomposition, we provide a constructive proof that the Stieltjes matrix S_{L} associated with L is tridiagonal. In the important case when L is a Riordan matrix using ordinary or exponential generating functions, we determine the specific form that S_{L} must have, and we demonstrate, constructively, a oneto-one correspondence between the generating function for the sequence and S_{L}. If L is Riordan when using ordinary generating functions, we show how to derive a recurrence relation for the sequence.

Keywords. Hankel matrix, Stieltjes matrix, ordinary generating function, exponential generating function, Riordan matrix, LDU decomposition, tridiagonal matrix.

1. Introduction

For each sequence in a large class of important combinatorial sequences, we can derive a closed form expression for an ordinary or exponential generating function starting with the associated Hankel matrix or Stieltjes matrix. In this paper we give explicit relationships between the generating function, the Hankel matrix and the Stieltjes matrix. We also provide several illustrative examples. In [3], some work was done using the Hankel matrix approach, but the conditions under which the method would work were not determined, or were only implicitly conjectured. In the present paper we use the Stieltjes matrix to obtain significant improvements in the analysis and application of the method.

Our basic assumption is that the Hankel matrix generated by the sequence has an LDU factorization, where L is a lower triangular matrix with all diagonal elements equal to one, U = L^{T} , and D is a diagonal matrix with all diagonal elements nonzero. The Hankel matrix generated by the sequence a_{0}, a_{1}, a_{2}, ..., is given by the infinite matrix

H = [ \begin{matrix}a_{0} & a_{1} & a_{2} & a_{3} & a_{4} & . \\ a_{1} & a_{2} & a_{3} & a_{4} & a_{5} & . \\ a_{2} & a_{3} & a_{4} & a_{5} & a_{6} & . \\ a_{3} & a_{4} & a_{5} & a_{6} & a_{7} & . \\ a_{4} & a_{5} & a_{6} & a_{7} & a_{8} & . \\ . & . & . & . & . & . \end{matrix} ] .

Without loss of generality we take a_{0} = 1. A necessary and sufficient condition for H to have an LDU factorization is that H be positive definite. When L is a Riordan matrix (see Section 2) using ordinary or exponential generating functions, our method will find a closed form expression for the generating function of the sequence 1, a_{1}, a_{2}, a_{3}, ... In the the ordinary generating function case we can then use [4] to find a recurrence relation for the sequence.

Example 1. Delannoy numbers: 1, 3, 13, 63, 321, 1683, ... This is sequence A1850 in [5]. See also [1, p. 81]. We apply Gaussian elimination to the Hankel matrix to obtain

H = [ \begin{matrix}1 & 3 & 13 & 63 & 321 & . \\ 3 & 13 & 63 & 321 & 1683 & . \\ 13 & 63 & 321 & 1683 & 8989 & . \\ 63 & 321 & 1683 & 8989 & 48639 & . \\ 321 & 1683 & 8989 & 48639 & 265729 & . \\ . & . & . & . & . & . \end{matrix} ] =

[ \begin{matrix}1 & & & & & . \\ 3 & 1 & & & & . \\ 13 & 6 & 1 & & & . \\ 63 & 33 & 9 & 1 & & . \\ 321 & 180 & 62 & 12 & 1 & . \\ . & . & . & . & . & . \end{matrix} ] [ \begin{matrix}1 & & & & & . \\ & 4 & & & & . \\ & & 8 & & & . \\ & & & 16 & & . \\ & & & & 32 & . \\ . & . & . & . & . & . \end{matrix} ] [ \begin{matrix}1 & 3 & 13 & 63 & 321 & . \\ & 1 & 6 & 33 & 180 & . \\ & & 1 & 9 & 62 & . \\ & & & 1 & 12 & . \\ & & & & 1 & . \\ . & . & . & . & . & . \end{matrix} ] .

The Stieltjes matrix S_{L} associated with L is the matrix S_{L} = L^{−1}\overline{L}, where \overline{L} is obtained from L by deleting the first row. (See Section 2 for more details about the Stieltjes matrix.) In Example 1,

S_{L} = [ \begin{matrix}3 & 1 & & & & . \\ 4 & 3 & 1 & & & . \\ & 2 & 3 & 1 & & . \\ & & 2 & 3 & 1 & . \\ & & & 2 & 3 & . \\ . & . & . & . & . & . \end{matrix} ] .

From its definition S_{L} gives the rule of formation of L. Specifically, it gives a rule for obtaining the n^{th} row of L from the previous row. In the example, we have for n ≥ 1

l_{n0} = 3l_{n−1,0} + 4l_{n−1,1}
l_{nk} = l_{n−1,k−1} + 3l_{n−1,k} + 2l_{n−1,k+1} , k ≥ 1 .

It is convenient to define the leftmost column of L to be the zeroth column, and the first row to be the zeroth row. We say that the zeroth column of L has a {3, 4} rule of formation and that the k^{th} column, k ≥ 1, has a {1, 3, 2} rule of formation. Notice that the zeroth column of L contains the Delannoy numbers and that S_{L} is tridiagonal. In Section 2 we prove that whenever H = LDU, then S_{L} is tridiagonal. From Theorem 2 in Section 2 we see that the Delannoy numbers have a closed-form ordinary generating function given by

g(x) = \frac{1}{1 − 3x − 4xf} = \frac{1}{\sqrt{1 − 6x + x^{2}}} ,

where

f(x) = x(1 + 3f + 2f^{2}) = \frac{1 − 3x − \sqrt{1 − 6x + x^{2}}}{4x} .

Since S_{L} is tridiagonal and L is a Riordan matrix, we can use [4] to obtain for the Delannoy numbers the recurrence

na_{n} = 3(4n − 3)a_{n−1} − 19(2n − 3)a_{n−2} + 3(4n − 9)a_{n−3} − (n − 3)a_{n−4};
for n ≥ 4, with a_{0} = 1, a_{1} = 3, a_{2} = 13, a_{3} = 63 .

Example 2. Bell numbers: 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, ... This sequence illustrates the exponential generating function case. It is sequence A110 in [5]. Here

L = [ \begin{matrix}1 & & & & & . \\ 1 & 1 & & & & . \\ 2 & 3 & 1 & & & . \\ 5 & 10 & 6 & 1 & & . \\ 15 & 37 & 31 & 10 & 1 & . \\ . & . & . & . & . & . \end{matrix} ] and S_{L} = [ \begin{matrix}1 & 1 & & & & . \\ 1 & 2 & 1 & & & . \\ & 2 & 3 & 1 & & . \\ & & 3 & 4 & 1 & . \\ & & & 4 & 5 & . \\ . & . & . & . & . & . \end{matrix} ] .

From Theorem 3 in Section 2, the form of S_{L} indicates that the exponential generating function g(x) of the Bell numbers is given by

ln(g) = ∫ (1 + f)dx, g(0) = 1,

where

f′(x) = 1 + f(x), f(0) = 0.

So we obtain

f(x) = e^{x} − 1 and g(x) = e^{e^{x}−1}.

We have found that the method works for many other important combinatorial sequences. These include

• the Catalan numbers: 1, 1, 2, 5, 14, 42, 132, 429, … (sequence A108)

• the shortened Catalan sequence: 1, 2, 5, 14, 42, 132, 429, …

• the Catalan numbers interspersed with zeros: 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, …

• central binomial coefficients: 1, 2, 6, 20, 70, 252, , 924, 3432, … (A984)

• central trinomial coefficients: 1, 1, 3, 7, 19, 51, 141, … (A2426),

• Schröder’s numbers: 1, 2, 6, 22, 90, 394, 1806, … (A6318)

• Schröder’s second problem: 1, 1, 3, 11, 45, 197, 903, 4279, … (A1003)

• gamma numbers or Motzkin sums: 1, 0, 1, 1, 3, 6, 15, 36, 91, 232, … (A5043)

• Fine numbers: 1, 0, 1, 2, 6, 18, 57, 186, 622, … (A957)

• directed animals: 1, 2, 5, 13, 35, 96, 267, 750, 2123, … (A5773)

• telephone numbers, or self-inverse permutations: 1, 1, 2, 4, 10, 26, 76, 232, 764, … (A85)

• derangement numbers: 1, 0, 1, 2, 9, 44, 265, 1854, 14833, … (A166).

In Section 2 we show that whenever H = LDU then S_{L} is always tridiagonal, and we give the specific form of S_{L}. Theorem 2 in that section indicates the specific form that S_{L} must have for L to be a Riordan matrix with ordinary generating functions. Theorem 3 indicates the specific form that S_{L} must have for L to be Riordan with exponential generating functions. In Section 3 we give some further examples.

2. Definitions and Theorems

Definition. The Hankel matrix H = (h_{nk})_{n,k≥0} generated by the sequence 1, a_{1}, a_{2}, a_{3}, ... is given by

h_{00} = 1, h_{nk} = a_{n+k} for n ≥ 0, k ≥ 0.

Definition. Let L = (l_{nk})_{n,k≥0} be a lower triangular matrix with l_{ii} = 1 for all i ≥ 0 . The Stieltjes matrix S_{L} associated with L is given by S_{L} = L^{−1}\overline{L}, where \overline{L} is obtained from L by deleting the first row of L. That is, the element in the n^{th} row and k^{th} column of \overline{L} is given by

\overline{l}_{nk} = l_{n+1,k} .

Remark. We note that S_{L} is unique, and so

S_{L} = SL̃ ⇔ L = L̃ .

Remark. If S_{L} = (s_{ik})_{i,k≥0} then

l_{nk} = ∑_{i≥o} s_{ik}l_{n−1,i} for n ≥ 1 .

That is, from S_{L} , we obtain a rule for computing the n^{th} row of L from the (n − 1)^{th} row.

Remark. S_{L} is tridiagonal if and only if there exist sequences {λ_{k}}_{k≥0} , and {μ_{k}}_{k≥0} such that

l_{n0} = λ_{0}l_{n−1,0} + μ_{0}l_{n−1,1} for n ≥ 1,
l_{nk} = l_{n−1,k−1} + λ_{k}l_{n−1,k} + μ_{k}l_{n−1,k+1} for k ≥ 1 and n ≥ 1,

and

s_{00} = λ_{0}, s_{10} = μ_{0} , and for k ≥ 1 , s_{kk} = λ_{k} , s_{k+1,k} = μ_{k} .

Definition. A Riordan matrix with ordinary generating functions is a lower triangular matrix for which the generating function for the k^{th} column, k ≥ 0, is given by g(x)[f(x)]^{k} , where

g(x) = 1 + g_{1}x + g_{2}x^{2} + ⋯ and f(x) = x + f_{2}x^{2} + f_{3}x^{3} + ⋯

Definition. A Riordan matrix with exponential generating functions is a lower triangular matrix for which the generating function for the k^{th} column, k ≥ 0, is given by \frac{1}{k!}g(x)[f(x)]^{k} , where

g(x) = 1 + g_{1}x + g_{2} \frac{x^{2}}{2!} + g_{3} \frac{x^{3}}{3!} + ⋯ and f(x) = x + f_{2} \frac{x^{2}}{2!} + f_{3} \frac{x^{3}}{3!} + · · · .

See [2] for a detailed description of Riordan matrices. In [6] Woodson explores other kinds of Riordan matrices.

Theorem 1. Let H = (h_{nk})_{n,k≥0} be the Hankel matrix generated by the sequence 1, a_{1}, a_{2}, a_{3}, ... Assume that H = LDU where

L = (l_{nk})_{n,k≥0} = [ \begin{matrix}1 & & & & & . \\ l_{10} & 1 & & & & . \\ l_{20} & l_{21} & 1 & & & . \\ l_{30} & l_{31} & l_{32} & 1 & & . \\ l_{40} & l_{41} & l_{42} & l_{43} & 1 & . \\ . & . & . & . & . & . \end{matrix} ] ,

D = [ \begin{matrix}d_{0} & & & & & . \\ & d_{1} & & & & . \\ & & d_{2} & & & . \\ & & & d_{3} & & . \\ & & & & d_{4} & . \\ . & . & . & . & . & . \end{matrix} ]  d_{i} ≠ 0 for all i,  U = L^{T} .

That is,

h_{nk} = ∑_{i=0}^{k} d_{i}l_{ki}l_{ni} .

Then the Stieltjes matrix S_{L} is tridiagonal with the form

S_{L} = [ \begin{matrix}λ_{0} & 1 & & & & . \\ μ_{0} & λ_{1} & 1 & & & . \\ & μ_{1} & λ_{2} & 1 & & . \\ & & μ_{2} & λ_{3} & 1 & . \\ & & & μ_{3} & λ_{4} & . \\ . & . & . & . & . & . \end{matrix} ] ,

where

λ_{0} = a_{1} , μ_{0} = d_{1} , λ_{k} = l_{k+1,k} − l_{k,k−1} , μ_{k} = \frac{d_{k+1}}{d_{k}} , k ≥ 1 .

Proof. We will prove that

l_{n0} = a_{1}l_{n−1,0} + d_{1}l_{n−1,1}

and

l_{nk} = l_{n−1,k−1} + λ_{k}l_{n−1,k} + μ_{k}l_{n−1,k+1} for all k ≥ 1.

We use induction on k. From the definition of the Hankel matrix,

h_{nk} = h_{n−1,k+1} for all k ≥ 0 and n ≥ 1

h_{n0} = h_{n−1,1} ⇔ d_{0}l_{n0} = d_{0}l_{n−1,0}l_{10} + d_{1}l_{n−1,1}l_{11} ⇔ l_{n0} = a_{1}l_{n−1,0} + d_{1}l_{n−1,1} . h_{n1} = h_{n−1,2} ⇔ d_{0}l_{10}l_{n0} + d_{1}l_{11}l_{n1} = d_{0}l_{20}l_{n−1,0} + d_{1}l_{21}l_{n−1,1} + d_{2}l_{22}l_{n−1,2}

⇔ d_{1}l_{n1} = l_{20}l_{n−1,0} − l_{10}l_{n0} + d_{1}l_{21}l_{n−1,1} + d_{2}l_{n−1,2}
⇔ d_{1}l_{n1} = d_{1}l_{n−1,0} + d_{1}(l_{21} − l_{10})l_{n−1,1} + d_{2}l_{n−1,2}
⇔ l_{n1} = l_{n−1,0} + λ_{1}l_{n−1,1} + μ_{1}l_{n−1,2}

Now assume that

l_{ni} = l_{n−1,i−1} + λ_{i}l_{n−1,i} + μ_{i}l_{n−1,i+1} for 1 ≤ i ≤ k − 1 .

Then

h_{nk} = h_{n−1,k+1} ⇔ ∑_{i=0}^{k} d_{i}l_{ki}l_{ni} = ∑_{i=0}^{k+1} d_{i}l_{k+1,i}l_{n−1,i}
⇔ ∑_{i=0}^{k−1} d_{i}l_{ki}l_{ni} − ∑_{i=0}^{k−1} d_{i}l_{k+1,i}l_{n−1,i} + d_{k}l_{nk} = d_{k}l_{k+1,k}l_{n−1,k} + d_{k+1}l_{n−1,k+1}
⇔ d_{0}l_{k0}l_{n0} + ∑_{i=1}^{k−1} d_{i}l_{ki}l_{ni} − [d_{0}l_{k+1,0}l_{n−1,0} + ∑_{i=1}^{k−1} d_{i}l_{k+1,i}l_{n−1,i}] + d_{k}l_{nk}
= d_{k}l_{k+1,k}l_{n−1,k} + d_{k+1}l_{n−1,k+1}
⇔ d_{0}l_{k0} [a_{1}l_{n−1,0} + d_{1}l_{n−1,1}] + ∑_{i=1}^{k−1} d_{i}l_{ki}l_{ni}

− [d_{0}(a_{1}l_{k0} + d_{1}l_{k1})l_{n−1,0} + ∑_{i=1}^{k−1} d_{i}l_{k+1,i}l_{n−1,i}] + d_{k}l_{nk}

= d_{k}l_{k+1,k}l_{n−1,k} + d_{k+1}l_{n−1,k+1}
⇔ d_{1}l_{k0}l_{n−1,1} + ∑_{i=1}^{k−1} d_{i}l_{ki}l_{ni} − [d_{1}l_{k1}l_{n−1,0} + ∑_{i=1}^{k−1} d_{i}l_{k+1,i}l_{n−1,i}] + d_{k}l_{nk}
= d_{k}l_{k+1,k}l_{n−1,k} + d_{k+1}l_{n−1,k+1}
⇔ d_{1}l_{k0}l_{n−1,1} + ∑_{i=1}^{k−1} d_{i}l_{ki} [l_{n−1,i−1} + λ_{i}l_{n−1,i} + \frac{d_{i+1}}{d_{i}} l_{n−1,i+1}]

− [d_{1}l_{k1}l_{n−1,0} + ∑_{i=1}^{k−1} d_{i}l_{n−1,i} [l_{k,i−1} + λ_{i}l_{ki} + \frac{d_{i+1}}{d_{i}} l_{k,i+1}]] + d_{k}l_{nk}

= d_{k}l_{k+1,k}l_{n−1,k} + d_{k+1}l_{n−1,k+1}
⇔ d_{1}l_{k0}l_{n−1,1} + ∑_{i=1}^{k−1} d_{i}l_{ki}l_{n−1,i−1} + ∑_{i=1}^{k−1} d_{i+1}l_{ki}l_{n−1,i+1}

− [d_{1}l_{k1}l_{n−1,0} + ∑_{i=1}^{k−1} d_{i}l_{k,i−1}l_{n−1,i} + ∑_{i=1}^{k−1} d_{i+1}l_{k,i+1}l_{n−1,i}] + d_{k}l_{nk}

= d_{k}l_{k+1,k}l_{n−1,k} + d_{k+1}l_{n−1,k+1}
⇔ d_{1} [l_{k0}l_{n−1,1} + l_{k1}l_{n−1,0} − l_{k1}l_{n−1,0} − l_{k0}l_{n−1,1}]

+d_{2} [l_{k2}l_{n−1,1} + l_{k1}l_{n−1,2} − l_{k1}l_{n−1,2} − l_{k2}l_{n−1,1}] +d_{3} [l_{k3}l_{n−1,2} + l_{k2}l_{n−1,3} − l_{k2}l_{n−1,3} − l_{k3}l_{n−1,2}] ...... ...... +d_{k−1} [l_{k,k−1}l_{n−1,k−2} + l_{k,k−2}l_{n−1,k−1} − l_{k,k−2}l_{n−1,k−1} − l_{k,k−1}l_{n−1,k−2}] +d_{k} [l_{k,k−1}l_{n−1,k} − l_{kk}l_{n−1,k−1}] + d_{k}l_{nk}

= d_{k}l_{k+1,k}l_{n−1,k} + d_{k+1}l_{n−1,k+1}

⇔ d_{k}l_{nk} = d_{k}l_{n−1,k−1} + d_{k} [l_{k+1,k} − l_{k,k−1}] l_{n−1,k} + d_{k+1}l_{n−1,k+1}
⇔ l_{nk} = l_{n−1,k−1} + λ_{k}l_{n−1,k} + μ_{k}l_{n−1,k+1}

When S_{L} has λ_{i} = λ and μ_{i} = μ for all i ≥ 1 we can obtain an ordinary generating function for the sequence 1, a_{1}, a_{2}, ...

Theorem 2. Let H be the Hankel matrix generated by the sequence 1, a_{1}, a_{2}, ..., and let H = LDL^{T}. Then S_{L} has the form

S_{L} = [ \begin{matrix}a_{1} & 1 & & & & . \\ d_{1} & λ & 1 & & & . \\ & μ & λ & 1 & & . \\ & & μ & λ & 1 & . \\ & & & μ & λ & . \\ . & . & . & . & . & . \end{matrix} ] ,

if and only if the ordinary generating function g(x) of the sequence 1, a_{1}, a_{2}, ... is given by

g(x) = \frac{1}{1 − a_{1}x − d_{1}xf} ,

where

f = x(1 + λf + μf^{2}) , f(0) = 0.

Proof. We note that μ ≠ 0 and

f = \frac{1 − λx − \sqrt{(1 − λx)^{2} − 4μx}}{2μx} .

Consider the lower triangular matrix L̃ such that the generating function for the k^{th} column is g(x)[f(x)]^{k}, k ≥ 0.

g(x) = \frac{1}{1 − a_{1}x − d_{1}xf} ⇔ g(x) = 1 + a_{1}xg(x) + d_{1}xgf
⇔ l̃_{00} = 1 and [x^{n}] g = a_{1} [x^{n}] xg + d_{1} [x^{n}] xgf
⇔ l̃_{00} = 1 and l̃_{n0} = a_{1}l̃_{n−1,0} + d_{1}l̃_{n−1,1} for n ≥ 1.

Also, for k ≥ 1 ,

f = x(1 + λf + μf^{2}) ⇔ gf^{k} = xgf^{k−1} + λxgf^{k} + μxgf^{k+1}
⇔ [x^{n}] gf^{k} = [x^{n}] xgf^{k−1} + λ [x^{n}] xgf^{k} + μ [x^{n}] xgf^{k+1}
⇔ l̃_{nk} = l̃_{n−1,k−1} + λl̃_{n−1,k} + μl̃_{n−1,k+1} .

Therefore S_{L} has the given form if and only if S_{L} = SL̃ ⇔ L = L̃.

We now turn to the exponential generating function case. We get an exponential generating function for the sequence 1, a_{1}, a_{2}, ... when the sequences \{λ_{i}\}_{i≥0} and \{\frac{μ_{i}}{i+1}\}_{i≥0} are arithmetic sequences.

Theorem 3. Let H be the Hankel matrix generated by the sequence 1, a_{1}, a_{2}, ..., and let H = LDL^{T} . Then S_{L} has the form given in Theorem 1. If {λ_{i}}_{i≥0}, is an arithmetic sequence with common difference λ and \{\frac{μ_{i}}{i+1}\}_{i≥0} an arithmetic sequence with common difference μ , then the exponential generating function g(x) for the sequence 1, a_{1}, a_{2}, ... is given by

ln(g) = ∫ (a_{1} + d_{1}f)dx , g(0) = 1,

where f is given by

f′ = 1 + λf + μf^{2} , f(0) = 0 .

Proof. Consider the lower triangular matrix L̂ with \frac{1}{k!}g(x)[f(x)]^{k} for the exponential generating function of the k^{th} column, k ≥ 0. We note that L̂ is a Riordan matrix with exponential generating functions.

ln(g) = ∫ (a_{1} + d_{1}f)dx ⇒ g′ = a_{1}g + d_{1}fg ⇒ [\frac{x^{n}}{n!} ] g′ = a_{1} [\frac{x^{n}}{n!} ] g + d_{1} [\frac{x^{n}}{n!} ] fg
⇒ l̂_{n+1,0} = a_{1}l̂_{n0} + d_{1}l̂_{n1} ⇒ l̂_{n0} = λ_{0}l̂_{n−1,0} + μ_{0}l̂_{n−1,1}

For k ≥ 1 ,

(\frac{gf^{k}}{k!} )′ = \frac{g′f^{k}}{k!} + \frac{gf^{k−1}f′}{(k − 1)!} = \frac{a_{1}gf^{k}}{k!} + \frac{d_{1}gf^{k+1}}{k!} + \frac{gf^{k−1} + λgf^{k} + μgf^{k+1}}{(k − 1)!}
= (a_{1} + λk)\frac{gf^{k}}{k!} + (d_{1} + μk)\frac{gf^{k+1}}{k!} + \frac{gf^{k−1}}{(k − 1)!}
= \frac{gf^{k−1}}{(k − 1)!} + λ_{k} \frac{gf^{k}}{k!} + \frac{μ_{k}}{k + 1} \frac{gf^{k+1}}{k!} .

Therefore

[\frac{x^{n}}{n!} ] (\frac{gf^{k}}{k!} )′ = [\frac{x^{n}}{n!} ] (\frac{gf^{k−1}}{(k − 1)!} + λ_{k} \frac{gf^{k}}{k!} + μ_{k} \frac{gf^{k+1}}{(k + 1)!}) .

That is,

l̂_{n+1,k} = l̂_{n,k−1} + λ_{k}l̂_{nk} + μ_{k}l̂_{n,k+1} ,
l̂_{nk} = l̂_{n−1,k−1} + λ_{k}l̂_{n−1,k} + μ_{k}l̂_{n−1,k+1} .

Therefore S_{L} has the given form if and only if L = L̂.

3. Further Examples

Example 3. Derangements: 1, 0, 1, 2, 9, 44, 265, 1854, 14833, ... This is sequence A166 in [5]. H = LDL^{T} and

S_{L} = [ \begin{matrix}0 & 1 & & & & . \\ 1 & 2 & 1 & & & . \\ & 4 & 4 & 1 & & . \\ & & 9 & 6 & 1 & . \\ & & & 16 & 8 & . \\ . & . & . & . & . & . \end{matrix} ] .

This is the exponential case with λ_{k} = 2k and μ_{k} = (k +1)^{2}. Therefore λ = 2 and μ = 1. So f′ = 1 + 2f + f^{2} with f(0) = 0. That gives f = \frac{x}{1−x} and ln(g) = ∫ fdx , g(0) = 1. So

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

Example 4. Here we start with a Stieltjes matrix having the form in Theorem 3. The associated sequence is 1,3,10,39,187,1128,8455, ... (sequence A54912 in [5]).

S_{L} = [ \begin{matrix}3 & 1 & & & & . \\ 1 & 6 & 1 & & & . \\ & 6 & 9 & 1 & & . \\ & & 15 & 12 & 1 & . \\ & & & 28 & 15 & . \\ . & . & . & . & . & . \end{matrix} ] .

Here S_{L} has the form in Theorem 3 with λ = 3 and μ = 2. Therefore the exponential generating function for the sequence in the leftmost column of L is given by ln(g) = ∫ (3+f)dx, g(0) = 1 where f′ = 1+3f +2f^{2}, f(0) = 0. We get f = \frac{e^{x}−1}{2−e^{x}} and

g(x) = \sqrt{\frac{e^{5x}}{2 − e^{x}}} = 1+3x+10\frac{x^{2}}{2!} +39\frac{x^{3}}{3!} +187\frac{x^{4}}{4!} +1128\frac{x^{5}}{5!} +8455\frac{x^{6}}{6!} +O(x^{7})

We can also use Theorem 1 to construct L and D. Recall that d_{i+1} = μ_{i}d_{i}, and that d_{0} = 1.

Acknowledgements

We thank the other members of the Howard University Combinatorics Group (Seyoum Getu, Louis Shapiro, Leon Woodson and Asamoah Nkwanta) for their helpful suggestions and encouragement.

References

1. L. Comtet. Advanced Combinatorics. D. Reidel Publishing Company, 1974.

2. S. Getu, L. W. Shapiro, W.-J. Woan, & L. C. Woodson. The Riordan Group. Discrete Applied Mathematics, 34 (1991), 229-239.

3. S. Getu, L. W. Shapiro, W.-J. Woan, & L. C. Woodson. How to Guess a Generating Function. SIAM Journal on Discrete Mathematics, 5 (1992), 497-499.

4. P. Peart, & L. C. Woodson. Triple Factorization of some Riordan Matrices. Fibonacci Quarterly, 31 (1993), 121-128.

5. N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. Published electronically at http://www.research.att.com/∼njas/sequences/.

6. L. C. Woodson. Infinite Matrices, C_{n}-Functions and Umbral Calculus. Ph.D. Thesis. Howard University, 1991.

(Concerned with sequences A108, A166, A957, A984, A1003, A1850, A2426, A5773, A6318, A54912.)

Received May 15, 1999; published in Journal of Integer Sequences June 4, 2000.

Return to Journal of Integer Sequences home page.