On a Transformation of Riordan Moment Sequences

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Abstract

We define a transformation that associates certain exponential moment sequences with ordinary moment sequences in a natural way. The ingredients of this transformation are series reversion, the Sumudu transform (a variant of the Laplace transform), and the inverting of generating functions. This transformation also has a simple interpretation in terms of continued fractions. It associates lattice path objects with permutation objects, and in particular it associates the Narayana triangle with the Eulerian triangle.

1 Introduction

In this note we study relationships between moment sequences that are defined by ordinary Riordan arrays [4, 19, 23] and by certain exponential Riordan arrays [4, 20], which may be described as Eulerian. The theory of orthogonal polynomials [11, 14, 17, 25] defined by Riordan arrays has been much studied [2, 3, 4, 6, 7]. For ordinary Riordan arrays, the associated orthogonal polynomials are generalized Chebyshev polynomials. In this note, we shall define a mapping T , whose inverse T^{−1} maps a subset of the set of moments defined by ordinary Riordan arrays to a set of moments whose exponential generating function is “Eulerian”. A central role in this mapping is played by the Sumudu transform [9, 10, 28].

Many sequences and triangles in this note are referenced by their Axxxxxx number in the On-Line Encyclopedia of Integer Sequences [21, 22], an invaluable tool for notes such as this one.

All matrices in this note are of infinite extent; we show in each case a relevant truncation. The operator [x^{n}] is the operator that extracts the coefficient of x^{n} in a power series [18]. Ordinary Riordan arrays are designated by (g, f) while exponential Riordan arrays are designated by [g, f].

2 Motivation

We begin with the Eulerian generating function

E(x, y; a, b) = \frac{(1 − y)e^{ax(1−y)}}{1 − ye^{bx(1−y)}} .

When a = 0 and b = 1, we get

E(x, y; 0, 1) = \frac{1 − y}{1 − ye^{x(1−y)}} ,

which is the generating function of the Eulerian polynomials

1, y, y(y + 1), y(y^{2} + 4y + 1), y(y^{3} + 11y^{2} + 11y + 1), y(y^{4} + 26y^{3} + 66y^{2} + 26y + 1), …,

with coefficient array the Eulerian triangle \underline{A123125} that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 4 & 1 & 0 & 0 \\ 0 & 1 & 11 & 11 & 1 & 0 \\ 0 & 1 & 26 & 66 & 26 & 1 \end{matrix} ) .

When a = 1 and b = 1, we get

E(x, y; 1, 1) = \frac{(1 − y)e^{x(1−y)}}{1 − ye^{x(1−y)}} ,

which is the generating function of the variant Eulerian polynomials S_{n}(y) that begin

1, 1, y + 1, y^{2} + 4y + 1, y^{3} + 11y^{2} + 11y + 1, y^{4} + 26y^{3} + 66y^{2} + 26y + 1, ….

Recall that we have [15]

S_{n}(t) = ∑_{w∈S_{n}} t^{des(w)}.

These polynomials have a coefficient array \underline{A173018} that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 4 & 1 & 0 & 0 & 0 \\ 1 & 11 & 11 & 1 & 0 & 0 \\ 1 & 26 & 66 & 26 & 1 & 0 \end{matrix} ) .

When a = 1 and b = 2 we get

E(x, y; 1, 2) = \frac{(1 − y)e^{x(1−y)}}{1 − ye^{2x(1−y)}} ,

which is the generating function of the type B Eulerian polynomials

1, y + 1, y^{2} + 6y + 1, y^{3} + 23y^{2} + 23y + 1, y^{4} + 76y^{3} + 230y^{2} + 76y + 1, …, with coefficient array \underline{A060187} that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 6 & 1 & 0 & 0 & 0 \\ 1 & 23 & 23 & 1 & 0 & 0 \\ 1 & 76 & 230 & 76 & 1 & 0 \\ 1 & 237 & 1682 & 1682 & 237 & 1 \end{matrix} ) .

We wish now to associate with this exponential generating function (in x) E(x, y; a, b) an ordinary generating function. To this end we shall

• Invert the generating function E(x, y; a, b) to get 1/E(x, y; a, b)

• Take the Sumudu transform of 1/E(x, y; a, b) to get an ordinary generating function g(x, y; a, b)

• Use series reversion to form the generating function G(x, y; a, b) = \frac{1}{x}Rev(xg(x, y, a, b)). We shall designate this transformation pipeline by the symbol T . Thus we have

T (E(x, y; a, b)) = G(x, y; a, b).

