Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths

Paul Barry School of Science Waterford Institute of Technology Ireland

                     pbarry@wit.ie

Aoife Hennessy Department of Computing, Mathematics and Physics Waterford Institute of Technology Ireland

               aoife.hennessy@gmail.com

Abstract

We study a family of polynomials in two variables, identifying them as the moments of a two-parameter family of orthogonal polynomials. The coefficient array of these orthogonal polynomials is shown to be an ordinary Riordan array. We express the generating function of the sequence of polynomials under study as a continued fraction, and determine the corresponding Hankel transform. An alternative characterization of the polynomials in terms of a related Riordan array is also given. This Riordan array is associated with Łukasiewicz paths. The special form of the production matrices is exhibited in both cases. This allows us to produce a bijection from a set of colored Łukasiewicz paths to a set of colored Motzkin paths. The polynomials studied generalize the notion of Narayana polynomial.

1 Introduction

In this note, we shall be concerned with the family of bivariate polynomials defined by

Q_{n}(r, s) = ∑_{k=0}^{n} ∑_{j=0}^{k} \binom{n}{j}\binom{n − j}{2(k − j)}a_{k−j}(s)r^{k},

where

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

Our main goal is to characterize Q_{n}(r, s) as the moment sequence of a family of orthogonal polynomials, and in so doing also show that the sequence Q_{n}(r, s) has Hankel transform h_{n}(r, s) = det(Q_{i+j}(r, s))_{0≤i,j≤n} [26] given by

h_{n}(r, s) = s^{n}r^{\binom{n+1}{2}}.

Examples of these sequences include the shifted Catalan numbers Q_{n}(1, 1), the central binomial coefficients Q_{n}(1, 2), the central Delannoy numbers Q_{n}(2, 2), and many other sequences that are documented in the On Line Encyclopedia of Integer Sequences [31, 32].

We use the production matrix of a particular Riordan array to establish the existence of a family of orthogonal polynomials for which the generalized Narayana polynomials are moments. We find it interesting to look at a closely related Riordan array, again with the generalized Narayana polynomials as elements of the first column, but where now the production matrix is not tri-diagonal. It does however have a structure that is interesting in its own right. The Hankel transform of the row sum sequence of this second Riordan array is also interesting to study.

2 Preliminaries on integer sequences, Riordan arrays and Hankel transforms

For an integer sequence a_{n}, that is, an element of ℤ^{ℕ}, the power series f(x) = ∑_{n=0}^{∞} a_{n}x^{n} is called the ordinary generating function or g.f. of the sequence. a_{n} is thus the coefficient of x^{n} in this series. We denote this by a_{n} = [x^{n}]f(x). For instance, F_{n} = [x^{n}]\frac{x}{1−x−x^{2}} is the n-th Fibonacci number \underline{A000045}, while C_{n} = [x^{n}]\frac{1−\sqrt{1−4x}}{2x} is the n-th Catalan number \underline{A000108}. We use the notation 0^{n} = [x^{n}]1 for the sequence 1, 0, 0, 0, …, \underline{A000007}. Thus 0^{n} = [n = 0] = δ_{n,0} = \binom{0}{n}. Here, we have used the Iverson bracket notation [19], defined by [P] = 1 if the proposition P is true, and [P] = 0 if P is false.

For a power series f(x) = ∑_{n=0}^{∞} a_{n}x^{n} with f(0) = 0 we define the reversion or compositional inverse of f to be the power series f̄(x) such that f(f̄(x)) = x.

For a lower triangular matrix (a_{n,k})_{n,k≥0} the row sums give the sequence with general term ∑_{k=0}^{n} a_{n,k}.

The Riordan group [30, 33], 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 [33]. We assume in addition that f_{1} = 1 in what follows. The associated matrix is the matrix whose i-th column is generated by g(x)f(x)^{i} (the first column being indexed by 0). The matrix corresponding to the pair g, f is denoted by (g, f) or R(g, f). The group law is then given by

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

The identity for this law is I = (1, x) and the inverse of (g, f) is (g, f)^{−1} = (1/(g ∘ f̄), f̄) where f̄ is the compositional inverse of f.

If M is the matrix (g, f), and a = (a_{0}, a_{1}, …)′ is an integer sequence with ordinary generating function A (x), then the sequence Ma has ordinary generating function g(x)A(f(x)). The (infinite) matrix (g, f) can thus be considered to act on the ring of integer sequences ℤ^{ℕ} by multiplication, where a sequence is regarded as a (infinite) column vector. We can extend this action to the ring of power series ℤ[[x]] by

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

Example 1. The so-called binomial matrix B is the element (\frac{1}{1−x}, \frac{x}{1−x}) of the Riordan group. It has general element \binom{n}{k}, and hence as an array coincides with Pascal’s triangle. More generally, B^{m} is the element (\frac{1}{1−mx}, \frac{x}{1−mx}) of the Riordan group, with general term \binom{n}{k}m^{n−k}. It is easy to show that the inverse B^{−m} of B^{m} is given by (\frac{1}{1+mx}, \frac{x}{1+mx}).

For an invertible matrix L, its production matrix (also called its Stieltjes matrix) [15, 16] is the matrix

P_{L} = L^{−1}L̂,

where L̂ is the matrix L with its first row removed. A Riordan array L is the inverse of the coefficient array of a family of orthogonal polynomials if and only if P_{L} is tri-diagonal [7, 8]. Necessarily, the Jacobi coefficients of these orthogonal polynomials are then constant. Such types of polynomials have been studied in many contexts, including orthogonal polynomials [34, 18, 1, 2], random walks [23, 20], group theory [13], non-commutative probability [29, 3, 11], and the study of random matrices [14].

