Exponential Riordan Arrays and Permutation Enumeration

Paul Barry School of Science Waterford Institute of Technology Ireland

                       pbarry@wit.ie

Abstract We show that the generating function of the symmetric group with respect to five

particular statistics gives rise to an exponential Riordan array, whose inverse is the coefficient array of the associated orthogonal polynomials. This also provides us with an LDU factorization of the Hankel matrix of the associated moments.

1 Introduction

In this note, we shall re-interpret some of the results of Zeng [30] in terms of exponential Riordan arrays. For this, we let 𝔖_{n} denote the set of permutations of {1, 2, …, n}. Given a permutation σ ∈ 𝔖_{n}, each value x = σ(i), 1 ≤ i ≤ n, can be classified according to one of the five following cases:

1. a peak (“pic de cycle”), if σ^{−1}(x) < x > σ(x);

2. a valley (“creux de cycle”), if σ^{−1} > x < σ(x);

3. a double rise (“double montée de cycle”), if σ^{−1}(x) < x < σ(x);

4. a double descent (“double descente de cycle”), if σ^{−1}(x) > x > σ(x);

5. a fixed point (“point fixe”), if σ(i) = i.

Using the notation of Zeng [30], we denote the number of peaks, valleys, double rises, double descents, and fixed points of σ respectively by pic σ, cc σ, dm σ, dd σ, and fix σ. We shall also denote by cyc σ the number of cycles of σ. We set

μ_{n} = ∑_{σ∈S_{n}} u_{1}^{cc σ}u_{2}^{pic σ}u_{3}^{dm σ}u_{4}^{dd σ}α^{fix σ}β^{cyc σ}.

We then have the following theorem.

Theorem 1. We let α_{1} and α_{2} be such that α_{1}α_{2} = u_{1}u_{2} and α_{1} + α_{2} = u_{3} + u_{4}. Then the exponential Riordan array

L = [e^{αβx} (\frac{α_{1} − α_{2}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} )^{β} , \frac{e^{α_{1}x} − e^{α_{2}x}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} ]

is the inverse of the coefficient array for the family of orthogonal polynomials for which μ_{n} are the moments. The elements of the first column of L are given by μ_{n}. The Hankel matrix H = (μ_{i+j})_{i,j≥0} has LDU factorization

H = LDL^{t}.

While partly expository in nature, this note assumes a certain familiarity with integer sequences, generating functions, orthogonal polynomials [5, 11, 26], Riordan arrays [21, 25], production matrices [10, 18], and the integer Hankel transform [1, 7, 16]. Many interesting examples of sequences and Riordan arrays can be found in Neil Sloane’s On-Line Encyclopedia of Integer Sequences (OEIS), [23, 24]. Sequences are frequently referred to by their OEIS number. For instance, the binomial matrix B (“Pascal’s triangle”) is \underline{A007318}.

The plan of the paper is as follows:

1. This Introduction

2. Integer sequences, exponential Riordan arrays and orthogonal polynomials

3. Proof of the theorem

4. A matrix product

2 Integer sequences, exponential Riordan arrays and orthogonal polynomials

For an integer sequence a_{n}, that is, an element of ℤ^{ℕ}, the power series f_{o}(x) = ∑_{k=0}^{∞} a_{k}x^{k} is called the ordinary generating function or g.f. of the sequence, while f_{e}(x) = ∑_{k=0}^{∞} \frac{a_{k}}{k!} x^{k} is called the exponential generating function or e.g.f. of the sequence. a_{n} is thus the coefficient of x^{n} in f_{o}(x). We denote this by a_{n} = [x^{n}]f_{o}(x). Similarly, a_{n} = n![x^{n}]f_{e}(x). For instance, F_{n} = [x^{n}]\frac{x}{1−x−x^{2}} is the n-th Fibonacci number \underline{A000045}, while n! = n![x^{n}]\frac{1}{1−x}, which says that \frac{1}{1−x} is the e.g.f. of n! \underline{A000142}. 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) = f^{[−1]}(x) such that f(f̄(x)) = x. We sometimes write f̄ = Revf.