We now work out the form of G(x, y; a, b). We have

\frac{1}{E(x, y; a, b)} = \frac{1 − ye^{bx(1−y)}}{(1 − y)e^{ax(1−y)}} .

Now the Sumudu transform is given by the variant of the Laplace transform

S(E)(x) = \frac{1}{x} ∫_{0}^{∞} E(t, y; a, b)e^{−t/x} dt.

We find that

S (\frac{1}{E(t, y; a, b)}) (x) = \frac{1 − x(a(y − 1) + b)}{1 + (1 − y)(2a − b)x + a(a − b)(y − 1)^{2}x^{2}} .

To finish, we multiply this generating function by x, we revert the result, and then we divide this reversion by x. We obtain that

G(x, y; a, b) = \frac{1 + x(y − 1)(2a − b) − \sqrt{1 − 2bx(y + 1) + b^{2}x^{2}(y − 1)^{2}}}{2(ax(a − b)(y − 1)^{2} + a(y − 1) + b)} .

Writing c(x) = \frac{1−\sqrt{1−4x}}{2x} for the generating function of the Catalan numbers [24] C_{n} = \frac{1}{n+1} \binom{2n}{n}, we can write this as

G(x, y; a, b) = \frac{1}{1 − x(b − 2a)(y − 1)}c (\frac{x(ax(a − b)(y − 1)^{2} + ay − a + b)}{(1 − x(b − 2a)(y − 1))^{2}}) .

Thus

T (\frac{(1 − y)e^{at(1−y)}}{1 − ye^{bt(1−y)}} ) (x) = \frac{1}{1 − x(b − 2a)(y − 1)}c (\frac{x(ax(a − b)(y − 1)^{2} + a(y − 1) + b)}{(1 − x(b − 2a)(y − 1))^{2}}) .

Example 1. We take the case a = 0, b = 1. We find that

T (E(t, y; 0, 1)) (x) = \frac{1}{1 + x(1 − y)}c (\frac{x}{1 + x(1 − y)}) .

This is the generating function for the Narayana polynomials that begin

1, y, y^{2} + y, y^{3} + 3y^{2} + y, y^{4} + 6y^{3} + 6y^{2} + y, …

with coefficient array the Narayana triangle \underline{A090181} that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 3 & 1 & 0 & 0 \\ 0 & 1 & 6 & 6 & 1 & 0 \\ 0 & 1 & 10 & 20 & 10 & 1 \end{matrix} ) .

Thus the Eulerian triangle is transformed to the Narayana triangle by T . Note that another perspective on links between the Narayana numbers and the Eulerian numbers can be found in [1], for instance.

Example 2. We consider the case a = 1 and b = 1. We find that

T (E(x, y; 1, 1)) (x) = \frac{1}{1 + x(y − 1)}c (\frac{xy}{(1 + x(y − 1))^{2}} ) .

This is the generating function for the Narayana polynomials N_{n}(y) that begin

1, 1, y + 1, y^{2} + 3y + 1, y^{3} + 6y^{2} + 6y + 1, …,

with coefficient array the Narayana triangle \underline{A131198} that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 \\ 1 & 6 & 6 & 1 & 0 & 0 \\ 1 & 10 & 20 & 10 & 1 & 0 \end{matrix} ) .

We have [15]

N_{n}(t) = ∑_{w∈S_{n}(231)} t^{des(w)}.

Example 3. We consider the B type case a = 1 and b = 2. We find that

T (E(t, y; 1, 2)) (x) = c (x(1 + y − x(y − 1)^{2})) .

This is the generating function of the polynomials that begin

1, y + 1, y^{2} + 6y + 1, y^{3} + 19y^{2} + 19y + 1, y^{4} + 48y^{3} + 126y^{2} + 48y + 1, …,

with coefficient array that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 6 & 1 & 0 & 0 & 0 & 0 \\ 1 & 19 & 19 & 1 & 0 & 0 & 0 \\ 1 & 48 & 126 & 48 & 1 & 0 & 0 \\ 1 & 109 & 562 & 562 & 109 & 1 & 0 \\ 1 & 234 & 2031 & 3916 & 2031 & 234 & 1 \end{matrix} ) .

This is thus the T transform of the type B Eulerian triangle. Note that setting y = 1 gives us the row sums, which are 2^{n}C_{n} = [x^{n}]c(2x).

Example 4. If a_{n} = n![x^{n}]f(x) and b_{n} = [x^{n}]T (f(s))(x), then we shall write