An important feature of Riordan arrays is that they have a number of sequence characterizations [12, 21]. The simplest of these is as follows.

Proposition 2. [21, Theorem 2.1, Theorem 2.2] Let D = [d_{n,k}] be an infinite triangular matrix. Then D is a Riordan array if and only if there exist two sequences A = [a_{0}, a_{1}, a_{2}, …] and Z = [z_{0}, z_{1}, z_{2}, …] with a_{0} ≠ 0, z_{0} ≠ 0 such that

• d_{n+1,k+1} = ∑_{j=0}^{∞} a_{j}d_{n,k+j}, (k, n = 0, 1, …)

• d_{n+1,0} = ∑_{j=0}^{∞} z_{j}d_{n,j}, (n = 0, 1, …).

The coefficients a_{0}, a_{1}, a_{2}, … and z_{0}, z_{1}, z_{2}, … are called the A-sequence and the Zsequence of the Riordan array L = (g(x), f(x)), respectively. Letting A(x) be the generating function of the A-sequence and Z(x) be the generating function of the Z-sequence, we have

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

The first column of P_{L} is then generated by Z(x), while the k-th column is generated by x^{k−1}A(x) (taking the first column to be indexed by 0).

For a given sequence a_{n}, the Hankel transform [26] of a_{n} is the sequence det(a_{i+j})_{0≤i,j≤n}. The Hankel transforms we shall be interested in will all be related to orthogonal polynomials, which in turn will be related to lattice paths [17, 35]. A lattice path [27] is a sequence of vertices in the integer lattice ℤ^{2}. A pair of consecutive vertices is called a step of the path. The height of a step is given by the y-value of the first vertex. A valuation is an integer function on the set of possible steps of ℤ^{2} × ℤ^{2}. A valuation of a path is the product of the valuations of its steps. We concern ourselves with Motzkin paths, k-colored Motzkin paths [4] and Łukasiewicz paths [35], which are defined below. A path of length n begins at (0, 0) and ends at (n, 0). The valuations will be independent of the x-coordinates of the points, therefore the x-coordinates are redundant and we can represent a path π by the sequence of its y-coordinates π = (π(0) ⋯ π(n)).

Definition 3. A path π = (π(0) ⋯ π(n)) is a Motzkin path [27] if it satisfies the following conditions

1. The elementary steps can be north-east, east and south-east.

2. Steps never go below the x axis.

3. π(0) = (0, 0) and π(n) = (n, 0)

If the east steps are labelled by k colors we obtain the k-colored Motzkin paths.

Definition 4. A path π = (π(0) ⋯ π(n)) is a Łukasiewicz path [27] if it satisfies the following conditions

1. The elementary steps can be north - east and east as those in Motzkin paths.

2. In addition south-east steps from level k can fall to any level above or on the x axis, and are denoted as λ_{k,l} and referred to as Łukasiewicz steps, where k is the starting point of the south-east step and l the level where the step ends.

3. Steps never go below the x axis.

Theorem 5. [27, Theorem 2.3] Let

μ_{n} = ∑_{π∈M} v(π)

where the sum is over the set of Motzkin paths π = (π(0) ⋯ π(n)) of length n. Here π(j) is the level after the j^{th} step, and the valuation of a path is the product of the valuations of its steps v(π) = ∏_{i=1}^{n} v_{i} where

v_{i} = v(π(i − 1), π(i)) = \begin{cases}1, & if the i^{th} step rises; \\ β_{π(i−1)}, & if the i^{th} step is horizontal; \\ α_{π(i−1)}, & if the i^{th} step falls. \end{cases}

\begin{matrix}1 \\ level i \\ β_{π(i−1)} \\ α_{π(i−1)} \end{matrix}

Then the g.f. of the sequence μ_{n} is given by

M(x) = ∑_{n=0}^{∞} μ_{n}x^{n}.

A continued fraction expansion of the g.f. is then

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

Now, from [25] we have the following result, Theorem 6. [24, Theorem 11] Let (a_{n})_{n≥0} be a sequence of numbers with g.f. ∑_{n=0}^{∞} a_{n}x^{n} expressible in the form

∑_{n=0}^{∞} a_{n}x^{n} = \frac{a_{0}}{1 − β_{0}x − \frac{α_{1}x^{2}}{1 − β_{1}x − \frac{α_{2}x^{2}}{...}}}.

Then the Hankel determinant det_{0≤i,j≤n−1}(a_{i+j}) is given by

a_{0}^{n}α_{1}^{n−1}α_{2}^{n−2} … α_{n−2}^{2}α_{n−1} = a_{0}^{n} ∏_{k=1}^{n−1} α_{k}^{n−k},

where the sequences {α_{n}}_{n≥1} and {β_{n}}_{n≥0} are the coefficients in the recurrence relation

P_{n}(x) = (x − β_{n})P_{n−1}(x) − α_{n}P_{n−2}(x), n = 1, 2, 3, 4, …

of the family of orthogonal polynomials P_{n} for which a_{n} forms the moment sequence.

3 Generalized Narayana polynomials

The sequence a_{n}(s) = ∑_{k=0}^{n} \binom{2n−k−1}{n−k} \frac{k+0^{n+k}}{n+0^{nk}} s^{k} has generating function [10]

g_{s}(x) = \frac{1}{1 − sxc(x)} = (1, xc(x)) · \frac{1}{1 − sx},

where c(x) = \frac{1−\sqrt{1−4x}}{2x} is the generating function of the Catalan numbers, and (1, xc(x)) is the Riordan array [30] whose k-th column has generating function (xc(x))^{k} [10]. Since c(x) has continued fraction expansion