The exponential Riordan group [2, 10, 8], is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions g(x) = g_{0} + g_{1}x + g_{2}x^{2} + ⋯ and f(x) = f_{1}x + f_{2}x^{2} + ⋯ where g_{0} ≠ 0 and f_{1} ≠ 0. The associated matrix is the matrix whose i-th column has exponential generating function g(x)f(x)^{i}/i! (the first column being indexed by 0). The matrix corresponding to the pair f, g is denoted by [g, f]. It is monic if g_{0} = 1. The group law is 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. We use the notation eR to denote this group. If M is the matrix [g, f], and u = (u_{n})_{n≥0} is an integer sequence with exponential generating function U (x), then the sequence Mu has exponential generating function g(x)U(f(x)). Thus the row sums of the array [g, f] are given by g(x)e^{f(x)} since the sequence 1, 1, 1, … has exponential generating function e^{x}.

Example 2. The binomial matrix is the matrix with general term \binom{n}{k}. It is realized by Pascal’s triangle. As an exponential Riordan array, it is given by [e^{x}, x]. We further have

([e^{x}, x])^{m} = [e^{mx}, x].

As an example of the calculation of an inverse, we have the following proposition.

Proposition 3.

L^{−1} = [(\frac{1 + α_{2}x}{1 + α_{1}x})^{\frac{αβ}{α_{1}−α_{2}}} (\frac{(1 + α_{2}x)^{\frac{α_{1}}{α_{1}−α_{2}}}}{(1 + α_{1}x)^{\frac{α_{2}}{α_{1}−α_{2}}}} )^{−β} , \frac{1}{α_{2} − α_{1}} ln (\frac{1 + α_{2}x}{1 + α_{1}x})] .

Proof. This follows since with

f(x) = \frac{e^{α_{1}x} − e^{α_{2}x}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}}

we have

f̄(x) = \frac{1}{α_{2} − α_{1}} ln (\frac{1 + α_{2}x}{1 + α_{1}x}) .

We note that we can then write L^{−1} as

L^{−1} = [\frac{(1 + α_{2}x)^{\frac{β(α−α_{1})}{α_{1}−α_{2}}}}{(1 + α_{1}x)^{\frac{β(α−α_{2})}{α_{1}−α_{2}}}} , \frac{1}{α_{2} − α_{1}} ln (\frac{1 + α_{2}x}{1 + α_{1}x})] .

An important concept for the sequel is that of production matrix. The concept of a production matrix [9, 10] is a general one, but for this work we find it convenient to review it in the context of Riordan arrays. Thus let P be an infinite matrix (most often it will have integer entries). Letting r_{0} be the row vector

r_{0} = (1, 0, 0, 0, …),

we define r_{i} = r_{i−1}P, i ≥ 1. Stacking these rows leads to another infinite matrix which we denote by A_{P}. Then P is said to be the production matrix for A_{P}. If we let

u^{T} = (1, 0, 0, 0, …, 0, …)

then we have

A_{P} = ( u^{T} ; u^{T} P ; u^{T} P^{2} ; ⋮ )

and

DA_{P} = A_{P} P

where D = (δ_{i+1,j})_{i,j≥0} (where δ is the usual Kronecker symbol). In [18, 22] P is called the Stieltjes matrix associated to A_{P}. In [10], we find the following result concerning matrices that are production matrices for exponential Riordan arrays.

Proposition 4. Let A = (a_{n,k})_{n,k≥0} = [g(x), f(x)] be an exponential Riordan array and let

c(y) = c_{0} + c_{1}y + c_{2}y^{2} + ⋯,  r(y) = r_{0} + r_{1}y + r_{2}y^{2} + ⋯  (1)

be two formal power series such that

r(f(x)) = f′(x)  (2)
c(f(x)) = \frac{g′(x)}{g(x)}.  (3)

Then