b_{n} = T a_{n}.

Thus we have, for instance,

T n! = C_{n}.

This follows because • We start with f(x) = \frac{1}{1−x}, which we invert to get 1 − x

• The Sumudu transform of 1 − t is 1 − x

• We have c(x) = \frac{1}{x}Rev(x(1 − x)).

What follows is a short table of transform pairs.

OEIS  a_{n}  b_{n} = T a_{n}  OEIS
\underline{A000142}  n!  C_{n}  \underline{A000108}
\underline{A049774} Permutations without double falls  Motzkin numbers  \underline{A001006}
\underline{A097899} Permutations with no runs of length 1  Motzkin sums  \underline{A005043}
\underline{A000670}  Fubini numbers  Little Schroeder numbers \underline{A001003}
\underline{A001586}  Springer numbers  -  \underline{A052709}
\underline{A000629}  Cyclically ordered partitions  Large Schroeder numbers \underline{A006318}

We close this section by noting that for sequences with ordinary generating functions that can be put in the form

G(x, y; a, b) = \frac{1}{1 + x(b − 2a)(1 − y)}c (\frac{x(ax(a − b)(y − 1)^{2} − a(1 − y) + b)}{(1 + x(b − 2a)(1 − y))^{2}}) ,

for appropriate choices of the parameters a, b and y, we can define the inverse transform T^{−1}. This is formed by reversing the above steps.

• Calculate g(x) = \frac{1}{x}Rev(xG)

• Calculate the inverse Sumudu transform of g(s) to get e(t)

• Form E(t) = \frac{1}{e(t)}.

3 Riordan arrays and Riordan moment sequences

All the sequences encountered thus far are examples of Riordan moment sequences. By this we mean that they are moment sequences associated with families of orthogonal polynomials that are defined either by ordinary or by exponential Riordan arrays. We recall that an ordinary Riordan array is an invertible lower-triangular matrix R defined by two power series

g(x) = 1 + g_{1}x + g_{2}x^{2} + ⋯,

and

f(x) = f_{1}x + f_{2}x^{2} + ⋯,

whose (n, k) element R_{n,k} is given by

R_{n,k} = [x^{n}]g(x)f(x)^{k}.

We write R = (g, f) to signify this. An ordinary Riordan array R defines a family of orthogonal polynomials if we have

R = (\frac{1 + λx + μx^{2}}{1 + αx + βx^{2}} , \frac{x}{1 + αx + βx^{2}} ) .

The inverse of the Riordan array R = (g, f) is given by

R^{−1} = (\frac{1}{g(f̄)}, f̄) ,

where f̄(x) = Rev(f)(x) is the reversion of the power series f(x), defined as the power series that satisfies f(f̄(x)) = x and f̄(f(x)) = x. For R = (\frac{1+λx+μx^{2}}{1+αx+βx^{2}} , \frac{x}{1+αx+βx^{2}} ) we have

R^{−1} = (μ(x), \frac{1 − αx − \sqrt{1 − 2αx + x^{2}(α^{2} − 4β)}}{2βx}) ,

where

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

The sequence with generating function μ(x) then appears as the first column of the inverse matrix R^{−1}. This is the (ordinary) Riordan moment sequence associated with the family of orthogonal polynomials defined by R. We have that

μ(x) = \frac{1}{1 − (α − λ)x − \frac{(β − μ)x^{2}}{1 − αx − \frac{βx^{2}}{1 − αx − \frac{βx^{2}}{1 − ⋯}}}}.

In an obvious notation, we write this as

μ(x) = J (α − λ, α, α, …; β − μ, β, β, …),

where J stands for “Jacobi”. This thus is the form of the generating function of an ordinary Riordan moment sequence. The corresponding family of orthogonal polynomials P_{n}(x) satisfies the associated three-term recurrence

P_{n}(x) = (x − α)P_{n−1}(x) − βP_{n−2}(x),

with P_{0}(x) = 1, P_{1}(x) = x − α + λ, and P_{2}(x) = x^{2} + x(λ − 2α) + α^{2} − αλ − β + μ. In the case that μ = 0, we obtain

μ(x) = \frac{1}{1 − x(α − 2λ)}c (\frac{x(λ − x(αλ − β − λ^{2}))}{(1 − x(α − 2λ))^{2}}) .

By the fundamental theorem of Riordan arrays, this can be written

μ(x) = (\frac{1}{1 − x(α − 2λ)}, \frac{x(λ − x(αλ − β − λ^{2}))}{(1 − x(α − 2λ))^{2}}) · c(x).