c(x) = \frac{1}{1 − \frac{x}{1 − \frac{x}{1 − ⋯}}},

the generating function g_{s}(x) has expansion

g_{s}(x) = \frac{1}{1 − \frac{sx}{1 − \frac{x}{1 − \frac{x}{1 − ⋯}}}}.

The matrix with general term

N_{n,k}(s) = ∑_{j=0}^{k} \binom{n}{j}\binom{n − j}{2(k − j)}a_{k−j}(s)

is the generalized Narayana triangle [5] defined by the sequence a_{n}(s), and the polynomials Q_{n}(r, s) thus represent generalized Narayana polynomials. The Narayana triangle \underline{A001263} with general term

\frac{1}{k + 1}\binom{n + 1}{k}\binom{n}{k}

corresponds to s = 1. For s = 2 we get the number triangle with general term \binom{n}{k}^{2} \underline{A008459}.

Proposition 7. The generating function of the polynomials Q_{n}(r, s) = ∑_{k=0}^{n} N_{n,k}(s)r^{k} is given by

g_{Q}(x) = \frac{1}{1 − (r + 1)x − \frac{srx^{2}}{1 − (r + 1)x − \frac{rx^{2}}{1 − (r + 1)x − \frac{rx^{2}}{1 − ⋯}}}}.

Proof. See Theorem 21, [5].

Corollary 8. The Hankel transform of Q_{n}(r, s) is given by

h_{n} = s^{n}r^{\binom{n+1}{2}}.

Proof. This follows from [24, 25].

We know [6] that the Narayana polynomials ∑_{k=0}^{n} \frac{1}{k+1} \binom{n}{k}\binom{n+1}{k}r^{k} can be characterized as being the first column elements of the inverse Riordan array

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

The following proposition generalizes this result, by providing a characterization of the polynomials Q_{n}(r, s) in terms of Riordan arrays.

Proposition 9. The polynomials Q_{n}(r, s) are given by the terms of the first column of the Riordan array

L = (\frac{1 + r(1 − s)x^{2}}{1 + (r + 1)x + rx^{2}} , \frac{x}{1 + (r + 1)x + rx^{2}} )^{−1} .

Proof. We can express g_{Q}(x) in closed form by noticing that

g_{Q}(x) = \frac{1}{1 − (r + 1)x − srx^{2}v} ,

where v is the solution of the equation

v = \frac{1}{1 − (r + 1)x − rx^{2}v} .

(The function v is the generating function of the Narayana triangle). We find that

g_{Q}(x) = \frac{2}{s\sqrt{x^{2}(r − 1)^{2} − 2x(r + 1) + 1} + (x(r + 1) − 1)(s − 2)}.

Standard Riordan array techniques [7] now show that this is equal to the generating

function of the first column of the inverse array (\frac{1+r(1−s)x^{2}}{1+(r+1)x+rx^{2}} , \frac{x}{1+(r+1)x+rx^{2}} )^{−1}.

Note that we can also express g_{Q}(x) as follows.

g_{Q}(x) = \frac{s\sqrt{x^{2}(r − 1)^{2} − 2x(r + 1) + 1} + (2 − s)(x(r + 1) − 1)}{2(x^{2}(r^{2}(s − 1) − r(s^{2} − 2s + 2) + s − 1) + (s − 1)(1 − 2x(r + 1)))}.

We have

L = (g_{Q}(x), \frac{1 − x(r + 1) − \sqrt{1 − 2x(r + 1) + x^{2}(r − 1)^{2}}}{2rx} ) .

Corollary 10. The polynomials Q_{n}(r, s) are the moments of the family of orthogonal polynomials P_{n}(x) that satisfy the recurrence

P_{n}(x) = (x − (r + 1))P_{n−1}(x) − rP_{n−2}(x), n > 2,

P_{0}(x) = 1, P_{1}(x) = x − (r + 1), P_{2}(x) = (x − (r + 1))P_{1}(x) − srP_{0}(x) = x^{2} − 2(r + 1)x + r^{2} + r(2 − s) + 1.

Proof. We need to show [7, 8] that the production matrix [15, 16] of

L = (\frac{1 + r(1 − s)x^{2}}{1 + (r + 1)x + rx^{2}} , \frac{x}{1 + (r + 1)x + rx^{2}} )^{−1}

is tri-diagonal. Standard Riordan array techniques show that this is so, with form

