Some Observations on the Lah and Laguerre Transforms of Integer Sequences

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract We study the Lah and related Laguerre transforms within the context of exponential Riordan arrays. Links to the Stirling numbers are explored. Results for finite matrices are generalized, leading to a number of useful matrix factorizations.

1 Integer sequences and transforms on them

In this note, we shall consider integer sequences

a : N_{0} → Z

with general term a_{n} = a(n). Normally, sequences will be described by either by their ordinary generating function (o.g.f.), that is, the function g(x) such that

g(x) = ∑_{n=0}^{∞} a_{n}x^{n},

or by their exponential generating function (e.g.f.) f(x), where

f(x) = ∑_{n=0}^{∞} a_{n} \frac{x^{n}}{n!} .

We shall encounter transformations that operate on integer sequences during the course of this note. An example of such a transformation that is widely used in the study of integer sequences is the so-called Binomial transform [14], which associates to the sequence with general term a_{n} the sequence with general term b_{n} where

b_{n} = ∑_{k=0}^{n} \binom{n}{k}a_{k}.  (1)

If we consider the sequence with general term a_{n} to be the column vector a = (a_{0}, a_{1}, …)′ then we obtain the binomial transform of the sequence by multiplying this (infinite) vector by the lower-triangle matrix B whose (n, k)-th element is equal to \binom{n}{k}:

B = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & … \\ 1 & 4 & 6 & 4 & 1 & 0 & … \\ 1 & 5 & 10 & 10 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

This transformation is invertible, with

a_{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}b_{k}.  (2)

We note that B corresponds to Pascal’s triangle. Its row sums are 2^{n}, while its diagonal sums are the Fibonacci numbers F (n + 1). If B^{m} denotes the m−th power of B, then the n−th term of B^{m}a where a = \{a_{n}\} is given by ∑_{k=0}^{n} m^{n−k}\binom{n}{k}a_{k}.

If A(x) is the ordinary generating function of the sequence a_{n}, then the ordinary generating function of the transformed sequence b_{n} is \frac{1}{1−x}A(\frac{x}{1−x}). Similarly, if G(x) is the exponential generating function (e.g.f.) of the sequence a_{n}, then the exponential generating function of the binomial transform of a_{n} is exp(x)G(x).

The binomial transform is an element of the exponential Riordan group, which can be defined as follows.

The exponential Riordan group [2], [3], [4], 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. The associated matrix is the matrix whose k-th column has exponential generating function g(x)f(x)^{k}/k! (the first column being indexed by 0). The matrix corresponding to the pair f, g is denoted by [g, f]. The group law is then given by