Proposition 5. We have

G(x, y; a, b) = J (y(b − a) + a, b(y + 1), b(y + 1), …; b^{2}y, b^{2}y, …).

We now turn our attention to exponential Riordan arrays. An exponential Riordan array R is an invertible lower-triangular matrix defined by two power series

g(x) = 1 + g_{1} \frac{x}{1!} + g_{2} \frac{x^{2}}{2!} + g_{3} \frac{x^{3}}{3!} + ⋯,

and

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

The general (n, k)-th element of R is then defined to be

R_{n,k} = \frac{n!}{k!}[x^{n}]g(x)f(x)^{k}.

We write [g, f] to denote this matrix. With every exponential Riordan array R we can associate its production matrix P_{R} which is defined to be the matrix P_{R} = R^{−1}\overline{R}, where \overline{R} is the matrix R with its first row removed [12, 13]. The matrix R^{−1} will then be the coefficient array of a family of orthogonal polynomials if P_{R} has a bivariate generating function of the form

e^{xy}(α + βx + y(1 + γx + δx^{2})) = e^{xy}(Z(x) + yA(x)),

where

A(x) = f′(f̄(x)), Z(x) = \frac{g′(f̄(x))}{g(f̄(x))}.

The matrix P_{R} then begins

( \begin{matrix}α & 1 & 0 & 0 & 0 & 0 & 0 \\ β & α + γ & 1 & 0 & 0 & 0 & 0 \\ 0 & 2β + 2δ & α + 2γ & 1 & 0 & 0 & 0 \\ 0 & 0 & 3(β + 2δ) & α + 3γ & 1 & 0 & 0 \\ 0 & 0 & 0 & 4(β + 3δ) & α + 4γ & 1 & 0 \\ 0 & 0 & 0 & 0 & 5(β + 4δ) & α + 5γ & 1 \\ 0 & 0 & 0 & 0 & 0 & 6(β + 5δ) & α + 6γ \end{matrix} ) .

Note that the diagonal terms form an arithmetic sequence, while the sub-diagonal terms, when divided successively by 1, 2, 3, …, also form an arithmetic sequence.

The corresponding exponential Riordan moment sequence (given by the first column elements of R) will then have a generating function given by the continued fraction [8, 26, 27]

μ_{e}(x) = \frac{1}{1 − αx − \frac{βx^{2}}{1 − (α + γ)x − \frac{(2β + 2δ)x^{2}}{1 − (α + 2γ)x − \frac{(3β + 6δ)x^{2}}{1 − ⋯}}}},

with coefficients drawn from the production matrix. Thus exponential Riordan moment sequences have ordinary generating functions given by

J (α, α + γ, α + 2γ, …; β, 2(β + δ), 3(β + 2δ), …).

Example 6. The exponential Riordan array \underline{A021009}

L = [\frac{1}{1 + x}, \frac{x}{1 + x}]

with general term

L_{n,k} = \frac{n!}{k!}(−1)^{n−k}\binom{n}{k}

is the coefficient matrix of the scaled Laguerre polynomials. The corresponding moments are n!, given by the initial column of the inverse array

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

The production matrix of this array begins

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

Thus n!, which has exponential generating function \frac{1}{1−x}, has an ordinary generating function given by

\frac{1}{1 − x − \frac{x^{2}}{1 − 3x − \frac{4x^{2}}{1 − 5x − \frac{9x^{2}}{1 − 7x − ⋯}}}}.

With regard to the exponential generating function E(x, y; a, b) (in x), we have the following result.

Theorem 7. The exponential Riordan array

[\frac{1 + bxy}{(1 + bx)^{a/b}} , \frac{1}{b(1 − y)} ln (\frac{1 + bx}{1 + bxy} )]

is the coefficient array of the family of orthogonal polynomials whose moment sequence has exponential generating function E(x, y; a, b).

Proof. The inverse of the above Riordan array is given by

[\frac{(1 − y)e^{ax(1−y)}}{1 − ye^{bx(1−y)}} , \frac{e^{bx} − e^{bxy}}{b(e^{bxy} − ye^{bx})}] .

We find that

A(x) = (1 + bx)(1 + bxy) and Z(x) = a(1 − y) + by + b^{2}yx.

This allows us to calculate the production matrix of the inverse Riordan array, which begins