P_{L} = ( \begin{matrix}r + 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ sr & r + 1 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & r & r + 1 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & r & r + 1 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & r & r + 1 & 1 & ⋯ \\ 0 & 0 & 0 & 0 & r & r + 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The three-term recurrence coefficients for P_{n}(x) can be read from P_{L}.

Corollary 11. The Hankel transform of Q_{n}(r, s) is given by

h_{n}(r, s) = s^{n}r^{\binom{n+1}{2}}.

Proof. This is a direct consequence of the form of g_{Q}; equivalently it is derived from the form of the production matrix above.

We note that Q_{n}(r, j/r) is an integer sequence for 0 ≤ j ≤ r −1. For instance, Q_{n}(2, 1/2) is the sequence that begins

1, 3, 10, 36, 138, 558, 2362, 10398, 47326, 221562, …

It has generating function

\frac{1}{1 − 3x − \frac{x^{2}}{1 − 3x − \frac{2x^{2}}{1 − 3x − \frac{2x^{2}}{1 − ⋯}}}}.

This means [9] that Q_{n}(2, 1/2) is the third binomial transform of the aeration of the sequence with generating function

\frac{1}{1 − \frac{x}{1 − \frac{2x}{1 − \frac{2x}{1 − ⋯}}}}.

This latter sequence is the sequence of generalized Catalan numbers C(2; n) \underline{A064062} with g.f.

\frac{1}{1 − xc(2x)}.

Thus the g.f. of Q_{n}(2, 1/2) can be represented as

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

The Hankel transform of Q_{n}(2, 1/2) is given by h_{n}(2, 1/2) = (\frac{1}{2})^{n} 2^{\binom{n+1}{2}} = 2^{\binom{n}{2}}, \underline{A006125}, a sequence with many combinatorial interpretations. One such is that it represents the number of graphs on n labeled nodes.

Similarly the sequence Q_{n}(3, 2/3) which begins

1, 4, 18, 88, 458, 2504, 14244, 83696, 505114, 3116968, …,

with g.f.

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

can be seen to be the fourth binomial transform of the aeration of the sequence with g.f.

\frac{1}{1 − 2xc(3x)}.

The Hankel transform of Q_{n}(3, 2/3) is given by

h_{n}(3, 2/3) = (\frac{2}{3})^{n} 3^{\binom{n+1}{2}},

which begins

1, 2, 12, 216, 11664, 1889568, 918330048, ….

This is \underline{A083667}, the number of antisymmetric binary relations on a set of n labeled points.

We note that in general, we can interpret the continued fraction form of g_{Q}(x) as saying that Q_{n}(r, s) is the (r + 1)-st binomial transform of the aeration of the sequence with g.f.

\frac{1}{1 − srxc(rx)}.

Thus we may express g_{Q}(x) as

g_{Q}(x) = \frac{1}{1 − (r + 1)x} \frac{1}{1 − sr (\frac{x}{1−(r+1)x})^{2} c (r (\frac{x}{1−(r+1)x})^{2})}.

Other interesting sequences are Q_{n}(n, 0) = (n+1)^{n}, or \underline{A000169}, Q_{n}(n, 1) = ∑_{k=0}^{n} \frac{1}{k+1} \binom{n}{k}\binom{n+1}{k}n^{k}, which is \underline{A099169}, and Q_{n}(n, 2) = ∑_{k=0}^{n} \binom{n}{k}^{2}n^{k}, which is \underline{A187021}.

4 Moment representation

We have the following moment representation of Q_{n}(r, s).

Q_{n}(r, s) = \{1, if r = 0; (r + 1)^{n}, if s = 0; ∑_{k=0}^{n} \frac{1}{k+1} \binom{n+1}{k}\binom{n}{k}r^{k} = \frac{1}{2π} ∫_{r+1−2\sqrt{r}}^{r+1+2\sqrt{r}} x^{n}^{\frac{\sqrt{−x^{2}+2x(r+1)−(r−1)^{2}}}{r}} dx, if s = 1, r ≠ 0; \frac{s}{2π} ∫_{r+1−2\sqrt{r}}^{r+1+2\sqrt{r}} x^{n} \frac{\sqrt{−x^{2} + 2x(r + 1) − (r − 1)^{2}}}{1 − s + r(s^{2} − 2s + 2) − r^{2}(s − 1) + 2x(r + 1)(s − 1) − x^{2}(s − 1)} dx+ \frac{s − 2}{2(s − 1)} ((r + 1 − s\sqrt{\frac{r}{s − 1}})^{n} + (r + 1 + s\sqrt{\frac{r}{s − 1}})^{n}) , otherwise.

This density function can be seen as a generalization of the Marčenko-Pastur density [28].

5 A product matrix

The motivation for the work in this section comes from the observation that the Riordan array

(\frac{1 + (c − a)x + (d − b)x^{2}}{1 + ax + bx^{2}} , \frac{x}{1 + ax + bx^{2}} )^{−1}

has production array

( \begin{matrix}c & 1 & 0 & 0 & 0 & 0 & ⋯ \\ d & a & 1 & 0 & 0 & 0 & ⋯ \\ 0 & b & a & 1 & 0 & 0 & ⋯ \\ 0 & 0 & b & a & 1 & 0 & ⋯ \\ 0 & 0 & 0 & b & a & 1 & ⋯ \\ 0 & 0 & 0 & 0 & b & a & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

while the Riordan array given by the product

(\frac{1 + (c − a)x + (d − b)x^{2}}{1 + ax + bx^{2}} , \frac{x}{1 + ax + bx^{2}} )^{−1} · (1, \frac{x}{1 + tx})

has production matrix

( \begin{matrix}c & 1 & 0 & 0 & 0 & 0 & ⋯ \\ d & a − t & 1 & 0 & 0 & 0 & ⋯ \\ dt & b & a − t & 1 & 0 & 0 & ⋯ \\ dt^{2} & bt & b & a − t & 1 & 0 & ⋯ \\ dt^{3} & bt^{2} & bt & b & a − t & 1 & ⋯ \\ dt^{4} & bt^{3} & bt^{2} & bt & b & a − t & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

In other words, we can show that the product matrix has

Z(x) = \frac{c − (ct − d)x}{1 − tx}, A(x) = \frac{1 − (2t − a)x − (at − b − t^{2})x^{2}}{1 − tx} .

It is possible to display Q_{n}(r, s) as the first column of a Riordan array in many ways. The Riordan array in the last section was chosen because its inverse is the coefficient array of the associated family of orthogonal polynomials. Another interesting Riordan array is the array

L̃ = ((1, \frac{x}{1 − x}) · (\frac{1 + r(1 − s)x^{2}}{1 + (r + 1)x + rx^{2}} , \frac{x}{1 + (r + 1)x + rx^{2}} ))^{−1}
= (\frac{1 − 2x − (r(s − 1) − 1)x^{2}}{1 + (r − 1)x} , \frac{x(1 − x)}{1 + (r − 1)x})^{−1}
= (\frac{1 + r(1 − s)x^{2}}{1 + (r + 1)x + rx^{2}} , \frac{x}{1 + (r + 1)x + rx^{2}} )^{−1} · (1, \frac{x}{1 + x})
= L · (1, \frac{x}{1 + x}) .

We have

L̃ = (g_{Q}(x), \frac{1 − x(r − 1) − \sqrt{1 − 2x(r + 1) + x^{2}(r − 1)^{2}}}{2} ) .

The matrix L̃ then has the production matrix

PL̃ = ( \begin{matrix}r + 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ rs & r & 1 & 0 & 0 & 0 & ⋯ \\ rs & r & r & 1 & 0 & 0 & ⋯ \\ rs & r & r & r & 1 & 0 & ⋯ \\ rs & r & r & r & r & 1 & ⋯ \\ rs & r & r & r & r & r & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

Such production matrices are linked to Łukasiewicz paths [22]. Example 12. We take the case r = 2, s = \frac{1}{2}. In this case we obtain the production matrix

PL̃ = ( \begin{matrix}3 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 2 & 1 & 0 & 0 & ⋯ \\ 1 & 2 & 2 & 2 & 1 & 0 & ⋯ \\ 1 & 2 & 2 & 2 & 2 & 1 & ⋯ \\ 1 & 2 & 2 & 2 & 2 & 2 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The associated Riordan array is

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

This matrix begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ 3 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 10 & 5 & 1 & 0 & 0 & 0 & ⋯ \\ 36 & 22 & 7 & 1 & 0 & 0 & ⋯ \\ 138 & 96 & 38 & 9 & 1 & 0 & ⋯ \\ 588 & 426 & 192 & 58 & 11 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

and has row sums u_{n} that begin

1, 4, 16, 66, 282, 1246, 5674, 26530, 126910, 619086, …,

with g.f.

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

We have the moment representation

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

Note also that the first column sequence 1, 3, 10, 36, … has the moment representation

u_{n} = \frac{1}{2π} ∫_{3−2\sqrt{2}}^{3+2\sqrt{2}} x^{n} \frac{\sqrt{−x^{2} + 6x − 1}}{x^{2} − 6x + 10} dx.

The Hankel transform of the row sum sequence u_{n} is equal to

2^{\binom{n}{2}}[x^{n}]\frac{1 − x}{1 − x + 2x^{2}} .

In general, the rows sums of L̃ can be shown to have Hankel transform

r^{\binom{n}{2}}[x^{n}]\frac{1 − x}{1 − rsx + rx^{2}} .

Example 13. We consider the case r = 1, s = 3. Then

L̃ = (1 − 2x − x^{2}, x(1 − x))^{−1} = (\frac{1}{1 − 2xc(x) − x^{2}c(x)^{2}} , xc(x)) .

The row sums u_{n} of L̃ have g.f.

\frac{1}{(1 − 2xc(x) − x^{2}c(x)^{2})(1 − xc(x))} = \frac{1 − 5x − (1 + x)\sqrt{1 − 4x}}{2x(x^{2} + 8x − 2)}.

We have the moment representation

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

The Hankel transform of the row sums is equal to

[x^{n}]\frac{1 − x}{1 − 3x + x^{2}} ,

or F_{2n+1}. The row sum sequence is \underline{A143464}, which begins

1, 3, 11, 42, 164, 649, 2591, 10408, ….

We can also look at sequences with negative values of r and s. For instance, the sequence Q_{n}(−1, −1) is associated with the production matrix

PL̃ = ( \begin{matrix}0 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & −1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & −1 & −1 & 1 & 0 & 0 & ⋯ \\ 1 & −1 & −1 & −1 & 1 & 0 & ⋯ \\ 1 & −1 & −1 & −1 & −1 & 1 & ⋯ \\ 1 & −1 & −1 & −1 & −1 & −1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The sequence Q_{n}(−1, −1) begins

1, 0, 1, 0, 0, 0, 1, 0, −2, 0, 6, 0, −18, 0, 57, 0, −186, 0, 622, …,

and represents the aeration of C(−1; n) \underline{A064310}. The sequence Q_{n}(−1, −1) has Hankel transform equal to (−1)^{n}.

Example 14. The case r = −1, s = 1 is also linked to the Fibonacci numbers. For this, we find that the row sums are

1, 1, −1, −2, 2, 5, −5, −14, 14, 42, −42, −132, 132, 429, …,

a sequence of signed doubled Catalan numbers. The Hankel transform in this case is (−1)^{\binom{n+1}{2}}F_{n+2}.

Example 15. Similarly, the case r = −1, s = −1 is also linked to the Fibonacci numbers. The row sums are given by

1, 1, 1, 0, 0, 1, 1, −2, −2, 6, 6, −18, −18, 57, 57, −186, −186, 622, …,

a sequence of signed doubled generalized Catalan numbers C(−1; n) (\underline{A064310}), given by C(−1; ⌊\frac{n+1}{2}⌋). The Hankel transform in this case is

1, 0, −1, −1, 2, 3, −5, −8, 13, 21, −34, …,

or (−1)^{\binom{n}{2}}F_{n−1}. The matrix in question is

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

6 A series reversion

It is interesting to study the reversion of xg_{Q}(x), that is, to study the appropriate solution of the equation

ug_{Q}(u) = x.

We obtain

\frac{u(x)}{x} = \frac{s\sqrt{4rx^{2}(s − 1) + 1} + 2x(1 − s)(r + 1) − s + 2}{2(1 − x(r + 1)(s − 2) + (1 − s + r(s^{2} − 2s + 2) − r^{2}(s − 1))x^{2})}.

This again is the generating function of a sequence of polynomials in r and s, which begins

1, −(r+1), r^{2}+r(2−s)+1, −r^{3}+r^{2}(2s−3)+r(2s−3)−1, r^{4}+r^{3}(4−3s)+r^{2}(2s^{2}−7s+6)+r(4−3s)+1, …

As polynomials in the variable r, these polynomials have coefficient array given by

N̄(s) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & ⋯ \\ −1 & −1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 2 − s & 1 & 0 & 0 & 0 & ⋯ \\ −1 & 2s − 3 & 2s − 3 & −1 & 0 & 0 & ⋯ \\ 1 & 4 − 3s & 2s^{2} − 7s + 6 & 4 − 3s & 1 & 0 & ⋯ \\ −1 & 4s − 5 & 2(7s − 5) − 5s^{2} & 2(7s − 5) − 5s^{2} & 4s − 5 & −1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

which apart from signs, is also Pascal-like. Examples for s = 0, …, 5 of these matrices N̄(s) are given at the end of the last section. The central coefficients M(s)

1, 2 − s, 2s^{2} − 7s + 6, −5s^{3} + 24s^{2} − 38s + 20, 14s^{4} − 84s^{3} + 188s^{2} − 187s + 70, …

of this triangle are of interest. As polynomials in s, they can be expressed as

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

The g.f. of M(s) is given by

g_{M}(s) = \frac{1}{1 + (s − 2)xc((1 − s)x)} = \frac{s − (s − 2)\sqrt{1 − (1 − s)4x}}{2(1 − (s − 2)^{2}x)}.

They are the moments of the family of orthogonal polynomials R_{n}(x) defined by

R_{n}(x) = (x − 2(1 − s))R_{n−1}(x) − (s − 1)^{2}R_{n−2}(x), n > 2,

with R_{0}(x) = 1, R_{1}(x) = x − (s − 2) and R_{2}(x) = x^{2} + x(3s − 4) + (s − 1)(s − 2). The coefficient array of this family of polynomials is given by the Riordan array

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

The moments M(s) are then the elements of the first column of the inverse of this array. They can be represented as

M_{n}(s) = \frac{1}{π} ∫_{4(1−s)}^{0} x^{n} \frac{(s − 2)\sqrt{x(4(1 − s) − x)}}{2x(x − s^{2} − 4(1 − s))} dx

for s ≠ 1, 2. The Hankel transform of M_{n}(s) is given by

h_{n}(s) = (s − 2)^{n}(s − 1)^{n^{2}}.

7 A bijection between paths related to P_{L} and PL̃

Returning to the production matrix introduced above,

P_{L} = ( \begin{matrix}r + 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ sr & r + 1 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & r & r + 1 & 1 & 0 & 0 & ⋯ \\ 0 & 0 & r & r + 1 & 1 & 0 & ⋯ \\ 0 & 0 & 0 & r & r + 1 & 1 & ⋯ \\ 0 & 0 & 0 & 0 & r & r + 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) ,

we are now interested in these matrix entries and their corresponding Motzkin paths. It is known [17, 22, 35] that the elements of the first column of the Riordan array corresponding to P_{L} count Motzkin paths returning to the x axis. Motzkin paths related to the matrix P_{L} above are referred to as (r+1)-colored Motzkin paths, where we have a choice of (r+1) colors for each east step. Similarly, each south-east step has a choice of r colors. We note that for the matrix above, the south-east step returning to the x axis has a choice of rs colors. For this reason, we will refer to such Motzkin weighted paths as (s-e_{x−axis}, e_{x−axis}; s-e, e)-Motzkin paths. Thus, P_{L} corresponds to a (rs, r +1; r, r +1)-Motzkin path. Similarly, it can be shown [22] that the first column of the Riordan array corresponding to the production matrix

PL̃ = ( \begin{matrix}r + 1 & 1 & 0 & 0 & 0 & 0 & ⋯ \\ rs & r & 1 & 0 & 0 & 0 & ⋯ \\ rs & r & r & 1 & 0 & 0 & ⋯ \\ rs & r & r & r & 1 & 0 & ⋯ \\ rs & r & r & r & r & 1 & ⋯ \\ rs & r & r & r & r & r & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

counts Łukasiewicz paths returning to the x axis. Adopting similar notation as for the Motzkin paths above, PL̃ corresponds with a (rs, r + 1; r, r)-Łukasiewicz path. Now, as the first column of the Riordan arrays corresponding to P_{L} and PL̃ both have generating function g_{Q}(x), we introduce the following bijection between Motzkin and Łukasiewicz paths.

Proposition 16. A bijection exists between the set of (rs, r + 1; r, r + 1)-Motzkin paths of length n and the set of (rs, r + 1; r, r)-Łukasiewicz paths of length n, for any n > 0.

We choose an ordering of colors of the east steps. In the proof below we refer to the east steps that are colored with the (r + 1)-th color as e_{r+1}

Proof. We construct a map ϕ : 𝕄 → 𝕃. Given a (rs, r + 1; r, r + 1)-Motzkin path P of length n, we can obtain a path ϕ(P) as follows:

• i-colored east steps remain unchanged, for i < r + 1.

• East steps e_{r+1}, become Łukasiewicz steps, taking the color of its associated north-east, south-east pair.

Conversely, given a (rs, r+1; r, r)-Łukasiewicz path we can obtain a (rs, r+1; r, r+1)-Motzkin path by

• i-colored east steps remain unchanged, for i < r + 1.

• Łukasiewicz steps form the (r + 1)^{th} colored east steps, e_{r+1}.

y axis (r + 1)rs rs r^{2}s (r + 1)r rr^{2}

We illustrate the Łukasiewicz path formed from the mapping ϕ, for a Motzkin path with all east steps e_{r+1}. We see that each north-east step is paired with its right horizontally visible south-east step. All east steps at the height of the south-east step belong to that north-east, south-east pair. For a north-east, south-east pair, with m level steps, at height (y + 1), the Łukasiewicz path becomes a north-east path of (m + 1) steps with a Łukasiewicz step λ_{(y+m+1,y)}. The Łukasiewicz step now takes the choice of colors of the original south-east step. North-east, south-east pairs with no east steps remain unchanged. We note that it is clear from above that the length is preserved.

Conversely, beginning with the Łukasiewicz path above, again we pair north-east steps with their right horizontally visible step, be that a south-east or Łukasiewicz step. The north-east step, whose left vertex corresponds to the right vertex of a Łukasiewicz step, remains a north-east step. All other north-east steps who are right horizontally paired with a Łukasiewicz step, form level steps colored e_{r+1}. North-east steps corresponding to right horizontally visible south-east steps remain unchanged, as do south-east steps.

Again, looking at the path above, the Łukasiewicz path corresponds to the Motzkin path with all east steps e_{r+1}. Considering all possible colorings of the Motzkin path, we have (r+1)^{9}r^{2}rs Motzkin paths. Now, from ϕ, counting all corresponding Łukasiewicz paths, with a choice of nine level steps and e_{r+1} forming Łukasiewicz steps, gives ∑_{i=0}^{9} \binom{9}{i}r^{i}r^{2}rs paths. For any path, considering a choice of all (r + 1) colors for m east steps at level y, belonging to a north-east, south-east step pair(not returning to the x axis) we have (r + 1)^{m}r. Now, (r + 1)^{m}r = ∑_{j=0}^{m} \binom{m}{j}r^{j}r which counts all combinations of Łukasiewicz paths with i-colored east steps, i < r+1. (We note that for any m level steps belonging to a south-east step which returns to the x-axis, we have (r + 1)^{m}rs = ∑_{j=1}^{m} \binom{m}{j}r^{j}rs which counts all combinations of Łukasiewicz paths with east steps with a choice of r colors.)

Example 17. For r, s = 1 we have the (1, 2; 1, 2)-Motzkin paths and the (1, 2; 1, 1)-Łukasiewicz paths, both counted by the shortened Catalan numbers \underline{A000108}. Let us look at the paths corresponding to one such Motzkin path of length n = 8, letting the level step colors be red and yellow, and choosing yellow to be e_{2}. As the Łukasiewicz steps retain the same colors as the north-east steps, we will only show the colorings of the level steps.

8 Examples

The table below lists the first six generalized Narayana triangles, in the sense of this article. For s = 0, we have the usual Pascal’s triangle, \underline{A007318}. For s = 1, we have the Narayana triangle \underline{A001263}, while for s = 2 we have \underline{A008459}, which has general term \binom{n}{k}^{2}.

\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 & 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 1 15 50 50 15 1 & 1 0 0 0 0 0 1 1 0 0 0 0 1 4 1 0 0 0 1 9 9 1 0 0 1 16 36 16 1 0 1 25 100 100 25 1 \\ s = 0 & s = 1 & s = 2 \\ 1 0 0 0 0 0 1 1 0 0 0 0 1 5 1 0 0 0 1 12 12 1 0 0 1 22 54 22 1 0 1 35 160 160 35 1 & 1 0 0 0 0 0 1 1 0 0 0 0 1 6 1 0 0 0 1 15 15 1 0 0 1 28 74 28 1 0 1 45 230 230 45 1 & 1 0 0 0 0 0 1 1 0 0 0 0 1 7 1 0 0 0 1 18 18 1 0 0 1 34 96 34 1 0 1 55 310 310 55 1 \\ s = 3 & s = 4 & s = 5 \end{matrix}

The next table lists some examples of the sequences Q_{n}(r, s) for the values of r and s shown.

(r, s)  Q_{n}(r, s)  OEIS number
(0,1)  1, 1, 1, 1, 1, 1, …  \underline{A000012}
(1,1)  1, 2, 5, 14, 42, 132, …  \underline{A000108}(n + 1)
(2,1)  1, 3, 11, 45, 197, 903, … \underline{A001003}(n + 1)
(3,1) 1, 4, 19, 100, 562, 3304, … \underline{A007564}(n + 1)
(4,1) 1, 5, 29, 185, 1257, 8925, … \underline{A059231}(n + 1)
(0,2)  1, 1, 1, 1, 1, 1, …  \underline{A000012}
(1,2)  1, 2, 6, 20, 70, 252, …  \underline{A000984}
(2,2) 1, 3, 13, 63, 321, 1683, …  \underline{A001850}
(3,2) 1, 4, 22, 136, 886, 5944, …  \underline{A069835}
(4,2) 1, 5, 33, 245, 1921, 15525, …  \underline{A084771}
(1,3)  1, 2, 7, 26, 100, 392, …  \underline{A101850}
(1,4)  1, 2, 8, 32, 132, 552, …  \underline{A155084}

Finally, we document the start of the matrices N̄(s) for s = 0, …, 5.

\begin{matrix}\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} & \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ −1 & −1 & −1 & −1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 \\ −1 & −1 & −1 & −1 & −1 & −1 \end{matrix} \\ s = 0 & s = 1 \\ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ −1 & 1 & 1 & −1 & 0 & 0 \\ 1 & −2 & 0 & −2 & 1 & 0 \\ −1 & 3 & −2 & −2 & 3 & −1 \end{matrix} & \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & 0 & 0 & 0 & 0 \\ 1 & −1 & 1 & 0 & 0 & 0 \\ −1 & 3 & 3 & −1 & 0 & 0 \\ 1 & −5 & 3 & −5 & 1 & 0 \\ −1 & 7 & −13 & −13 & 7 & −1 \end{matrix} \\ s = 2 & s = 3 \\ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & 0 & 0 & 0 & 0 \\ 1 & −2 & 1 & 0 & 0 & 0 \\ −1 & 5 & 5 & −1 & 0 & 0 \\ 1 & −8 & 10 & −8 & 1 & 0 \\ −1 & 11 & −34 & −34 & 11 & −1 \end{matrix} & \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ −1 & −1 & 0 & 0 & 0 & 0 \\ 1 & −3 & 1 & 0 & 0 & 0 \\ −1 & 7 & 7 & −1 & 0 & 0 \\ 1 & −11 & 21 & −11 & 1 & 0 \\ −1 & 15 & −65 & −65 & 15 & −1 \end{matrix} \\ s = 4 & s = 5 \end{matrix}

9 Acknowledgements

The author would like to thank an anonymous referee for their informative remarks and bibliographical additions.

References

[1] R. Askey and M. E. H. Ismail, A generalization of ultraspherical polynomials, in P. Erdös, ed., Studies in Pure Mathematics. To the Memory of Paul Turán, Birkhäuser, 1983, pp. 55–78.

[2] R. Askey and M. E. H. Ismail, Recurrence Relations, Continued Fractions and Orthogonal Polynomials, Memoirs of the Amer. Math. Soc. 300, AMS, 1984.

[3] M. Anshelevich, Free martingale polynomials, J. Funct. Anal. 201 (2003), 228–261.

[4] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, A construction for enumerating k-coloured Motzkin paths, Lecture Notes in Comput. Sci., 959, (1995), 254–263.

[5] P. Barry, On a generalization of the Narayana triangle, J. Integer Seq., 14 (2011), Article 11.4.5.

[6] P. Barry and A. Hennessy, A note on Narayana triangles and related polynomials, Riordan arrays and MIMO capacity calculations, J. Integer Seq., 14 (2011), Article 11.3.8.

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

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

[9] P. Barry, Continued fractions and transformations of integer sequence, J. Integer Seq., 12 (2010), Article 09.7.6.

[10] P. Barry, A Catalan transform and related transformations on integer sequences, J. of Integer Seq., 8 (2005), Article 05.4.5.

[11] M. Bożejko and W. Bryc, On a class of free Lévy laws related to a regression problem, J. Funct. Anal. 236 (2006), 59–77.

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

[13] J. M. Cohen and A. R. Trenholme, Orthogonal polynomials with constant recursion formula and an application to harmonic analysis, J. Funct. Anal. 59 (1984), 175–184.

[14] B. Collins, Product of random projections, Jacobi ensembles and universality problems arising from free probability, Probab. Theory Related Fields 133 (2005), 315–344.

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

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

[17] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math., 32 (1980), 125–161.

[18] J. Geronimus, On a set of polynomials, Ann. of Math. 31 (1930), 681–686.

[19] I. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison–Wesley, 1995.

[20] F. A. Grünbaum, Random walks and orthogonal polynomials: some challenges, in M. Pinsky, B. Birner, eds., Probability, Geometry and Integrable Systems MSRI publications 55 CUP 2008, 241–260.

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

[22] A. Hennessy, A study of Riordan arrays with applications to continued fractions, orthogonal polynomials and lattice paths, PhD Thesis, Waterford Institute of Technology, 2011.

[23] S. Karlin and J. L. McGregor, The differential equations of birth-and-death processes, and the Stieltjes moment problem, Trans. Amer. Math. Soc. 85 (1957), 489–546.

[24] C. Krattenthaler, Advanced determinant calculus, Séminaire Lotharingien Combin. 42 (1999), Article B42q., available electronically at

    http://arxiv.org/abs/math/9902004, 2012.

[25] C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 68–166.

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

[27] Franz Lehner, Cumulants, lattice paths and orthogonal polynomials,Discrete Math., 270 (2003), 177–191.

[28] V. A. Marčenko and L. A. Pastur, Distribution of eigenvalues in certain sets of random matrices, Math. USSR Sb. 1 (1967), 457–483.

[29] N. Saitoh and H. Yoshida, The infinite divisibility and orthogonal polynomials with a constant recursion formula in free probability theory, Probab. Math. Statist. 21 (2001), 159–170.

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

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

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

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

[34] G. Szegö, Orthogonal Polynomials, 4th ed., American Mathematical Society, 1975.

[35] X. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, lecture notes, UQAM, 1983.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 15B36, 42C05, 11C20, 15B05.

Keywords: Narayana polynomial, Riordan array, production matrix, orthogonal polynomial, Hankel transform.

(Concerned with sequences \underline{A000007}, \underline{A000012}, \underline{A000045}, \underline{A000108}, \underline{A000169}, \underline{A000984}, \underline{A001003}, \underline{A001263}, \underline{A001850}, \underline{A006125}, \underline{A007318}, \underline{A007564}, \underline{A008459}, \underline{A059231}, \underline{A064062}, \underline{A064310}, \underline{A069835}, \underline{A083667}, \underline{A084771}, \underline{A099169}, \underline{A101850}, \underline{A143464}, \underline{A155084}, \underline{A187021}.)

Received November 9 2011; revised version received April 17 2012. Published in Journal of Integer Sequences, April 20 2012.

Return to Journal of Integer Sequences home page.