[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.

If M is the matrix [g, f], and a = {a_{n}} is an integer sequence with exponential generating function A (x), then the sequence Ma has exponential generating function g(x)A(f(x)).

We shall use the notation (g(x), f(x)) to denote an element of the (ordinary) Riordan group [5]. Riordan group techniques have been used to provide alternative proofs of many binomial identities that originally appeared in works such as [8], [9]. See for instance [12], [13].

Example 1. The Binomial matrix B is the element [e^{x}, x] of the exponential Riordan group. More generally, B^{k} is the element [e^{kx}, x] of the exponential Riordan group. It is easy to show that the inverse B^{−k} of B^{k} is given by [e^{−kx}, x]. Note that as an element of the (ordinary) Riordan group, B is given by (\frac{1}{1−x}, \frac{x}{1−x}). Similarly B^{k} is the element (\frac{1}{1−kx}, \frac{x}{1−kx}) of the Riordan group.

Example 2. The exponential generating function of the row sums of the matrix [g, f] is obtained by applying [g, f] to e^{x}, the e.g.f. of the sequence 1, 1, 1, . . .. Hence the row sums of [g, f] have e.g.f. g(x)e^{f(x)}.

We shall frequently refer to sequences by their sequence number in the On-Line Encylopedia of Integer Sequences [10], [11]. For instance, Pascal’s triangle is \underline{A007318} while the Fibonacci numbers F (n) are \underline{A000045}.

Example 3. The Permutation matrix P and its inverse. We consider the matrix

P = [\frac{1}{1 − x}, x].

The general term P (n, k) of this matrix is easily found:

P (n, k) = \frac{n!}{k!}[x^{n}]\frac{x^{k}}{1 − x}
= \frac{n!}{k!}[x^{n−k}]\frac{1}{1 − x}
= \frac{n!}{k!}[x^{n−k}] ∑_{j=0}^{∞} x^{j}

= \frac{n!}{k!}  if  n − k ≥ 0,  = 0,  otherwise,
= [k ≤ n]\frac{n!}{k!}.

Here, we have used the Iverson bracket notation [6], defined by [P] = 1 if the proposition P is true, and [P] = 0 if P is false. For instance, δ_{ij} = [i = j], while δ_{n} = [n = 0].

Clearly, the inverse of this matrix is P^{−1} = [(1 − x), x]. The general term of this matrix is given by

P^{−1}(n, k) = \frac{n!}{k!}[x^{n}](1 − x)x^{k}
= \frac{n!}{k!}[x^{n−k}](1 − x)
= \frac{n!}{k!}(δ_{n−k} − δ_{n−k−1})
= δ_{n−k} − (k + 1)δ_{n−k−1}

Thus

P = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 2 & 2 & 1 & 0 & 0 & 0 & … \\ 6 & 6 & 3 & 1 & 0 & 0 & … \\ 24 & 24 & 12 & 4 & 1 & 0 & … \\ 120 & 120 & 60 & 20 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

while

P^{−1} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ −1 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & −2 & 1 & 0 & 0 & 0 & … \\ 0 & 0 & −3 & 1 & 0 & 0 & … \\ 0 & 0 & 0 & −4 & 1 & 0 & … \\ 0 & 0 & 0 & 0 & −5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

2 The Lah transform

Introduced by Jovovic (see, for instance, \underline{A103194}), the Lah transform is the transformation on integer sequences whose matrix is given by

Lah = [1, \frac{x}{1 − x}].

Properties of the matrix obtained from the n × n principal sub-matrix of Lah, and related matrices have been studied in [7]. From the above definition, we see that the matrix Lah has general term Lah(n, k) given by

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

= \frac{n!}{k!}[x^{n−k}] ∑ j\binom{k + j − 1}{j}x^{j}
= \frac{n!}{k!}\binom{n − 1}{n − k}

Thus if b_{n} is the Lah transform of the sequence a_{n}, we have

b_{n} = ∑_{k=0}^{n} \frac{n!}{k!}\binom{n − 1}{n − k}a_{k}.

It is clear that the inverse of this matrix Lah^{−1} is given by [1, \frac{x}{1+x}] with general term Lah(n, k)(−1)^{n−k}. Thus

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

Numerically, we have

Lah = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 1 & 0 & 0 & 0 & … \\ 0 & 6 & 6 & 1 & 0 & 0 & … \\ 0 & 24 & 36 & 12 & 1 & 0 & … \\ 0 & 120 & 240 & 120 & 20 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

Operating on the sequence with e.g.f. f(x), it produces the sequence with e.g.f. f(\frac{x}{1−x}).

Example 4. The row sums of the matrix Lah, obtained by operating on the sequence 1, 1, 1 … with e.g.f. e^{x}, is the sequence 1, 1, 3, 13, 73, 501, … (\underline{A000262}) with e.g.f. e^{\frac{x}{1−x}}. We observe that this is n!L(n, −1, −1) = n!L_{n}^{(−1)}(−1) (see Appendix for notation). This sequence counts the number of partitions of {1, .., n} into any number of lists, where a list means an ordered subset.

3 The generalized Lah transform

Extending the definition in [7], we can define, for the parameter t, the generalized Lah matrix

Lah[t] = [1, \frac{x}{1 − tx}].

It is immediate that Lah[0] = [1, x] = I, and Lah[1] = Lah. The general term of the matrix Lah[t] is easily computed:

Lah[t](n, k) = \frac{n!}{k!}[x^{n}]\frac{x^{k}}{(1 − tx)^{k}}
= \frac{n!}{k!}[x^{n−k}] ∑_{j=0}^{∞} \binom{−k}{j}(−1)^{j}t^{j}x^{j}

= \frac{n!}{k!}[x^{n−k}] ∑ j\binom{k + j − 1}{j}t^{j}x^{j}
= \frac{n!}{k!}\binom{n − 1}{n − k}t^{n−k}.

We can easily establish that Lah[t]^{−1} = [1, \frac{x}{1+tx}] = Lah[−t] with general term \frac{n!}{k!} \binom{n−1}{n−k}t^{n−k}(−1)^{n−k}. We also have

Lah[u + v] = Lah[u] · Lah[v].

This follows since

Lah[u] · Lah[v] = [1, \frac{x}{1 − ux}][1, \frac{x}{1 − vx}]
= [1, \frac{\frac{x}{1−vx}}{1 − \frac{ux}{1−vx}}]
= [1, \frac{\frac{x}{1−vx}}{\frac{1−vx−ux}{1−vx}}]
= [1, \frac{x}{1 − (u + v)x}]
= Lah[u + v].

For integer m, it follows that

Lah[mt] = (Lah[t])^{m}.

4 Laguerre related transforms

In this section, we will define the Laguerre transform on integer sequences to be the transform with matrix given by

Lag = [\frac{1}{1 − x}, \frac{x}{1 − x}].

We favour this denomination through analogy with the Binomial transform, whose matrix is given by

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

Numerically, we have

Lag = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 2 & 4 & 1 & 0 & 0 & 0 & … \\ 6 & 18 & 9 & 1 & 0 & 0 & … \\ 24 & 96 & 72 & 16 & 1 & 0 & … \\ 120 & 600 & 600 & 200 & 25 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

The inverse of the Laguerre transform, as we understand it in this section, is given by

Lag^{−1} = [\frac{1}{1 + x}, \frac{x}{1 + x}].

Clearly, the general term Lag(n, k) of the matrix Lag is given by

Lag(n, k) = \frac{n!}{k!}\binom{n}{k}.

Thus if b_{n} is the Laguerre transform of the sequence a_{n}, we have

b_{n} = ∑_{k=0}^{n} \frac{n!}{k!}\binom{n}{k}a_{k}.

The e.g.f. of b_{n} is given by \frac{1}{1−x}f(\frac{x}{1−x}) where f(x) is the e.g.f. of a_{n}. The inverse matrix of Lag has general term given by (−1)^{n−k} \frac{n!}{k!} \binom{n}{k}. Thus

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

The relationship between the Lah transform with matrix Lah and the Laguerre transform with matrix Lag is now clear:

Lag = [\frac{1}{1 − x}, \frac{x}{1 − x}]
= [\frac{1}{1 − x}, x][1, \frac{x}{1 − x}]
= P · Lah

We note that this implies that

Lag(n, k) = \frac{n!}{k!}\binom{n}{k}
= ∑_{i=0}^{n}[i ≤ n]\frac{n!}{i!} \frac{i!}{k!}\binom{i − 1}{i − k}
= ∑_{i=0}^{n}[k ≤ n]\frac{n!}{k!}\binom{i − 1}{i − k}
= \frac{n!}{k!} ∑_{i=0}^{n} \binom{i − 1}{i − k}

which indeed is true since

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

Numerically, we have

P · Lah = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 2 & 2 & 1 & 0 & 0 & 0 & … \\ 6 & 6 & 3 & 1 & 0 & 0 & … \\ 24 & 24 & 12 & 4 & 1 & 0 & … \\ 120 & 120 & 60 & 20 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 1 & 0 & 0 & 0 & … \\ 0 & 6 & 6 & 1 & 0 & 0 & … \\ 0 & 24 & 36 & 12 & 1 & 0 & … \\ 0 & 120 & 240 & 120 & 20 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

= ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 2 & 4 & 1 & 0 & 0 & 0 & … \\ 6 & 18 & 9 & 1 & 0 & 0 & … \\ 24 & 96 & 72 & 16 & 1 & 0 & … \\ 120 & 600 & 600 & 200 & 25 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

= Lag

Similarly we have

Lag^{−1} = Lah^{−1} · P^{−1},

which implies that

Lag^{−1}(n, k) = (−1)^{n−k} \frac{n!}{k!}\binom{n}{k}
= ∑_{i=0}^{n}(−1)^{n−i} \frac{n!}{i!}\binom{n − 1}{n − i}(δ_{i−k} − (k + 1)δ_{i−k−1}).

It is of course possible to pass from Lag to Lah by:

Lah = P^{−1} · Lag.

Thus

Lah(n, k) = \frac{n!}{k!}\binom{n − 1}{n − k}
= ∑_{i=0}^{n}(δ_{n−i} − (i + 1)δ_{n−i−1})\frac{i!}{k!}\binom{i}{k}

We note in passing that this gives us the identity

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

P^{−1} · Lag = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ −1 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & −2 & 1 & 0 & 0 & 0 & … \\ 0 & 0 & −3 & 1 & 0 & 0 & … \\ 0 & 0 & 0 & −4 & 1 & 0 & … \\ 0 & 0 & 0 & 0 & −5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 2 & 4 & 1 & 0 & 0 & 0 & … \\ 6 & 18 & 9 & 1 & 0 & 0 & … \\ 24 & 96 & 72 & 16 & 1 & 0 & … \\ 120 & 600 & 600 & 200 & 25 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

= ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 2 & 1 & 0 & 0 & 0 & … \\ 0 & 6 & 6 & 1 & 0 & 0 & … \\ 0 & 24 & 36 & 12 & 1 & 0 & … \\ 0 & 120 & 240 & 120 & 20 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

= Lah

Thus if the Laguerre transform of a_{n} has general term b_{n}, then the general term of the Lah transform of a_{n} will be given by

b_{n} − nb_{n−1}

(for n > 0).

Example 5. The row sums of the matrix Lag, that is, the transform of the sequence 1, 1, 1, … with e.g.f. e^{x}, is the sequence 1, 2, 7, 34, 209, 1546, 13327, … with e.g.f. \frac{1}{1−x}e^{\frac{x}{1−x}}. This is \underline{A002720}. Among other things, it counts the number of matchings in the bipartite graph K(n, n). It general term is ∑_{k=0}^{n} \frac{n!}{k!} \binom{n}{k}. This is equal to L_{n}(−1) where L_{n}(x) is the n-th Laguerre polynomial.

Example 6. The row sums of the matrix Lag^{−1} yield the sequence 1, 0, −1, 4, −15, 56, −185, 204, … with e.g.f. \frac{1}{1+x}e^{\frac{x}{1+x}}. It has general term ∑_{k=0}^{n}(−1)^{n−k} \frac{n!}{k!} \binom{n}{k} which is equal to (−1)^{n}L_{n}(1).

5 The Associated Laguerre transforms

The Lah and Laguerre transforms, as defined above, are elements of a one-parameter family of transforms, whose general element is given by

Lag^{(α)} = [\frac{1}{(1 − x)^{α+1}} , \frac{x}{1 − x}].

We can calculate the general term of this matrix in the usual way:

Lag^{(α)}(n, k) = \frac{n!}{k!}[x^{n}](1 − x)^{−(α+1)}x^{k}(1 − x)^{−k}
= \frac{n!}{k!}[x^{n−k}](1 − x)^{−(α+k+1)}
= \frac{n!}{k!} ∑_{j=0}^{∞} \binom{α + k + j}{j}x^{j}

= \frac{n!}{k!}\binom{n + α}{n − k}.

We note that Lah = Lag^{(−1)} while Lag = Lag^{(0)}. We can factorize Lag^{(α)} as follows:

Lag^{(α)} = [\frac{1}{(1 − x)^{α}} , x][\frac{1}{1 − x}, \frac{x}{1 − x}]
= P^{(α)} · Lag

where P^{(α)} has general term \frac{n!}{k!} \binom{n+α−k−1}{n−k}. Clearly, P^{(1)} = P. In fact, we have P^{(α)} = P^{α}. The transform of the sequence a_{n} by the associated Laguerre transform for α is the sequence b_{n} with general term b_{n} = ∑_{k=0}^{n} \frac{n!}{k!} \binom{n+α}{n−k}a_{k}, which has e.g.f. \frac{1}{(1−x)^{α+1}} f(\frac{x}{1−x}).

We note that in the literature of Riordan arrays, the subset of matrices of the form (1, f(x)) forms a sub-group, called the associated group. We trust that this double use of the term “associated” does not cause confusion.

6 The Generalized Laguerre transform

We define, for the parameter t, the generalized Laguerre matrix Lag[t] to be

Lag[t] = [\frac{1}{1 − tx}, \frac{x}{1 − tx}].

We immediately have

Lag[t] = [\frac{1}{1 − tx}, \frac{x}{1 − tx}]
= [\frac{1}{1 − tx}, x][1, \frac{x}{1 − tx}]
= P[t] · Lah[t].

where the generalized permutation matrix P[t] has general term [k ≤ n]\frac{n!}{k!}t^{n−k}. It is clear that

Lag[t]^{−1} = Lag[−t] = [\frac{1}{1 + tx}, \frac{x}{1 + tx}].

It is possible to generalize the associated Laguerre transform matrices in similar fashion.

7 Transforming the expansion of \frac{x}{1−μx−νx^{2}}

The e.g.f. of the expansion of \frac{x}{1−μx−νx^{2}} takes the form

f(x) = A(μ, ν)e^{r_{1}x} + B(μ, ν)e^{r_{2}x}

which follows immediately from the Binet form of the general term. Thus the transform of this sequence by Lag^{(α)} will have e.g.f.

\frac{A(μ, ν)}{(1 − x)^{α+1}} e^{\frac{r_{1}x}{1−x}} + \frac{B(μ, ν)}{(1 − x)^{α+1}} e^{\frac{r_{2}x}{1−x}} .

In the case of the Lah transform (α = −1), we get the simple form

Ae^{\frac{r_{1}x}{1−x}} + Be^{\frac{r_{2}x}{1−x}}

while in the Laguerre case (α = 0) we get

A\frac{e^{\frac{r_{1}x}{1−x}}}{1 − x} + B \frac{e^{\frac{r_{2}x}{1−x}}}{1 − x}

But \frac{e^{\frac{rx}{1−x}}}{1−x} is the e.g.f. of the sequence n!L_{n}(−r). Thus is this case, the transformed sequence has general term An!L_{n}(−r_{1}) + Bn!L_{n}(−r_{2}).

Example 7. The Laguerre transform of the Fibonacci numbers

F (n) = \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^{n} − \frac{1}{\sqrt{5}}(\frac{1 − \sqrt{5}}{2})^{n}

is given by

\frac{1}{\sqrt{5}}n!L_{n}(−\frac{1 + \sqrt{5}}{2}) − \frac{1}{\sqrt{5}}n!L_{n}(−\frac{1 − \sqrt{5}}{2}).

This is \underline{A105277}. It begins 0, 1, 5, 29, 203, 1680, 16058, . . ..

Example 8. The Laguerre transform of the Jacobsthal numbers [1], [15] (expansions of \frac{x}{1−x−2x^{2}} )

J(n) = \frac{2^{n}}{3} − \frac{(−1)^{n}}{3}

is given by

\frac{1}{3}n!L_{n}(−2) − \frac{1}{3}n!L_{n}(1).

This is \underline{A129695}. It begins 0, 1, 5, 30, 221, 1936, 19587, . . .. We can use this result to express the Lah transform of the Jacobsthal numbers, since this is equal to b_{n} − nb_{n−1} where b_{n} is the Laguerre transform of J(n). We find

\frac{n!}{3}(L_{n}(−2) − L_{n−1}(−2) − (L_{n}(1) − L_{n−1}(1))).

Example 9. We calculate the Lag^{(1)} transform of the Jacobsthal numbers J(n). Since Lag^{(1)} = P · Lag, we apply P to the Laguerre transform of J(n). This gives us

∑_{k=0}^{n} \frac{n!}{k!}(k!L_{k}(−2) − k!L_{k}(1))/3 = \frac{n!}{3} ∑_{k=0}^{n}(L_{k}(−2) − L_{k}(1)).

This sequence has e.g.f. \frac{1}{(1−x)^{2}} ^{\frac{e^{\frac{2x}{(1−x)}} −e^{\frac{−x}{1−x}}}{3}} .

8 The Lah and Laguerre transforms and Stirling numbers

In this section, we follow the notation of [6]. Thus the Stirling numbers of the first kind, denoted by \left[{n \atop k}\right], are the elements of the matrix

s = [1, ln(\frac{1}{1 − x})].

\left[{n \atop k}\right] counts the number of ways to arrange n objects into k cycles.

The Stirling numbers of the second kind, denoted by \left\{{n \atop k}\right\}, count the number of ways to partition a set of n things into k nonempty subsets. \left\{{n \atop k}\right\} are the elements of the matrix

S = [1, e^{x} − 1].

We have

\left\{{n \atop k}\right\} = ∑_{i=0}^{k} \binom{k}{i}\frac{i^{n}}{k!}.

We note that the matrix [1, e^{x} − 1] of Stirling numbers of the second kind is the inverse of the matrix with elements (−1)^{n−k}\left[{n \atop k}\right], which is the matrix [1, ln(1 + x)].

Related matrices include

[\frac{1}{1 − x}, ln(\frac{1}{1 − x})]

whose elements are given by \left[{n+1 \atop k+1}\right] and its signed version,

[\frac{1}{1 + x}, ln(\frac{1}{1 + x})]

whose elements are given by (−1)^{n−k}\left[{n+1 \atop k+1}\right], along with their inverses, given respectively by [e^{−x}, 1−e^{−x}], with general element (−1)^{n−k}\left\{{n+1 \atop k+1}\right\}, and [e^{x}, e^{x}−1] with general element \left\{{n+1 \atop k+1}\right\}.

We can generalize a result linking the Lah matrix to the Stirling numbers [7] to the infinite matrix case as follows:

Lah = s · S.

This is because we have

s · S = [1, ln(\frac{1}{1 − x})][1, e^{x} − 1]
= [1, e^{ln( \frac{1}{1−x})} − 1]
= [1, \frac{1}{1 − x} − 1]
= [1, \frac{x}{1 − x}] = Lah.

Thus we have

S = s^{−1} · Lah, s = Lah · S^{−1}.

We now observe that

[\frac{1}{1 − x}, \frac{x}{1 − x}][1, ln(1 + x)] = [\frac{1}{1 − x}, ln(1 + \frac{x}{1 − x})]
= [\frac{1}{1 − x}, ln(\frac{1}{1 − x})]

or

Lag · ((−1)^{n−k}\left[{n \atop k}\right]) = (\left[{n + 1 \atop k + 1}\right]) .

We deduce the identity

\left[{n + 1 \atop k + 1}\right] = ∑_{j=0}^{n} \frac{n!}{j!}\binom{n}{j}(−1)^{j−k}\left[{j \atop k}\right].

Taking the inverse of the matrix identity above, we obtain

(\left[{n + 1 \atop k + 1}\right])^{−1} = ((−1)^{n−k}\left[{n \atop k}\right])^{−1} · Lag^{−1}

which can be established alternatively by noting that

[1, e^{x} − 1][\frac{1}{1 + x}, \frac{x}{1 + x}] = [1.\frac{1}{1 + e^{x} − 1}, \frac{e^{x} − 1}{1 + e^{x} − 1}]
= [e^{−x}, 1 − e^{−x}].

This establishes the identity

(−1)^{n−k}\left\{{n + 1 \atop k + 1}\right\} = ∑_{j=0}^{n}(−1)^{j−k}\binom{j}{k}\frac{j!}{k!}\left\{{n \atop j}\right\}.

Finally, from the matrix identity

Lag · ((−1)^{n−k}\left[{n \atop k}\right]) = (\left[{n + 1 \atop k + 1}\right]) .

we deduce that

Lag = (\left[{n + 1 \atop k + 1}\right]) · ((−1)^{n−k}\left[{n \atop k}\right])^{−1}
= (\left[{n + 1 \atop k + 1}\right]) · (\left\{{n \atop k}\right\}) .

Thus

Lag(n, k) = ∑_{j=0}^{n} \left[{n + 1 \atop j + 1}\right]\left\{{j \atop k}\right\}.

This is equivalent to the factorization

Lag = [\frac{1}{1 − x}, \frac{x}{1 − x}] = [\frac{1}{1 − x}, ln(\frac{1}{1 − x})][1, e^{x} − 1].

This implies (see Appendix A) that

L_{n}(x) = \frac{1}{n!} ∑_{k=0}^{n} ∑_{j=0}^{n} \left[{n + 1 \atop j + 1}\right]\left\{{j \atop k}\right\}(−x)^{k}.

It is natural in this context to define as associated Stirling numbers of the first kind the elements \left[{n \atop k}\right]_{α} of the matrices

[\frac{1}{(1 − x)^{α}} , ln(\frac{1}{1 − x})].

For instance, \left[{n \atop k}\right]_{0} = \left[{n \atop k}\right] and \left[{n \atop k}\right]_{1} = \left[{n+1 \atop k+1}\right]. We note that signed versions of these numbers have been documented by Lang (see for instance \underline{A049444} and \underline{A049458}). To calculate \left[{n \atop k}\right]_{2}, we proceed as follows:

(\left[{n \atop k}\right]_{2}) = [\frac{1}{(1 − x)^{2}} , ln(\frac{1}{1 − x})]
= P · [\frac{1}{1 − x}, ln(\frac{1}{1 − x})]
= ([k ≤ n]\frac{n!}{k!}) (\left[{n + 1 \atop k + 1}\right]) .

Thus

\left[{n \atop k}\right]_{2} = ∑_{j=0}^{n} \frac{n!}{j!}\left[{j + 1 \atop k + 1}\right] = ∑_{j=0}^{n} \frac{n!}{j!}\left[{n \atop k}\right]_{1}.

More generally, since [\frac{1}{(1−x)^{α}} , ln(\frac{1}{1−x})] = P[\frac{1}{(1−x)^{α−1}} , ln(\frac{1}{1−x})], we have

\left[{n \atop k}\right]_{α} = ∑_{j=0}^{n} \frac{n!}{j!}\left[{n \atop k}\right]_{α−1}.

Lag^{(α)}(n, k) = ∑_{j=0}^{n} \left[{n \atop j}\right]_{α+1}\left\{{n \atop k}\right\}.

For example,

Lag^{(1)} = [\frac{1}{(1 − x)^{2}} , ln(\frac{1}{1 − x})][1, e^{x} − 1]
= (∑_{j=0}^{n} \left[{n \atop j}\right]_{2}\left\{{j \atop k}\right\})

= (∑_{j=0}^{n} ∑_{i=0}^{n} \frac{n!}{i!}\left[{n + 1 \atop j + 1}\right]\left\{{j \atop k}\right\}) .

In general, we have

Lag^{(α)} = [\frac{1}{(1 − x)^{α+1}} , \frac{x}{1 − x}] = [\frac{1}{(1 − x)^{α+1}} , ln(\frac{1}{1 − x})][1, e^{x} − 1].

This implies that

Lag^{(α)}(n, k) = ∑_{j=0}^{n} \left[{n \atop j}\right]_{α+1}\left\{{n \atop k}\right\}.

9 The generalized Lah, Laguerre and Stirling matrices

Given a parameter t define the generalized Stirling numbers of the first kind to be the elements of the matrix

s[t] = [1, \frac{1}{t} ln(\frac{1}{1 − tx})].

Similarly, we define the generalized Stirling numbers of the second kind to be the elements of the matrix

S[t] = [1, \frac{e^{tx} − 1}{t}].

Then

S[t]^{−1} = s[−t].

For instance,

s[−t] · S[t] = [1, −\frac{1}{t} ln(\frac{1}{1 + tx})][1, \frac{e^{tx} − 1}{t}]
= [1, −\frac{1}{t} ln(\frac{1}{1 + t\frac{e^{tx}−1}{t}})]
= [1, −\frac{1}{t} ln(\frac{1}{e^{tx}})]
= [1, \frac{1}{t} ln(e^{tx})]
= [1, x] = I.

The general term of s[t] is given by t^{n−k}\left[{n \atop j}\right] and that of S[t] is given by t^{n−k}\left\{{n \atop j}\right\}. An easy calculation establishes that

Lah[t] = s[t]S[t].

From this we immediately deduce that

Lag[t] = P[t]s[t]S[t].

Similarly results for the generalized associated Laguerre transform matrices can be derived.

10 Appendix A - the Laguerre and associated Laguerre functions

The associated Laguerre polynomials [16] are defined by

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

Their exponential generating function is

\frac{e^{\frac{xz}{1−z}}}{(1 − z)^{α+1}}

The Laguerre polynomials are given by L_{n}(x) = L_{n}^{(0)}(x). The associated Laguerre polynomials are orthogonal on the interval [0, ∞) for the weight e^{−x}x^{α}.

Using the notation developed above, we have

L_{n}^{(α)}(x) = \frac{1}{n!} ∑_{k=0}^{n} Lag^{(α)}(n, k)(−x)^{k}

= \frac{1}{n!} ∑_{k=0}^{n} ∑_{i=0}^{n} \left[{n \atop j}\right]_{α+1}\left\{{j \atop k}\right\}(−x)^{k}.

In particular,

L_{n}(x) = \frac{1}{n!} ∑_{k=0}^{n} ∑_{i=0}^{n} \left[{n + 1 \atop j + 1}\right]\left\{{j \atop k}\right\}(−x)^{k}.

11 Acknowledgements

The author would like to thank an anonymous reviewer for their careful reading of this manuscript and their constructive remarks.

12 Appendix B - Lah and Laguerre transforms in the OEIS

Table 1. Table of Lah transforms

a_{n}  Lah transform b_{n}
A000290  A103194
A104600  A121020
A000262  A025168
A000079  A052897
A000110  A084357
A000085  A049376
A000670  A084358

Table 2. Table of Laguerre transforms

a_{n}  Laguerre transform b_{n}
A000007  A000142
A000012  A002720
A000045  A105277
A000079  A087912
A001045  A129695

References

[1] P. Barry, Triangle Geometry and Jacobsthal Numbers, Irish Math. Soc. Bulletin 51 (2003), 45–57.

[2] P. Barry, On a family of generalized Pascal triangles defined by exponential Riordan arrays, J. Integer Sequences 10, Article 07.3.5.

[3] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices and Riordan arrays, arXiv:math.CO/0702638v1, 2007.

[4] E. Deutsch,  L. Shapiro,  Exponential Riordan Arrays,  Lec-
ture Notes,  Nankai University,  2004,  available electronically at

http://www.combinatorics.net/ppt2004/Louis%20W.%20 Shapiro/shapiro.pdf,

2007.

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

[6] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[7] Tan Mingshu, Wang Tianming, Lah Matrix and its algebraic properties, Ars Combinatoria 70 (2004), 97–108.

[8] J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002.

[9] J. Riordan, Combinatorial Identities, John Wiley & Sons, 1968.

[10] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Available at

   http://www.research.att.com/~njas/sequences/.

[11] N. J. A. Sloane, The on-line encyclopedia of integer sequences, Notices of the AMS, 50 (2003), 912–915.

[12] R. Sprugnoli, Riordan Array Proofs of Identities in Gould’s Book. Published electronically at http://www.dsi.unifi.it/˜ resp/GouldBK.pdf, 2007.

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

[14] E. W. Weisstein, http://mathworld.wolfram.com/BinomialTransform.html/, 2007.

[15] E. W. Weisstein, http://mathworld.wolfram.com/JacobsthalNumber.html/, 2007.

[16] E. W. Weisstein, http://mathworld.wolfram.com/LaguerrePolynomial.html/, 2007.

2000 Mathematics Subject Classification: Primary 11B83; Secondary 05A19, 15A30, 33C45. Keywords: Lah transform, Laguerre polynomials, Stirling numbers, exponential Riordan array.

(Concerned with sequences \underline{A000079}, \underline{A000085}, \underline{A000110}, \underline{A000142}, \underline{A000262}, \underline{A000290}, \underline{A000670}, \underline{A002720}, \underline{A007318}, \underline{A025168}, \underline{A049376}, \underline{A052897}, \underline{A084357}, \underline{A084358}, \underline{A087912}, \underline{A103194}, \underline{A104600}, \underline{A105277}, \underline{A121020}, and \underline{A129695}.)

Received April 18 2007; revised version received May 1 2007. Published in Journal of Integer Sequences, May 2 2007.

Return to Journal of Integer Sequences home page.