( \begin{matrix}y(b − a) + a & 1 & 0 & 0 & 0 \\ b^{2}y & y(2b − a) + a + b & 1 & 0 & 0 \\ 0 & 4b^{2}y & y(3b − a) + a + 2b & 1 & 0 \\ 0 & 0 & 9b^{2}y & y(4b − a) + a + 3b & 1 \\ 0 & 0 & 0 & 16b^{2}y & y(5b − a) + a + 4b \end{matrix} ) .

This indicates that E(x, y; a, b) is the exponential generating function of an exponential Riordan moment sequence which has an ordinary generating function given by

\frac{1}{1 − (y(b − a) + a)x − \frac{b^{2}yx^{2}}{1 − (y(2b − a) + a + b)x − \frac{4b^{2}yx^{2}}{1 − (y(3b − a) + a + 2b)x − \frac{9b^{2}yx^{2}}{1 − ⋯}}}}.

Corollary 8. The ordinary generating function of the exponential Riordan moment sequence with e.g.f. E(x, y; a, b) is given by

J (y(b − a) + a, y(b − a) + a + b(1 + y), y(b − a) + a + 2b(1 + y), …; b^{2}y, 4b^{2}y, 9b^{2}y, …).

This is the Eulerian case, where β = δ = b^{2}y. We are now in a position to interpret the transformation T in terms of ordinary generating functions expressed as continued fractions. The description is easiest in the direction of T^{−1}.

We have that T^{−1} maps the ordinary Riordan moments defined by the Riordan array

(\frac{1 + (a(y − 1) + b)x}{1 + b(y + 1)x + b^{2}yx^{2}} , \frac{x}{1 + b(y + 1)x + b^{2}yx^{2}} )

to the exponential Riordan moments defined by the exponential Riordan array

[\frac{1 + bxy}{(1 + bx)^{a/b}} , \frac{1}{b(1 − y)} ln (\frac{1 + bx}{1 + bxy} )] .

In both cases, the moment sequences are described by the first column elements of the respective inverse arrays. In terms of continued fractions, we have that T^{−1} maps

J (y(b − a) + a, b(y + 1), b(y + 1), …; b^{2}y, b^{2}y, …)

to

J (y(b − a) + a, y(b − a) + a + b(1 + y), y(b − a) + a + 2b(1 + y), …; b^{2}y, 4b^{2}y, 9b^{2}y, …).

Thus the first elements are mapped to their partial sums, while the second terms are scaled by (1, 4, 9, …). Reversing this process (taking first differences; dividing by (1, 4, 9, …)) now gives us the effect of T .

4 Further results

Proposition 9. The moment sequence μ_{n} defined by the ordinary Riordan array

(\frac{1 − αx}{1 + βx + γx^{2}} , \frac{x}{1 + βx + γx^{2}} )

satisfies

μ_{n} = [x^{n}]\frac{1}{x}Rev (\frac{x(1 + αx)}{1 + (β + 2α)x + (α^{2} + αβ + γ)x^{2}} ) .

Proof. The moment sequence is the first column of the inverse array. This has generating function

\frac{2}{1 − (2α + β)x + \sqrt{1 − 2βx + (β^{2} − 4γ)x^{2}}} ,

which is given by the reversion in the statement of the proposition.

Corollary 10. The generating function G(x, y; a, b) = T (E(t, y; a, b))(x) is the generating function of the moment sequence of the family of orthogonal polynomials defined by the ordinary Riordan array

(\frac{1 − (a(y − 1) + b)x}{1 + b(1 + y)x + b^{2}yx^{2}} , \frac{x}{1 + b(1 + y)x + b^{2}yx^{2}} )

Proof. We compare the coefficients α, β, γ in the proposition with the coefficients in

S (\frac{1}{E(t, y; a, b)}) (x).

Thus

α = −a(y − 1) + b, β + 2α = (1 − y)(2a − b), α^{2} + αβ + γ = a(a − b)(y − 1)^{2}.

We solve these equations for α, β, γ.

Proposition 11. Let μ_{o}(x) be the generating function of the moment sequence of the ordinary Riordan array

(\frac{1 − αx}{1 + βx + γx^{2}} , \frac{x}{1 + βx + γx^{2}} ) .

Then

• μ_{0}(x) = J (β + α, β, β, …; γ, γ, γ, …).

• The T^{−1} transform of μ_{0}(x) is

μ_{e}(x) = \frac{\sqrt{β^{2} − 4γ}e^{\frac{1}{2} (2α+β)t}}{\sqrt{β^{2} − 4γ} cosh (\frac{1}{2} \sqrt{β^{2} − 4γ}t) − β sinh (\frac{1}{2} \sqrt{β^{2} − 4γ}t)}