(i)  a_{n+1,0} = ∑_{i} i!c_{i}a_{n,i}  (4)
(ii)  a_{n+1,k} = r_{0}a_{n,k−1} + \frac{1}{k!} ∑_{i≥k} i!(c_{i−k} + kr_{i−k+1})a_{n,i}  (5)

or, defining c_{−1} = 0,

a_{n+1,k} = \frac{1}{k!} ∑_{i≥k−1} i!(c_{i−k} + kr_{i−k+1})a_{n,i}.  (6)

Conversely, starting from the sequences defined by (1), the infinite array (a_{n,k})_{n,k≥0} defined by (6) is an exponential Riordan array.

A consequence of this proposition is that P = (p_{i,j})_{i,j≥0} where

p_{i,j} = \frac{i!}{j!}(c_{i−j} + jr_{r−j+1}) (c_{−1} = 0).

Furthermore, the bivariate exponential generating function

ϕ_{P} (t, z) = ∑_{n,k} p_{n,k}t^{k} \frac{z^{n}}{n!}

of the matrix P is given by

ϕ_{P} (t, z) = e^{tz}(c(z) + tr(z)).

Note in particular that we have

r(x) = f′(f̄(x))

and

c(x) = \frac{g′(f̄(x))}{g(f̄(x))}.

Example 5. We consider the exponential Riordan array L = [\frac{1}{1−x}, x], \underline{A094587}. This array has elements

L = ( \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} )

and general term [k ≤ n]\frac{n!}{k!} with inverse

L^{−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} )

which is the array [1 − x, x]. In particular, we note that the row sums of the inverse, which begin 1, 0, −1, −2, −3, … (that is, 1 − n), have e.g.f. (1 − x) exp(x). This sequence is thus the binomial transform of the sequence with e.g.f. (1 − x) (which is the sequence starting 1, −1, 0, 0, 0, …). In order to calculate the production matrix P of L = [\frac{1}{1−x}, x] we note that f(x) = x, and hence we have f′(x) = 1 so f′(f̄(x)) = 1. Also g(x) = \frac{1}{1−x} leads to g′(x) = \frac{1}{(1−x)^{2}} , and so, since f̄(x) = x, we get

\frac{g′(f̄(x))}{g(f̄(x))} = \frac{1}{1 − x}.

Thus the generating function for P is

e^{tz} (\frac{1}{1 − z} + t) .

Thus P is the matrix [\frac{1}{1−x}, x] with its first row removed.

Example 6. We consider the exponential Riordan array L = [1, \frac{x}{1−x}]. The general term of this matrix may be calculated as follows:

T_{n,k} = \frac{n!}{k!}[x^{n}]\frac{x^{k}}{(1 − x)^{k}}
= \frac{n!}{k!}[x^{n−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=0}^{∞} \binom{k + j − 1}{j}x^{j}

= \frac{n!}{k!}\binom{k + n − k − 1}{n − k}
= \frac{n!}{k!}\binom{n − 1}{n − k},

with

L = ( \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} ) .

Thus its row sums, which have e.g.f. exp (\frac{x}{1−x}), have general term ∑_{k=0}^{n} \frac{n!}{k!} \binom{n−1}{n−k}. This is \underline{A000262}, the ‘number of “sets of lists”: the number of partitions of \{1, .., n\} into any number of lists, where a list means an ordered subset’. Its general term is equal to (n−1)!L_{n−1}(1, −1). The inverse of [1, \frac{x}{1−x}] is the exponential Riordan array L^{−1} = [1, \frac{x}{1+x}], \underline{A111596}. The row sums of this sequence have e.g.f. exp (\frac{x}{1+x}), and start 1, 1, −1, 1, 1, −19, 151, . . .. This is \underline{A111884}. To calculate the production matrix of L = [1, \frac{x}{1−x}] we note that g′(x) = 0, while f̄(x) = \frac{x}{1+x} with f′(x) = \frac{1}{(1+x)^{2}} . Thus

f′(f̄(x)) = (1 + x)^{2},

and so the generating function of the production matrix is given by

e^{tz}t(1 + z)^{2}.