• The ordinary generating function of the transformed moment sequence is given by

J (α + β, α + 2β, α + 3β, …; γ, 4γ, 9γ, …).

5 Further examples

Example 12. The Motzkin numbers M_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k} are the moments of the Riordan array

(\frac{1}{1 + x + x^{2}} , \frac{x}{1 + x + x^{2}} ) ,

where α = 0, β = 1, γ = 1. In this case we find that

M_{n} = [x^{n}]\frac{1}{x}Rev (\frac{x}{1 + x + x^{2}} ) .

The generating function of M_{n} is thus \frac{1−x−\sqrt{1−2x−3x^{2}}}{2x^{2}} , which can be expressed as the continued fraction

\frac{1}{1 − x − \frac{x^{2}}{1 − x − \frac{x^{2}}{1 − x − ⋯}}},

or

J (1, 1, 1, …; 1, 1, 1, …).

Thus the T^{−1} transform of the Motzkin sequence has an ordinary generating function given by

J (1, 2, 3, …; 1, 4, 9, …).

This is \underline{A049774}, the number of permutations of n elements not containing the consecutive pattern 123.

Example 13. The so-called “Motzkin sums” MS_{n} = ∑_{k=0}^{n} \binom{n}{k}(\binom{k}{n−k} − \binom{k}{n−k−1}) \underline{A005043} are the moments of the Riordan array

(\frac{1 + x}{1 + x + x^{2}} , \frac{x}{1 + x + x^{2}} ) ,

where a = 1, b = 1, c = 1. In this case we find that

MS_{n} = [x^{n}]\frac{1}{x}Rev (\frac{x(1 − x)}{1 − x + x^{2}} ) .

In this case the generating function \frac{1+x−\sqrt{1−2x−3x^{2}}}{2x(1+x)} is given by

J (0, 1, 1, …; 1, 1, 1, …).

Thus its T^{−1} transform is given by

J (0, 1, 2, 3, …; 1, 4, 9, …).

This is \underline{A097899}, the number of permutations of [n] with no runs of length 1.

Example 14. We consider the sequence a_{n} \underline{A052186} which begins

1, 0, 1, 3, 14, 77, 497, 3676, ….

The ordinary generating function of this sequence is

J (0, 3, 5, 7, 9, …; 1, 4, 9, 16, 25, …).

The T transform of this sequence will therefore have generating function

J (0, 3, 2, 2, 2, …; 1, 1, 1, 1, 1, …).

Now the sequence with generating function

J (1, 3, 2, 2, 2, …; 1, 1, 1, 1, 1, …)

which begins

1, 1, 2, 6, 21, 78, 298, 1157, 4539, 17936, …

is \underline{A129775}, the number of maximally clustered permutations in S_{n} (those that avoid the patterns 3421, 4312 and 43214). Thus the image of \underline{A052186} by T is the INVERT(−1) transform of \underline{A129775}. (The INVERT(a) transform of the sequence with generating function f(x) (where f_{0} ≠ 0) is the sequence with generating function \frac{f(x)}{1+axf(x)}). Note that a_{n} has the integral representation [16]

a_{n} = ∫_{0}^{∞} \frac{x^{n}e^{x}}{(Ei(x) + e^{x})^{2} + π^{2}} dx + \frac{−𝔭}{𝔭 − 1},

where 𝔭 ≈ 0.434818 is a simple pole of ϕ(z) = \frac{z}{1−e^{z}E_{1}(z)} − z.

Example 15. We consider the T^{−1} transform of the sequence \underline{A064641}, which has a generating function

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

The general term of this sequence b_{n} has the integral representation

b_{n} = \frac{1}{2π} ∫_{3−2\sqrt{3}}^{3+2\sqrt{3}} x^{n} \frac{\sqrt{3(1 + 2x) − x^{2}}}{1 + x} dx.

This sequence counts the number of paths from (0, 0) to (n, n) not rising above y = x, using steps (1, 0), (0, 1), (1, 1) and (2, 1).

Letting g(x) = \frac{1−x}{1+x+x^{2}} , we calculate the inverse Laplace transform of \frac{1}{s}f (\frac{1}{s}). We obtain

e^{−t/2} (cos (\frac{\sqrt{3}t}{2}) − \sqrt{3} sin (\frac{\sqrt{3}t}{2})) .

Thus the desired transform is the exponential generating function

\frac{e^{t/2}}{cos (\frac{\sqrt{3}t}{2}) − \sqrt{3} sin (\frac{\sqrt{3}t}{2})}.

This expands to the sequence that begins

1, 2, 7, 35, 232, 1919, 19045, 220502, 2917663, 43431983, ….

In this case we have

J (2, 3, 3, 3, …; 3, 3, 3, 3) → J (2, 5, 8, 11, …; 3, 12, 27, 48, …).

Example 16. We have seen that the T^{−1} transform operates on moment sequences defined by Riordan arrays of the form

(\frac{1 − ax}{1 + bx + cx^{2}} , \frac{x}{1 + bx + cx^{2}} ) .

However, ordinary Riordan arrays of the form

(\frac{1 − ax − bx^{2}}{1 + cx + dx^{2}} , \frac{x}{1 + cx + dx^{2}} )

also define moment sequences. To see the nature of the obstruction, we take the example of the matrix

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

Then the relevant moment sequence has generating function

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

This expands to give the sequence \underline{A111961}, which begins

1, 2, 6, 18, 56, 176, 558, 1778, 5686, 18230, ….

Its generating function is equal to

J (2, 1, 1, 1, …; 2, 1, 1, 1, …).

We now attempt to apply the T^{−1} transform in its “reversion-Sumudu^{−1}-inverting” form. We find that

\frac{1}{x}Rev(xG(x)) = \frac{\sqrt{1 + 2x + 5x^{2}} − x}{1 + 2x + 4x^{2}}.

Given its non-rational form, it is problematic to apply S^{−1} to this generating function. We can of course proceed as before with the continued fraction mapping, to get

J (2, 1, 1, 1, …; 2, 1, 1, 1, …) → J (2, 3, 4, 5, …; 2, 4, 9, 16, …).

The image sequence then begins

1, 2, 6, 22, 94, 454, 2454, 14766, 98678, 730422, ….

6 A note on the symmetric Eulerian triangle

We have seen two variants of the Eulerian triangle that are associated with the sequence 1, 4, 9, . . .. The Pascal-like (or centrally symmetric) variant \underline{A008292} that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 4 & 1 & 0 & 0 & 0 & 0 \\ 1 & 11 & 11 & 1 & 0 & 0 & 0 \\ 1 & 26 & 66 & 26 & 1 & 0 & 0 \\ 1 & 57 & 302 & 302 & 57 & 1 & 0 \\ 1 & 120 & 1191 & 2416 & 1191 & 120 & 1 \end{matrix} )

differs from the other two forms. To see this, we consider the bivariate generating function

\frac{e^{x(1+y)}(1 − y)^{2}}{(ye^{x} − e^{yx})^{2}} .

Again, we can show that this is the generating function of an exponential Riordan moment sequence. In this case, we find that the ordinary generating function is

J (y + 1, 2(y + 1), 3(y + 1), …; 2y, 6y, 12y, 20y, …)

thus associating it with the sequence 1, 3, 6, … rather than 1, 4, 9, . . ..

If we now use an analogue of the T transform to associate with this an ordinary Riordan moment sequence, we get

J (y + 1, 2(y + 1), …; 2y, 6y, 12y, …) → J (y + 1, y + 1, y + 1, …; 2y, 2y, 2y, …).

This last term gives us the triangle with bivariate generating function

g(x, y) = \frac{1}{1 − x(1 + y)}c (\frac{2x^{2}y}{(1 − x(1 + y))^{2}} ) .

This triangle begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 4 & 1 & 0 & 0 & 0 & 0 \\ 1 & 9 & 9 & 1 & 0 & 0 & 0 \\ 1 & 16 & 38 & 16 & 1 & 0 & 0 \\ 1 & 25 & 110 & 110 & 25 & 1 & 0 \\ 1 & 36 & 255 & 480 & 255 & 36 & 1 \end{matrix} ) .

We note that the triangle whose generating function is given by

\frac{1}{x}Rev_{x}(xg(x, y))

is the signed Pascal-like Riordan array

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

Thus this latter Riordan array may be seen as a simple antecedent to the Pascal-like triangle of Eulerian numbers.

7 Conclusion

In this note we have shown that ordinary Riordan moment sequences, defined by Riordan arrays of the form (\frac{1−αx}{1+βx+γx^{2}} , \frac{x}{1+βx+γx^{2}} ), can be mapped to exponential Riordan moments of Eulerian type. Some interesting sequence pairings have been exhibited between lattice path theoretic sequences and permutation-based sequences. There remains the challenge of putting this algebraic-analytic mapping into a full combinatorial context. As an example, we have seen that