Thus the production matrix of the inverse begins

( \begin{matrix}0 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 2 & 4 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 6 & 6 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 12 & 8 & 1 & ⋯ \\ 0 & 0 & 0 & 0 & 20 & 10 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Example 7. The exponential Riordan array A = [\frac{1}{1−x}, \frac{x}{1−x}], or

A = ( \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} )

has general term

T_{n,k} = \frac{n!}{k!}\binom{n}{k}.

Its inverse is A^{−1} = [\frac{1}{1+x}, \frac{x}{1+x}] with general term (−1)^{n−k} \frac{n!}{k!} \binom{n}{k}. This is \underline{A021009}, the triangle of coefficients of the Laguerre polynomials L_{n}(x). The production matrix of A is given by

( \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 3 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 4 & 5 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 9 & 7 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 16 & 9 & 1 & ⋯ \\ 0 & 0 & 0 & 0 & 25 & 11 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Example 8. The exponential Riordan array L = [e^{x}, ln (\frac{1}{1−x})], or

L = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 3 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 8 & 6 & 1 & 0 & 0 & ⋯ \\ 1 & 24 & 29 & 10 & 1 & 0 & ⋯ \\ 1 & 89 & 145 & 75 & 15 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

is the coefficient array for the polynomials

2F_{0}(−n, x; −1)

which are an unsigned version of the Charlier polynomials (of order 0) [11, 20, 26]. This is \underline{A094816}. We have

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

or the product of the binomial array B and the array of (unsigned) Stirling numbers of the first kind. The production matrix of the inverse of this matrix is given by

( \begin{matrix}−1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & −2 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 2 & −3 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 3 & −4 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 4 & −5 & 1 & ⋯ \\ 0 & 0 & 0 & 0 & 5 & −6 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

which indicates the orthogonal nature of these polynomials. We can prove this form as follows. We have

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

Hence g(x) = e^{−(1−e^{−x})} and f(x) = 1 − e^{−x}. We are thus led to the equations

r(1 − e^{−x}) = e^{−x},
c(1 − e^{−x}) = −e^{−x},

with solutions r(x) = 1 − x, c(x) = x − 1. Thus the bi-variate generating function for the production matrix of the inverse array is

e^{tz}(z − 1 + t(1 − z)),

which is what is required.

According to Proposition 4, for a Riordan array to have a tri-diagonal production array P, it is necessary and sufficient that P be of the form

( \begin{matrix}c_{0} & r_{0} & 0 & 0 & 0 & 0 & ⋯ \\ c_{1} & c_{0} + r_{1} & r_{0} & 0 & 0 & 0 & ⋯ \\ 0 & 2(c_{1} + r_{2}) & c_{0} + 2r_{1} & r_{0} & 0 & 0 & ⋯ \\ 0 & 0 & 3(c_{1} + 2r_{2}) & r_{0} & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 4(c_{1} + 3r_{2}) & c_{0} + 4r_{1} & r_{0} & ⋯ \\ 0 & 0 & 0 & 0 & 5(c_{1} + 4r_{2}) & c_{0} + 5r_{1} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We recognize in this the form of Meixner’s solution [19, 12] to the question of which families of Sheffer polynomials [15] are orthogonal. Thus P corresponds to the family of orthogonal polynomials (S_{n}(x))_{n≥0} that satisfy

S_{n+1}(x) = (x − (c_{0} + nr_{1}))S_{n}(x) − n(c_{1} + nr_{2})S_{n−1}(x).

Of importance to this study are the following results (the first is the well-known “Favard’s Theorem”), which we essentially reproduce from [14].

Theorem 9. [14] (Cf. [27, Théorème 9, p. I-4] or [28, Theorem 50.1]). Let (p_{n}(x))_{n≥0} be a sequence of monic polynomials, the polynomial p_{n}(x) having degree n = 0, 1, . . .. Then the sequence (p_{n}(x)) is (formally) orthogonal if and only if there exist sequences (α_{n})_{n≥0} and (β_{n})_{n≥1} with β_{n} ≠ 0 for all n ≥ 1, such that the three-term recurrence

p_{n+1} = (x − α_{n})p_{n}(x) − β_{n}(x), for n ≥ 1,

holds, with initial conditions p_{0}(x) = 1 and p_{1}(x) = x − α_{0}.

Theorem 10. [14] (Cf. [27, Prop. 1, (7), p. V-5] or [28, Theorem 51.1]). Let (p_{n}(x))_{n≥0} be a sequence of monic polynomials, which is orthogonal with respect to some functional L. Let

p_{n+1} = (x − α_{n})p_{n}(x) − β_{n}(x), for n ≥ 1,

be the corresponding three-term recurrence which is guaranteed by Favard’s theorem. Then the generating function

g(x) = ∑_{k=0}^{∞} μ_{k}x^{k}

for the moments μ_{k} = L(x^{k}) satisfies

g(x) = \frac{μ_{0}}{1 − α_{0}x − \frac{β_{1}x^{2}}{1 − α_{1}x − \frac{β_{2}x^{2}}{1 − α_{2}x − \frac{β_{3}x^{2}}{1 − α_{3}x − ⋯}}}}.

The Hankel transform of μ_{n}, which is the sequence with general term h_{n} = |μ_{i+j}|_{0≤i,j≤n}, is then given by

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

3 Proof of Theorem 1

Proof. We first note that since

g(x) = e^{αβx} (\frac{α_{1} − α_{2}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} )^{β} ,

by [30, Theorem 1], the first column of the Riordan array is indeed {μ_{n}}_{n≥0}. We now calculate the production matrix P_{L} of L. We have

r(x) = f′(f̄(x)) = (1 + α_{2}x)(1 + α_{1}x)

and

c(x) = \frac{g′(f̄(x))}{g(f̄(x))} = β(α + α_{1}α_{2}x).

Thus the bivariate generating function for the production matrix P_{L} of L is given by

e^{tz}(β(α + α_{1}α_{2}x) + t(1 + α_{2}x)(1 + α_{1}x)).

Now this is equal to

e^{tz}(αβ + βu_{1}u_{2}x + t(1 + (u_{3} + u_{4})x + u_{1}u_{2}x^{2})).

But this implies that P_{L} is precisely the Jacobi tri-diagonal matrix corresponding to the continued J-fraction

\frac{1}{1 − αβx − \frac{βu_{1}u_{2}x^{2}}{1 − (αβ + u_{3} + u_{4})x − \frac{2(β + 1)u_{1}u_{2}x^{2}}{1 − (αβ + 2(u_{3} + u_{4}))x − \frac{3(β + 2)u_{1}u_{2}x^{2}}{1 − ⋯}}}}

which by [30] is equal to the generating function

∑_{k=0}^{∞} μ_{k}x^{k}.

The matrix P_{L} begins:

( \begin{matrix}αβ & 1 & 0 & 0 & 0 & 0 & ⋯ \\ βu_{1}u_{2} & αβ + u_{3} + u_{4} & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 2(β + 1)u_{1}u_{2} & αβ + 2(u_{3} + u_{4}) & 0 & 0 & 0 & ⋯ \\ 0 & 0 & 3(β + 2)u_{1}u_{2} & αβ + 3(u_{3} + u_{4}) & 0 & 0 & ⋯ \\ 0 & 0 & 0 & 4(β + 3)u_{1}u_{2} & αβ + 4(u_{3} + u_{4}) & 0 & ⋯ \\ 0 & 0 & 0 & 0 & 5(β + 4)u_{1}u_{2} & αβ + 5(u_{3} + u_{4}) & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

This implies that L^{−1} is indeed the coefficient array of the set of orthogonal polynomials which correspond to the tri-diagonal array P_{L}. The results of [17, 18] now imply that if H = (μ_{i+j})_{i,j≥0} then

H = LDL^{t}.

As pointed out by an anonymous referee, this result could also have been arrived at using the theory of orthogonal Sheffer polynomials, as the μ_{n} are seen to be the moment sequence of the orthogonal polynomials defined by

P_{n+1}(x) = (x − b_{n})P_{n}(x) − λ_{n}P_{n−1}(x),

with P_{−1}(x) = 0 and P_{1}(x) = 1, where b_{n} = αβ + n(u_{3} + u_{4}) and λ_{n} = n(β + n)u_{1}u_{2}. Thus (P_{n}(x))_{n≥0} is a sequence of orthogonal Sheffer polynomials [12]. Note that the interrelationship between Riordan arrays and Sheffer polynomials is comprehensively studied in [15].

The elements of the diagonal matrix D are the successive products of the elements of the sub-diagonal of P_{L}:

βu_{1}u_{2}, 2β(β + 1)u_{1}^{2}u_{2}^{2}, 6β(β + 1)(β + 2)u_{1}^{3}u_{2}^{3}, …

Corollary 11. The Hankel transform of μ_{n} is given by

h_{n} = (u_{1}u_{2})^{\binom{n+1}{2}} ∏_{k=0}^{n} k!(β + k)^{n−k}.

We notice in particular that this is independent of α, u_{3} and u_{4}. We have the following factorization.

L = [e^{αβx} (\frac{α_{1} − α_{2}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} )^{β} , \frac{e^{α_{1}x} − e^{α_{2}x}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} ]

= [e^{αβx}, x] [(\frac{α_{1} − α_{2}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} )^{β} , \frac{e^{α_{1}x} − e^{α_{2}x}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} ]
= [e^{x}, x]^{αβ}L_{0},

where the matrix L_{0} has production matrix generated by

e^{tz}(βu_{1}u_{2}x + t(1 + (u_{3} + u_{4})x + u_{1}u_{2}x^{2})).

This matrix begins

( \begin{matrix}0 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ βu_{1}u_{2} & u_{3} + u_{4} & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 2(β + 1)u_{1}u_{2} & 2(u_{3} + u_{4}) & 0 & 0 & 0 & ⋯ \\ 0 & 0 & 3(β + 2)u_{1}u_{2} & 3(u_{3} + u_{4}) & 0 & 0 & ⋯ \\ 0 & 0 & 0 & 4(β + 3)u_{1}u_{2} & 4(u_{3} + u_{4}) & 0 & ⋯ \\ 0 & 0 & 0 & 0 & 5(β + 4)u_{1}u_{2} & 5(u_{3} + u_{4}) & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Thus L_{0}^{−1} is the coefficient array of the orthogonal polynomials whose moments have generating function given by

\frac{1}{1 − \frac{βu_{1}u_{2}x^{2}}{1 − (u_{3} + u_{4})x − \frac{2(β + 1)u_{1}u_{2}x^{2}}{1 − ⋯}}}.

In fact, we have

L_{0}^{−1} = [(\frac{(1 + α_{2}x)^{\frac{α_{1}}{α_{1}−α_{2}}}}{(1 + α_{1}x)^{\frac{α_{2}}{α_{1}−α_{2}}}} )^{−β} , \frac{1}{α_{2} − α_{1}} ln (\frac{1 + α_{2}x}{1 + α_{1}x})] .

Example 12. The exponential Riordan array [\frac{e^{x}}{2e^{x}−e^{2x}} , \frac{e^{2x}−e^{x}}{2e^{x}−e^{2x}} ] begins:

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 3 & 5 & 1 & 0 & 0 & 0 & ⋯ \\ 13 & 31 & 12 & 1 & 0 & 0 & ⋯ \\ 75 & 233 & 133 & 22 & 1 & 0 & ⋯ \\ 541 & 2071 & 1560 & 385 & 35 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Its first column is the sequence \underline{A000670}, known as the ordered Bell numbers. The production matrix of this array is

( \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 2 & 4 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 8 & 7 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 18 & 10 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 32 & 13 & 1 & ⋯ \\ 0 & 0 & 0 & 0 & 50 & 16 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Thus the ordered Bell numbers are the moments μ_{n} of the family of orthogonal polynomials whose coefficient array is given by

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

and whose generating function is given by

\frac{1}{1 − x − \frac{2x^{2}}{1 − 4x − \frac{8x^{2}}{1 − 7x − \frac{18x^{2}}{1 − ⋯}}}}.

4 A matrix product

We recall that the matrix [\frac{1}{1−rx}, \frac{x}{1−rx}] has production matrix

( \begin{matrix}r & 1 & 0 & 0 & 0 & 0 & ⋯ \\ r^{2} & 3r & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 4r^{2} & 5r & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 9r^{2} & 7r & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 16r^{2} & 9r & 1 & ⋯ \\ 0 & 0 & 0 & 0 & 25r^{2} & 11r & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

We use the notation Lag[r] for this matrix [\frac{1}{1−rx}, \frac{x}{1−rx}] [3]. We now form the product L · Lag[r] to get

L · Lag[r] = [e^{αβx} (\frac{α_{1} − α_{2}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} )^{β} , \frac{e^{α_{1}x} − e^{α_{2}x}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} ] · [\frac{1}{1 − rx}, \frac{x}{1 − rx}]

= [e^{αβx} (\frac{α_{1} − α_{2}}{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}} )^{β} \frac{α_{1}e^{α_{2}x} − α_{2}e^{α_{1}x}}{(α_{1} + r)e^{α_{2}x} − (α_{2} + r)e^{α_{1}x}} , \frac{e^{α_{1}x} − e^{α_{2}x}}{(α_{1} + r)e^{α_{2}x} − (α_{2} + r)e^{α_{1}x}} ] .

For β = 1, this product is equal to

[e^{αx} \frac{α_{1} − α_{2}}{(α_{1} + r)e^{α_{2}x} − (α_{2} + r)e^{α_{1}x}} , \frac{e^{α_{1}x} − e^{α_{2}x}}{(α_{1} + r)e^{α_{2}x} − (α_{2} + r)e^{α_{1}x}} ] .

This matrix has a tri-diagonal production array which starts

( \begin{matrix}α + r & 1 & 0 & 0 & 0 & 0 & ⋯ \\ (α_{1} + r)(α_{2} + r) & α + α_{1} + α_{2} + 3r & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 4(α_{1} + r)(α_{2} + r) & α + 2(α_{1} + α_{2}) + 5r & 1 & 0 & 0 & ⋯ \\ 0 & 0 & 9(α_{1} + r)(α_{2} + r) & α + 3(α_{1} + α_{2}) + 7r & 1 & 0 & ⋯ \\ 0 & 0 & 0 & 16(α_{1} + r)(α_{2} + r) & α + 4(α_{1} + α_{2}) + 9r & 1 & ⋯ \\ 0 & 0 & 0 & 0 & 25(α_{1} + r)(α_{2} + r) & α + 5(α_{1} + α_{2}) + 11r & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Thus for β = 1, this product matrix is again the inverse of the coefficient array of a family of orthogonal polynomials. Taking inverses, we arrive at the following product of orthogonal polynomial coefficient arrays:

[\frac{1}{1 + rx}, \frac{x}{1 + rx}] · [(\frac{1 + α_{2}x}{1 + α_{1}x})^{\frac{α}{α_{1}−α_{2}}} \frac{(1 + α_{1}x)^{\frac{α_{2}}{α_{1}−α_{2}}}}{(1 + α_{2}x)^{\frac{α_{1}}{α_{1}−α_{2}}}} , \frac{1}{α_{2} − α_{1}} ln (\frac{1 + α_{2}x}{1 + α_{1}x})]

= [\frac{1}{1 + rx}, \frac{x}{1 + rx}] · [\frac{(1 + α_{2}x)^{\frac{α−α_{1}}{α_{1}−α_{2}}}}{(1 + α_{1}x)^{\frac{α−α_{2}}{α_{1}−α_{2}}}} , \frac{1}{α_{2} − α_{1}} ln (\frac{1 + α_{2}x}{1 + α_{1}x})]

= [\frac{(1 + (α_{1} + r)x)^{\frac{α_{2}−α}{α_{1}−α_{2}}}}{(1 + (α_{2} + r)x)^{\frac{α_{1}−α}{α_{1}−α_{2}}}} , \frac{1}{α_{1} − α_{2}} ln (\frac{1 + (α_{1} + r)x}{1 + (α_{2} + r)x})] .

References

[1] P. Barry, P. Rajković, and M. Petković, An application of Sobolev orthogonal polynomials to the computation of a special Hankel determinant, in W. Gautschi, G. Rassias, and M. Themistocles, eds., Approximation and Computation, Springer, 2010.

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

[3] P. Barry, Some observations on the Lah and Laguerre transforms of integer sequences, J. Integer Seq., 10 (2007), Article 07.4.6.

[4] G.-S. Cheon, H. Kim, and L. W. Shapiro, Riordan group involution, Linear Algebra Appl., 428 (2008), 941–952.

[5] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, New York, 1978.

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

[7] A. Cvetković, P. Rajković and M. Ivković, Catalan numbers, the Hankel transform and Fibonacci numbers, J. Integer Seq., 5 (2002), Article 02.1.3.

[8] E. Deutsch and L. Shapiro, Exponential Riordan arrays, Lec-

ture Notes,  Nankai University,  2004,  available electronically at

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

[9] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices, Adv. in Appl. Math. 34 (2005), 101–122.

[10] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices and Riordan arrays,

http://arxiv.org/abs/math/0702638v1, February 22 2007.

[11] W. Gautschi, Orthogonal Polynomials: Computation and Approximation, Clarendon Press - Oxford, 2003.

[12] C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York.

[13] Tian-Xiao He and R. Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 2009 (2009), 3962–3974.

[14] C. Krattenthaler, Advanced determinant calculus, Sém. Lotharingien

Combin. 42 (1999),  Article B42q,  available electronically at

http://www.mat.univie.ac.at/ kratt/artikel/detsurv.html.

[15] Tian-Xiao He, L. C. Hsu, and P. J.-S. Shiue, The Sheffer group and the Riordan group, Discrete Appl. Math. 155 (2007), 1895–1909.

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

[17] P. Peart and L. Woodson, Triple factorization of some Riordan matrices, Fibonacci Quart., 31 (1993), 121–128.

[18] P. Peart and W.-J. Woan, Generating functions via Hankel and Stieltjes matrices, J. Integer Seq., 3 (2000), Article 00.2.1.

[19] J. Meixner, Orthogonale Polynomsysteme mit einer Besonderen Gestalt der Erzeugenden Funktion, J. Lond. Math. Soc. 9, (1934), 6–13.

[20] S. Roman, The Umbral Calculus, Dover Publications, 2005.

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

[22] L. W. Shapiro, Bijections and the Riordan group, Theoret. Comput. Sci. 307 (2003), 403–413.

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

    cally at http://www.research.att.com/∼njas/sequences/, 2010.

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

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

[26] G. Szegö, Orthogonal Polynomials, 4th ed., Amer. Math. Soc., 1975.

[27] X. J. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, UQAM, Montreal, Québec, 1983.

[28] H. S. Wall, Analytic Theory of Continued Fractions, Chelsea, 1973.

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

[30] J. Zeng, Énumérations de permutations et J-fractions continues, Europ. J. Combin., 14 (1993), 373–382.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 42C05, 11B83, 11C20, 15B05, 15B36, 20B30, 33C45. Keywords: Permutation, integer sequence, orthogonal polynomials, moments, exponential Riordan array, Hankel determinant, Hankel transform.

(Concerned with sequences \underline{A000045}, \underline{A000142}, \underline{A000262}, \underline{A000670}, \underline{A007318}, \underline{A021009}, \underline{A094587}, \underline{A094816}, \underline{A111596}, and \underline{A111884}.)

Received June 25 2010; revised version received September 13 2010 Published in Journal of Integer Sequences, December 5 2010.

Return to Journal of Integer Sequences home page.