T : ∑_{w∈S_{n}} t^{des(w)} → ∑_{w∈S_{n}(231)} t^{des(w)}.

8 Acknowledgments

The author is indebted to the anonymous reviewers for their careful reading of this paper and their helpful remarks.

References

[1] J. Agapito, On symmetric polynomials with only real zeros and nonnegative γ-vectors, Linear Algebra App., 451 (2014), 260–289.

[2] P. Barry and A. M. Mwafise, Classical and semi-classical orthogonal polynomials defined by Riordan arrays, and their moment sequences, J. Integer Sequences, 21 (2018), Article 18.1.5.

[3] P. Barry, On the restricted Chebyshev-Boubaker polynomials, Integral Transforms Spec. Funct., 28 (2017), 1–16.

[4] P. Barry, Riordan Arrays: A Primer, Logic Press, 2017.

[5] P. Barry, A note on a family of generalized Pascal matrices defined by Riordan arrays, J. Integer Sequences, 16 (2013), Article 13.5.4.

[6] P. Barry, Riordan arrays, orthogonal polynomials as moments, and Hankel transforms, J. Integer Sequences, 14 (2011), Article 11.2.2.

[7] P. Barry and A. Hennessy, Meixner-type results for Riordan arrays and associated integer sequences, J. Integer Sequences, 13 (2010), Article 10.9.4.

[8] P. Barry, Continued fractions and transformations of integer sequences, J. Integer Sequences, 12 (2009), Article 09.7.6.

[9] F. B. M. Belgacem and A. A. Karaballi, Sumudu transform fundamental properties investigations and applications, Int. J. Stoch. Anal., 2006, Article ID 91083, 1–23.

[10] F. B. M. Belgacem, A. A. Karaballi, and S. L. Kalla, Analytical investigations of the Sumudu transform and applications to integral production equations, Math. Probl. Eng., 2003 (2003), 103–118.

[11] T. S. Chihara, An Introduction to Orthogonal Polynomials, Dover Publicatons, 2011.

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

[13] E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices and Riordan arrays, Ann. Comb., 13 (2009), 65–85.

[14] W. Gautschi, Orthogonal Polynomials: Computation and Approximation, Clarendon Press, 2004.

[15] T. Kyle Petersen, Eulerian Numbers, Birkhäuser, 2015.

[16] R. J. Martin and M. J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica, 35 (2015), 309–315.

[17] J. C. Mason and D. C. Handscomb, Chebyshev Polynomials, Chapman and Hall/CRC, 2002.

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

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

[20] L. Shapiro, A survey of the Riordan group, available electronically at Center for Combinatorics, Nankai University, 2018.

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

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

[22] N. J. A. Sloane, The on-line encyclopedia of integer sequences, Notices Amer. Math. Soc., 50 (2003), 912–915.

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

[24] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

[25] G. Szegö, Orthogonal Polynomials, 4th edition, Amer. Math. Soc., 1975.

[26] G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Lecture Notes, LACIM, UQAM, Montreal, Québec, 1984. Available at

    http://www.xavierviennot.org/xavier/polynomes_orthogonaux.html.

[27] H. S. Wall, Analytic Theory of Continued Fractions, AMS Chelsea Publishing, 2000.

[28] G. K. Watugala, Sumudu transform: a new integral transform to solve differential equations and control engineering problems, Internat. J. Math. Ed. Sci. Tech., 24 (1993), 35–43.

2010 Mathematics Subject Classification: Primary 15B36; Secondary 33C45, 11B83, 11C20, 05A15, 44A10. Keywords: Riordan array, exponential generating function, Narayana triangle, Eulerian triangle, Catalan number, moment sequence, orthogonal polynomial, Sumudu transform.

(Concerned with sequences \underline{A000108}, \underline{A000142}, \underline{A000629}, \underline{A000670}, \underline{A001003}, \underline{A001006}, \underline{A001586}, \underline{A005043}, \underline{A006318}, \underline{A008292}, \underline{A021009}, \underline{A049774}, \underline{A052186}, \underline{A052709}, \underline{A060187}, \underline{A064641}, \underline{A090181}, \underline{A097899}, \underline{A111961}, \underline{A123125}, \underline{A129775}, \underline{A131198}, and \underline{A173018}.)

Received February 9 2018; revised versions received July 10 2018; July 16 2018. Published in Journal of Integer Sequences, August 23 2018.

Return to Journal of Integer Sequences home page.