On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences

Paul Barry School of Science South East Technological University Ireland

                         pbarry@wit.ie

Abstract Building on work by Yang and Gao, we explore links between the enumeration of lattice paths with steps (1, 1), (1, −1), (1, 0) and (2, 0), Riordan arrays, continued fractions and a conjectured link to Somos-4 sequences. The study gives insights into the Pascal rhombus and its Riordan array generalizations. We rely on the A-matrix definition of Riordan arrays first defined by Merlini, Rogers, Sprugnoli, and Verri for many of our results.

1 Introduction

By a Motzkin-Schröder path we shall understand a lattice path, going from (0, 0) to (n, 0) using four types of step, U = (1, 1), D = (1, −1), h = (1, 0) and H = (2, 0), that does not go below the axis y = 0 (see Figure 1). Such paths have been called 2-Motzkin paths, but this term has been also used to describe Motzkin paths with two types of horizontal h steps [3, 4]. These paths have also been called 2-generalized Motzkin paths [12]. To avoid confusion, we use the term Motzkin-Schröder path in this note. A Motzkin-Schröder path with no H-steps is an ordinary Motzkin path, while a Motzkin-Schröder path of length 2n with no h-steps is an ordinary Schröder path. Lattice paths in the positive quadrant from (0, 0) to (n, 0) with only the steps (1, 1) and (1, −1) are called Dyck paths of length n.

Known sequences will be referred to by their On-Line Encyclopedia of Integer Sequences (OEIS) numbers [13, 16]. All number triangles in this note are of infinite extent; we show suitable truncations in relevant cases.

Dyck paths of length n are enumerated by the Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} \underline{A000108}, governed by the recurrence

C_{n} = ∑_{i=0}^{n−1} C_{i}C_{n−i−1}, C_{0} = 1.

Motzkin paths of length n are enumerated by the Motzkin numbers M_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k} \underline{A001006}, governed by the recurrence

M_{n} = M_{n−1} + ∑_{i=0}^{n−2} M_{i}M_{n−2−i}, M_{0} = 1, M_{1} = 1.

Schröder paths of length 2n are enumerated by the large Schröder numbers S_{n} = ∑_{k=0}^{n} \binom{n+k}{2k}C_{k} \underline{A06318}, governed by the recurrence

S_{n} = 3S_{n−1} + ∑_{i=1}^{n−2} S_{i}S_{n−i−1}, S_{0} = 1, S_{1} = 2.

Proposition 1. The number A_{n} = A_{n}(r, s, t) of Motzkin-Schröder paths of length n where the horizontal steps h can be of r colors, the horizontal steps H can be of s colors and the up steps (1, 1) can be of t colours is given by the following recurrence

A_{n} = rA_{n−1} + sA_{n−2} + t ∑_{i=0}^{n−2} A_{i}A_{n−2−i}, A_{0} = 1, A_{1} = r.  (1)

Proof. The first term on the right covers the case where the path, which ends at (n, 0), has a final h step. The second term covers the case where the path ends with a final H step. This leaves the case where the path ends with a final down (1, −1) step. Thus at some stage there was an up-step from the line y = 0, which accounts for the multiplier t, and this up step factors the part of the path from level 1 up into two paths of length i and n − 2 − i.

We have for instance, the following instances of A_{n}(r, s, t) (where “aerated” signifies a sequence whose odd-indexed terms are 0. Such a sequence will have a generating function with only even powers of x).

A_{n}(r, s, t)  sequence  OEIS
A_{n}(1, 1, 1) 1, 1, 3, 6, 16, 40, …  \underline{A128720}
A_{n}(1, 0, 0) 1, 1, 1, 1, 1, 1, …  \underline{A000012}
A_{n}(0, 1, 0) 1, 0, 1, 0, 1, 0, …  \underline{A059841}
A_{n}(0, 0, 1) 1, 0, 1, 0, 2, 0, … \underline{A000108} aerated
A_{n}(1, 1, 0) 1, 1, 2, 3, 5, 8, …  \underline{A000045}
A_{n}(1, 0, 1) 1, 1, 2, 4, 9, 21, …  \underline{A001006}
A_{n}(0, 1, 1) 1, 0, 2, 0, 6, 0, … \underline{A006318} aerated
A_{n}(1, 0, 2) 1, 1, 3, 7, 21, 61, … \underline{A025235}
A_{n}(0, 1, 2) 1, 0, 3, 0, 15, 0, … \underline{A103210} aerated
A_{n}(1, 1, 2) 1, 1, 4, 9, 31, 92, …  − − −

Figure 1: Motzkin-Schröder paths for n = 0, 1, 2, 3

2 Generating functions, continued fractions and Riordan arrays

By translating the recurrence (1) into an equation for the generating function, we obtain the following proposition.

Proposition 2. Let g(x) = g(x; r, s, t) = ∑_{n=0}^{∞} A_{n}(r, s, t)x^{n}. Then we have

• g(x) = \frac{1}{1−rx−sx^{2}} c (\frac{tx^{2}}{(1−rx−sx^{2})^{2}} ), where c(x) = \frac{1−\sqrt{1−4x}}{2x} is the generating function of the Catalan numbers,

• g(x) = \frac{1}{1−(r−\sqrt{t})x−sx^{2}} m (\frac{\sqrt{t}x}{1−(r−\sqrt{t})x−sx^{2}} ), where m(x) is the generating function of the Motzkin numbers.

Before proving this result, we recall some results about Riordan arrays [1, 14, 15]. A Riordan array can be defined by a pair of power series g(x), f(x) where

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

where g_{0} ≠ 0, and

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

where f_{0} = 0 and f_{1} ≠ 0. Such pairs (g(x), f(x)) then constitute a group for the product

(g(x), f(x)) · (u(x), v(x)) = (g(x)u(f(x)), v(f(x))).

The pair (g(x), f(x)) acts on a power series h(x) by weighted composition as follows.

(g(x), f(x)) · h(x) = g(x)h(f(x)).

This operation is generally referred to as the fundamental theorem of Riordan arrays. The pair of power series (g(x), f(x)) has a matrix representation given by the matrix (t_{n,k})_{0≤i,j≤∞} where

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

Here, [x^{n}] is the linear functional that extracts the coefficient of x^{n} in the power series. The matrix (t_{n,k}) is then the Riordan array representing the Riordan group element (g(x), f(x)). By an abuse of language, we often refer to the pair (g(x), f(x)) as a Riordan array. By construction, Riordan arrays are invertible lower-triangular matrices, and the group product above translates into matrix multiplication in the matrix representation.

Riordan arrays have several sequence characterizations. For instance, (t_{n,k}) is a Riordan array if and only if we can express t_{n+1,k+1} as a (fixed) linear combination of the elements in the row above it and starting with t_{n,k}. The coefficients of this linear combination constitute what is referred to as the A sequence of the array. An alternative A matrix characterization exists, and we shall see some examples of this later in this note.

Proof. The generating function g(x) satisfies the equation

g(x) = 1 + rxg(x) + sx^{2}g(x) + tx^{2}g(x)^{2}.

Solving this equation for g(x), we find that

g(x) = \frac{1 − rx − sx^{2} − \sqrt{(1 − rx − sx^{2})^{2} − 4tx^{2}}}{2tx^{2}} .

With c(x) = \frac{1−\sqrt{1−4x}}{2x}, this last expression is then equal to

\frac{1}{1 − rx − sx^{2}} c (\frac{tx^{2}}{(1 − rx − sx^{2})^{2}} ) .

Similarly, with

m(x) = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}}

we can verify that

g(x) = \frac{1}{1 − (r − \sqrt{t})x − sx^{2}} m (\frac{\sqrt{t}x}{1 − (r − \sqrt{t})x − sx^{2}} ) .

Corollary 3. The generating function g(x; r, s, t) is the result of operating on the generating function of the Motzkin numbers m(x) by the Riordan array

(\frac{1}{1 − (r − \sqrt{t})x − sx^{2}} , \frac{\sqrt{t}x}{1 − (r − \sqrt{t})x − sx^{2}} ) .

Proof. This follows from the proposition and the fundamental theorem of Riordan arrays [15], which takes the form (u(x), v(x)) · g(x) = u(x)g(v(x)).

Corollary 4. The generating function g(x; r, s, t) is the result of operating on the generating function of the Catalan numbers c(x) by the stretched Riordan array

(\frac{1}{1 − rx − sx^{2}} , \frac{tx^{2}}{(1 − rx − sx^{2})^{2}} ) .

Corollary 5. We have

A_{n}(r, s, t) = ∑_{k=0}^{n} ∑_{j=0}^{n−2k} \binom{2k + j}{j}\binom{j}{n − 2k − j}s^{n−2k−j}r^{2(k+j)−n}t^{k}C_{k}.

The generating function c(x) of the Catalan numbers can be expressed as the following Stieltjes-type continued fraction [17].

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

Operating on this by the stretched Riordan array (\frac{1}{1−rx−sx^{2}} , \frac{tx^{2}}{(1−rx−sx^{2})^{2}} ) and simplifying, gives us the following result.

Proposition 6. We let g(x; r, s, t) be the generating function of generalized Motzkin-Schröder lattice paths where the h steps have r colors, the H steps have s colors and the up steps have t colors. Then we have

g(x) = \frac{1}{1 − rx − sx^{2} − \frac{tx^{2}}{1 − rx − sx^{2} − \frac{tx^{2}}{1 − rx − ⋯}}}.

Proof. Solving the equation

u = \frac{1}{1 − rx − sx^{2} − tx^{2}u}

gives u(x) = g(x).

3 Number triangles

We express

g(x; r, s, t) = \frac{1 − rx − sx^{2} − \sqrt{1 − 2rx + (r^{2} − 2s − 4t)x^{2} + 2rsx^{3} + s^{2}x^{4}}}{2tx^{2}}

= \frac{1 − rx − sx^{2} − \sqrt{(1 − rx − sx^{2})^{2} − 4tx^{2}}}{2tx^{2}}

as

g(x; r, s, t) = ∑_{n=0}^{∞} ∑_{k=0}^{∞} T_{n,k}(s, t)r^{k}x^{n}.

Then the matrix (T_{n,k}(s, t)) begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ s + t & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 2s + 3t & 0 & 1 & 0 & 0 & 0 \\ (s + t)(s + 2t) & 0 & 3(s + 2t) & 0 & 1 & 0 & 0 \\ 0 & 3s^{2} + 12ts + 10t^{2} & 0 & 2(2s + 5t) & 0 & 1 & 0 \\ (s + t) (s^{2} + 5ts + 5t^{2}) & 0 & 6 (s^{2} + 5ts + 5t^{2}) & 0 & 5(s + 3t) & 0 & 1 \end{matrix} ) .

For instance, when s = t = 1, the row sums of this triangle (corresponding to r = 1), give the numbers of Motzkin-Schröder paths of length n 1, 1, 3, 6, 16, 40, . . .. Thus we have

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 5 & 0 & 1 & 0 & 0 & 0 \\ 6 & 0 & 9 & 0 & 1 & 0 & 0 \\ 0 & 25 & 0 & 14 & 0 & 1 & 0 \\ 22 & 0 & 66 & 0 & 20 & 0 & 1 \end{matrix} ) · ( \begin{matrix}1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix} ) = ( \begin{matrix}1 \\ 1 \\ 3 \\ 6 \\ 16 \\ 40 \\ 109 \end{matrix} ) .

This triangle is \underline{A132277}.

The first column of the matrix (T_{n,k}(s, t)) has its generating function given by g(x; 0, s, t), or

g(x; 0, s, t) = \frac{1 − sx^{2} − \sqrt{(1 − sx^{2}) − 4tx^{2}}}{2tx^{2}} .

This expands to give the aerated sequence

1, 0, s + t, 0, s^{2} + 3st + 2t^{2}, 0, s^{3} + 6s^{2}t + 10st^{2} + 5t^{3}, 0, ….

When s = t = 1, this gives the aerated large Schröder numbers 1, 0, 2, 0, 6, 0, 22, 0, . . .. We have the following related continued fraction.

Proposition 7. The generating function g(\sqrt{x}; 0, s, t) can be expressed as the following Thron-type continued fraction [9]

g(\sqrt{x}; 0, s, t) = \frac{1}{1 − sx − \frac{tx}{1 − sx − \frac{tx}{1 − sx − ⋯}}}.

Proof. Solving the equation u = \frac{1}{1−sx−txu} yields

u(x) = \frac{1 − sx − \sqrt{1 − 2(s + 2t)x + s^{2}x^{2}}}{2tx} = g(\sqrt{x}; 0, s, t).

Thus g(\sqrt{x}; 0, s, t) is the generating function of Schröder paths whose level steps have s colors and whose up steps have t colors. The generating function g(\sqrt{x}; 0, s, t) expands to give the sequence that begins

1, s + t, s^{2} + 3st + 2t^{2}, s^{3} + 6s^{2}t + 10st^{2} + 5t^{3}, ….

In matrix terms, this gives us, for instance

( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ t & 1 & 0 & 0 & 0 \\ 2t^{2} & 3t & 1 & 0 & 0 \\ 5t^{3} & 10t^{2} & 6t & 1 & 0 \\ 14t^{4} & 35t^{3} & 30t^{2} & 10t & 1 \end{matrix} ) ( \begin{matrix}1 \\ s \\ s^{2} \\ s^{3} \\ s^{4} \end{matrix} ) = ( \begin{matrix}1 \\ s + t \\ s^{2} + 3st + 2t^{2} \\ s^{3} + 6s^{2}t + 10st^{2} + 5t^{3} \\ ⋯ \end{matrix} ) .

The matrix that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 & 0 \\ 5 & 10 & 6 & 1 & 0 & 0 & 0 \\ 14 & 35 & 30 & 10 & 1 & 0 & 0 \\ 42 & 126 & 140 & 70 & 15 & 1 & 0 \\ 132 & 462 & 630 & 420 & 140 & 21 & 1 \end{matrix} )

is \underline{A060693}, whose (n, k)-th element counts the number of Schröder paths from (0, 0) to (2n, 0) having k peaks.

4 Hankel transform

The Hankel transform h_{n}(r, s, t) of A_{n}(r, s, t), given by h_{n} = |A_{i+j}(r, s, t)|_{0≤i,j≤n}, begins

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

We have the following conjecture [2].

Conjecture 8. Let A_{n}(r, s, t) be the sequence giving the number of Motzkin-Schröder paths whose h steps have r colors, whose H steps have s colors, and whose up steps have t colors. Then the Hankel transform h_{n}(r, s, t) of A_{n}(r, s, t) is a ((rt)^{2}, t^{2}((s + t)^{2} − r^{2}t)) Somos-4 sequence.

Here, by an (α, β) Somos-4 sequence we mean a sequence s_{n} [6] such that

αs_{n−1}s_{n−3} + βs_{n−4}^{2} = s_{n}s_{n−4}.

Example 9. The sequence A_{n}(1, 1, 1) is the sequence 1, 1, 3, 6, 16, 40, … that counts Motzkin-Schröder paths, \underline{A128720}. Its Hankel transform h_{n}(1, 1, 1) is given by \underline{A174168}. This sequence begins

1, 2, 5, 17, 109, 706, 9529, 149057, 3464585, ….

It is a (1, 3) Somos-4 sequence.

5 The Pascal rhombus and the A-matrix

In this section we let g(x) = g(x; 1, 1, 1). Thus

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

The Riordan array (R_{n,k}) of Bell type given by (g(x), xg(x)) begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 & 0 \\ 6 & 7 & 3 & 1 & 0 & 0 \\ 16 & 18 & 12 & 4 & 1 & 0 \\ 40 & 53 & 37 & 18 & 5 & 1 \end{matrix} ) .

This is \underline{A132276}. This Riordan array is known in the literature as the left-bounded Pascal rhombus [8, 12, 18]. The rhombus appellation comes from the following property.

R_{n,k} = \begin{cases}0, & if k < 0; \\ 0^{k}, & if n = 0; \\ \binom{1}{k}, & if n = 1; \\ R_{n−1,k−1} + R_{n−1,k} + R_{n−1,k+1} + R_{n−2,k}, & otherwise. \end{cases}

Thus this is a Riordan array with A-matrix [5, 10] given by

( \begin{matrix}0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ) .

The row sums of this matrix, which begin

1, 2, 6, 17, 51, 154, 473, 1464, …

are given by \underline{A059398}, which counts the left factors of Motzkin-Schröder paths (or equivalently, the number of symmetric Motzkin-Schröder paths of length 2n). The generating function of the row sums of a Bell matrix (g(x), xg(x)) is the INVERT transform \frac{g(x)}{1−xg(x)} of g(x). We deduce that the generating function of \underline{A059398} can be expressed as the generating function

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

In fact, we have the following proposition.

Proposition 10. The generating function \frac{g(x)}{1−xyg(x)} of the left-bounded Pascal rhombus can be expressed as the following continued fraction.

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

Proof. We have that

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

Simplifying the right hand side shows that G(x, y) = \frac{g(x)}{1−xyg(x)}.

We note that the generating function given by the continued fraction

\frac{1}{1 − x − (y + 1)x^{2} − \frac{x^{2}}{1 − x − x^{2} − \frac{x^{2}}{1 − x − x^{2} − ⋯}}}

is the generating function of the stretched Riordan array (g(x), x^{2}g(x)) which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 6 & 2 & 0 & 0 & 0 & 0 & 0 \\ 16 & 7 & 1 & 0 & 0 & 0 & 0 \\ 40 & 18 & 3 & 0 & 0 & 0 & 0 \\ 109 & 53 & 12 & 1 & 0 & 0 & 0 \end{matrix} ) .

The row sums

1, 1, 4, 8, 24, 61, 175, 486, 1405, 4059, …

of this matrix are thus the diagonal sums of the left-bounded Pascal rhombus. This sequence is \underline{A190156}. It thus has generating function given by

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

Proposition 11. The generating function

\frac{1}{1 − x − x^{2} − \frac{(y + 1)x^{2}}{1 − x − x^{2} − \frac{x^{2}}{1 − x − x^{2} − ⋯}}}

is that of the triangle with general term T_{n,2k} where (T_{n,k}) is the left-bounded Pascal rhombus (g(x), xg(x)). The row sums of this matrix have generating function

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

The array (T_{n,2k}) begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 6 & 3 & 0 & 0 & 0 & 0 & 0 \\ 16 & 12 & 1 & 0 & 0 & 0 & 0 \\ 40 & 37 & 5 & 0 & 0 & 0 & 0 \\ 109 & 120 & 25 & 1 & 0 & 0 & 0 \end{matrix} ) .

The row sums

1, 1, 4, 9, 29, 82, 255, 773, 2410, 7499, …

are the main diagonal of the Pascal rhombus \underline{A059317}.

This row sums sequence is then given by \underline{A059345}. We recall that the (left-justified) Pascal rhombus begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 4 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 8 & 9 & 8 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 4 & 13 & 22 & 29 & 22 & 13 & 4 & 1 & 0 & 0 & 0 & 0 \\ 1 & 5 & 19 & 42 & 72 & 82 & 72 & 42 & 19 & 5 & 1 & 0 & 0 \\ 1 & 6 & 26 & 70 & 146 & 218 & 255 & 218 & 146 & 70 & 26 & 6 & 1 \end{matrix} ) ,

where we have high-lighted the main diagonal elements. The generating function of the Pascal rhombus (R_{n,k}) is \frac{1}{1−x−xy−xy^{2}−x^{2}y^{2}} . We briefly examine the bisection R_{n,2k} of the Pascal rhombus, which 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 & 8 & 8 & 1 & 0 & 0 & 0 \\ 1 & 13 & 29 & 13 & 1 & 0 & 0 \\ 1 & 19 & 72 & 72 & 19 & 1 & 0 \\ 1 & 26 & 146 & 255 & 146 & 26 & 1 \end{matrix} ) .

Conjecture 12. The generating function of the bisection (R_{n,2k}) of the Pascal rhombus is given by

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

Based on this conjecture, we can further posit that the row sums of this triangle, which begin

1, 2, 6, 18, 57, 184, 601, 1974, 6502, 21446, …,

have generating function

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

and the diagonal sums, which begin

1, 1, 2, 5, 10, 22, 50, 112, 254, 579, …,

have generating function

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

Example 13. We consider the number triangle (R̃_{n,k}) defined as follows.

R̃_{n,k} = \begin{cases}0, & if k < 0; \\ 0^{k}, & if n = 0; \\ \binom{1}{k} + \binom{0}{k}, & if n = 1; \\ R̃_{n−1,k−1} + 2R̃_{n−1,k} + R̃_{n−1,k+1} + R̃_{n−2,k}, & otherwise. \end{cases}

This array begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 6 & 4 & 1 & 0 & 0 & 0 & 0 \\ 18 & 16 & 6 & 1 & 0 & 0 & 0 \\ 58 & 60 & 30 & 8 & 1 & 0 & 0 \\ 194 & 224 & 134 & 48 & 10 & 1 & 0 \\ 670 & 836 & 570 & 248 & 70 & 12 & 1 \end{matrix} ) .

The first column sequence R̃_{n,0}

1, 2, 6, 18, 58, 194, …

counts Motzkin-Schröder paths with two kinds of h steps. It is essentially \underline{A085139}. We deduce that

R̃_{n,0} = ∑_{k=0}^{n+1} (\frac{n+k−1}{2} ; \frac{n−k+1}{2})\frac{1 − (−1)^{n−k}}{2} C_{k}.

The Hankel transform of the sequence R̃_{n,0} is the sequence 2^{⌊ \frac{(n+1)^{2}}{3} ⌋} that begins

1, 2, 8, 32, 256, 4096, 65536, ….

This sequence satisfies the (simplified) Somos-4 relation

s_{n} = \frac{4s_{n−1}s_{n−3}}{s_{n−4}} .

Example 14. We consider the number triangle (R̄_{n,k}) defined as follows.

R̄_{n,k} = \begin{cases}0, & if k < 0; \\ 0^{k}, & if n = 0; \\ \binom{1}{k} + 2\binom{0}{k}, & if n = 1; \\ R̄_{n−1,k−1} + 3R̄_{n−1,k} + R̄_{n−1,k+1} + R̄_{n−2,k}, & otherwise. \end{cases}

The matrix (R̄_{n,k}) begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 11 & 6 & 1 & 0 & 0 & 0 & 0 \\ 42 & 31 & 9 & 1 & 0 & 0 & 0 \\ 168 & 150 & 60 & 12 & 1 & 0 & 0 \\ 696 & 709 & 351 & 98 & 15 & 1 & 0 \\ 2965 & 3324 & 1920 & 672 & 145 & 18 & 1 \end{matrix} ) .

The first column sequence R̄_{n,0} (essentially \underline{A084782}), counts Motzkin-Schröder paths with three types of h step. The generating function of the sequence R̄_{n,0} can be expressed as

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

The Hankel transform of this sequence begins

1, 2, 13, 97, 901, 29186, 1647721, 93837697, ….

By our conjecture this is a (9, −5) Somos-4 sequence (\underline{A184019}).

Note that the matrix R̄ is a Bell-type Riordan array with A-matrix

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

We finish this section by noting that the matrix product (R_{n,k}) · ((−1)^{n−k}\binom{n}{k}) begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 4 & 0 & 1 & 0 & 0 & 0 \\ 7 & 2 & 6 & 0 & 1 & 0 & 0 \\ 10 & 18 & 3 & 8 & 0 & 1 & 0 \\ 37 & 24 & 33 & 4 & 10 & 0 & 1 \end{matrix} ) .

It is a Riordan array whose row sums enumerate the Motzkin-Schröder paths. The triangle itself enumerates Motzkin-Schröder paths of length n according to the number of h steps at level 0.

6 The A-matrix and continued fractions

The governing result concerning the A-matrix approach to Riordan arrays is as follows [5, 10].

Theorem 15. A lower-triangular array (t_{n,k})_{0≤n,k≤∞} is a Riordan array if and only if there exists another array A = (a_{i,j})_{i,j∈ℕ_{0}} with a_{0,0} ≠ 0, and a sequence (ρ_{j})_{j∈ℕ_{0}} such that

t_{n+1,k+1} = ∑_{i≥0} ∑_{j≥0} a_{i,j}t_{n−i,k+j} + ∑_{j≥0} ρ_{j}t_{n+1,k+j+2}.

The power series definition of a Riordan array is as follows. A Riordan array is defined by a pair of power series, g(x) and f(x), where

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

and

f(x) = f_{1}x + f_{2}x^{2} + f_{3}x^{3} + ⋯, f_{0} = 0 and f_{1} ≠ 0.

We then have

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

where [x^{n}] is the functional that extracts the coefficient of x^{n}. The relationship between f(x) and the pair (A, ρ) is given by the following key equation.

\frac{f(x)}{x} = ∑_{i≥0} x^{i}R^{(i)}(f(x)) + \frac{f(x)^{2}}{x} ρ(f(x)),

where R^{(i)} is the generating series of the i-th row of A, and ρ(x) is the generating series of the sequence ρ_{n}.

We consider the case

A = ( \begin{matrix}1 & b & d \\ 1 & a & c \end{matrix} ) ,

with ρ_{n} = 0 for all n. To find u = f(x), we solve the equation

\frac{u}{x} = 1 + bu + du^{2} + x(1 + au + cu^{2}).

We obtain

u(x) = \frac{1 − ax − bx^{2} − \sqrt{(1 − ax − bx^{2})^{2} − 4x^{2}(1 + x)(d + cx)}}{2x(d + cx)}.

We can express this as

\frac{u(x)}{x} = \frac{(1 + x)}{1 − ax − bx^{2}} ct (\frac{x^{2}(1 + x)(d + cx)}{(1 − ax − bx^{2})^{2}}) .

Thus we can express this as the following continued fraction.

\frac{u(x)}{x} = \frac{1}{1 − ax − bx^{2} − \frac{x^{2}(1 + x)(d + cx)}{1 − ax − bx^{2} − \frac{x^{2}(1 + x)(d + cx)}{1 − ax − bx^{2} − ⋯}}}.

We now look at the 8 cases defined by the A-matrix ( \begin{matrix}a & b & c \\ 1 & 1 & 1 \end{matrix} ) for a, b, c ∈ \{0, 1\}.

• The case ( \begin{matrix}0 & 0 & 0 \\ 1 & 1 & 1 \end{matrix} ). This gives us the equation

\frac{u}{x} = 1 + u + u^{2},

with solution

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

The corresponding equation

T_{n,k} = T_{n−1,k−1} + T_{n−1,k} + T_{n−1,k+1}

gives us the Bell Riordan array (m(x), xm(x)) that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 \\ 4 & 5 & 3 & 1 & 0 & 0 \\ 9 & 12 & 9 & 4 & 1 & 0 \\ 21 & 30 & 25 & 14 & 5 & 1 \end{matrix} ) .

The generating function m(x) is that of the Motzkin numbers \underline{A001006} and the Riordan array is \underline{A064189}.

• The case ( \begin{matrix}0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix} ). We obtain

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

This case corresponds to lattice paths with steps (1, 1), (1, −1), (1, 0) and a second up step (2, 1). The generating function g(x) = \frac{f(x)}{x} is that of the so-called horse permutations [7]. The equation

T_{n,k} = T_{n−1,k−1} + T_{n−1,k} + T_{n−1,k+1} + T_{n−2,k+1}

yields the Bell-type Riordan array that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 \\ 5 & 5 & 3 & 1 & 0 & 0 \\ 12 & 14 & 9 & 4 & 1 & 0 \\ 31 & 38 & 28 & 14 & 5 & 1 \end{matrix} ) .

Figure 2: “Horse” paths for n = 0, 1, 2, 3

The generating function g(x) expands to give the sequence \underline{A071359} which begins

1, 1, 2, 5, 12, 31, 83 ….

The Riordan array is \underline{A190252}. The matrix given by (g(x), xg(x)) · (\frac{1}{1+x}, \frac{x}{1+x}) where the second array is the inverse binomial array ((−1)^{n−k}\binom{n}{k}) begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 0 & 1 & 0 & 0 & 0 \\ 4 & 4 & 3 & 0 & 1 & 0 & 0 \\ 11 & 9 & 6 & 4 & 0 & 1 & 0 \\ 28 & 26 & 15 & 8 & 5 & 0 & 1 \end{matrix} ) .

This counts such “horse” paths [7, 10] (see Figure 2) in terms of the number of flat steps at level 0. These paths are governed by the following recurrence

H_{n} = H_{n−1} + ∑_{i=0}^{n−2} H_{i}H_{n−2−i} + ∑_{i=0}^{n−3} H_{i}H_{n−3−i}, H_{0} = 1, H_{1} = 1, H_{2} = 2.  (2)

Equivalently, we have the following equation for the generating function g_{h}(x). g_{h}(x) = 1 + xg_{h}(x) + x^{2}g_{h}(x)^{2} + x^{3}g_{h}(x)^{2}.

• The case ( \begin{matrix}0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ) is that of the Motzkin-Schröder paths. Thus

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

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

Then the equation

T_{n,k} = T_{n−1,k−1} + T_{n−1,k} + T_{n−1,k+1} + T_{n−2,k}

yields the Bell-type Riordan array (g(x), xg(x)) with f(x) = xg(x) which begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 & 0 \\ 6 & 7 & 3 & 1 & 0 & 0 \\ 16 & 18 & 12 & 4 & 1 & 0 \\ 40 & 53 & 37 & 18 & 5 & 1 \end{matrix} ) .

This is \underline{A132276}.

• The case ( \begin{matrix}0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} ) gives us

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

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

The equation

T_{n,k} = T_{n−1,k−1} + T_{n−1,k} + T_{n−1,k+1} + T_{n−2,k} + T_{n−2,k+1}

yields the Bell-type Riordan array that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 & 0 \\ 7 & 7 & 3 & 1 & 0 & 0 \\ 19 & 20 & 12 & 4 & 1 & 0 \\ 53 & 61 & 40 & 18 & 5 & 1 \end{matrix} ) .

The sequence that begins

1, 1, 3, 7, 19, 53, 153, …

is \underline{A078481}.

• The case ( \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix} ) gives us

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

The corresponding equation

T_{n,k} = T_{n−1,k−1} + T_{n−1,k} + T_{n−1,k+1} + T_{n−2,k} + T_{n−2,k−1}

leads to the Riordan array (g(x), (1 + x)xg(x)) where f(x) = x(1 + x)g(x). This array begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 5 & 7 & 5 & 1 & 0 & 0 \\ 12 & 19 & 16 & 7 & 1 & 0 \\ 31 & 52 & 49 & 29 & 9 & 1 \end{matrix} ) .

This is not of Bell-type. The sequence 1, 1, 2, 5, 12, … is \underline{A071359}. The generating function f(x)/x expands to give the sequence that begins

1, 2, 3, 7, 17, 43, ….

This is \underline{A143013}.

• The case ( \begin{matrix}1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix} ) gives us

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

The corresponding equation

T_{n,k} = T_{n−1,k−1} + T_{n−1,k} + T_{n−1,k+1} + T_{n−2,k} + T_{n−2,k−1}

leads to the Riordan array (g(x), (1+x)xg(x)) (where f(x) = x(1+x)g(x)) that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 6 & 7 & 5 & 1 & 0 & 0 \\ 16 & 21 & 16 & 7 & 1 & 0 \\ 44 & 64 & 52 & 29 & 9 & 1 \end{matrix} ) .

This is not a Bell-type Riordan array.

• The case ( \begin{matrix}1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ) gives us

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

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

T_{n,k} = T_{n−1,k−1} + T_{n−1,k} + T_{n−1,k+1} + T_{n−2,k} + T_{n−2,k}

leads to the Riordan array (g(x), (1 + x)xg(x)) where f(x) = x(1 + x)g(x), that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 3 & 3 & 1 & 0 & 0 & 0 \\ 7 & 9 & 5 & 1 & 0 & 0 \\ 19 & 27 & 19 & 7 & 1 & 0 \\ 53 & 81 & 67 & 33 & 9 & 1 \end{matrix} ) .

The sequence 1, 1, 3, 7, 19, … is \underline{A078481}. The generating function f(x)/x expands to give the sequence that begins

1, 2, 4, 10, 26, 72, 206, 606, 1820,

which is essentially \underline{A102407}.

• The case ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} ) gives us

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

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

The corresponding equation

T_{n,k} = T_{n−1,k−1} + T_{n−1,k} + T_{n−1,k+1} + T_{n−2,k−1} + T_{n−2,k} + T_{n−2,k+1}

leads to the Riordan array (g(x), (1 + x)xg(x)) where f(x) = x(1 + x)g(x), that begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 3 & 3 & 1 & 0 & 0 & 0 \\ 8 & 9 & 5 & 1 & 0 & 0 \\ 23 & 29 & 19 & 7 & 1 & 0 \\ 69 & 93 & 70 & 33 & 9 & 1 \end{matrix} ) .

In this case, the generating function f(x)/x expands to give the sequence that begins

1, 2, 4, 11, 31, 92, 283, 893, 2875, ….

This is essentially \underline{A247333}.

To each of the cases above, we can associate an elliptic curve.

• To the case of ( \begin{matrix}0 & 0 & 0 \\ 1 & 1 & 1 \end{matrix} ) we can associate the curve of equation

y^{2} + xy − y = −x^{2}.

Solving this for y gives y = \frac{1−x−\sqrt{1−2x−3x^{2}}}{2} . Equivalently, the solution to

xy^{2} + xy − y = −x

gives y = \frac{1−x−\sqrt{1−2x−3x^{2}}}{2x}.

• To the case of ( \begin{matrix}0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix} ) we can associate the curve of equation

y^{2} + xy − y = −x^{3} − x^{2},

which yields

y = \frac{1 − x − \sqrt{1 − 2x − 3x^{2} − 4x^{3}}}{2} .

Note then that

(1 + x)^{2}x^{2}y^{2} + (1 + x)x^{2}y − (1 + x)y = −x^{3} − x^{2}

gives

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

• To the case of ( \begin{matrix}0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ) we can associate the curve of equation

y^{2} + x^{2}y + xy − y = −x^{2}.

This yields

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

Alternatively,

xy^{2} + x^{2}y + xy − y = −x

yields

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

• To the case of ( \begin{matrix}0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} ) we can associate the curve of equation

y^{2} + x^{2}y + xy − y = −x^{3} − x^{2},

which gives

y = \frac{1 − x − x^{2} − \sqrt{1 − 2x − 5x^{2} − 2x^{3} + x^{4}}}{2} .

Alternatively we have the curve with equation

(xy(1 + x))^{2} + x^{2}(xy(1 + x)) + x(xy(1 + x)) − (xy(1 + x)) = −x^{3} − x^{2},

which gives

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

• To the case of ( \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix} ) we can associate the curve of equation

y^{2} + xy − y = −x^{3} − x^{2}.

• To the case of ( \begin{matrix}1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix} ) we can associate the curve of equation

y^{2} + xy − y = −x^{4} − 2x^{3} − x^{2},

which yields

y = \frac{1 − x − \sqrt{1 − 2x − 3x^{2} − 8x^{3} − 4x^{4}}}{2} .

• To the case of ( \begin{matrix}1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ) we can associate the curve of equation

y^{2} + x^{2}y_{x}y − y = −x^{3} − x^{2}.

• To the case of ( \begin{matrix}1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ) we can associate the curve of equation

y^{2} + x^{2}y + xy − y = −x^{4} − 2x^{3} − x^{2},

which yields

y = \frac{1 − x − x^{2} − \sqrt{1 − 2x − 5x^{2} − 6x^{3} − 3x^{4}}}{2} .

The change of variable y → xy(1 + x) then yields y = f(x) as

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

7 3-generalized Motzkin paths

Using the nomenclature of [12], we shall understand by a 3-generalized Motzkin path a path with unit up and down steps given, respectively, by (1, 1) and (1, −1), and three horizontal steps h,H, and H of lengths, respectively, of 1, 2, and 3. Such paths are enumerated by the sequence which begins

1, 1, 3, 7, 18, 48, 132, 372, 1069, 3121, 9232, 27610, ….

We find that the generating function g_{3}(x) of these 3-generalized Motzkin paths is given by the continued fraction expression

g_{3}(x) = \frac{1}{1 − x − x^{2} − x^{3} − \frac{x^{2}}{1 − x − x^{2} − x^{3} − \frac{x^{2}}{1 − x − x^{2} − x^{3} − ⋯}}}.

Solving the equation

u = \frac{1}{1 − x − x^{2} − x^{3} − x^{2}u},

we find that

u = u(x) = g_{3}(x) = \frac{1 − x − x^{2} − x^{3} − \sqrt{1 − 2x − 5x^{2} + 3x^{4} + 2x^{5} + x^{6}}}{2x^{2}} ,

or equivalently [18]

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

The number triangle given by the Riordan array (g_{3}(x), xg_{3}(x)) begins

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 & 0 \\ 7 & 7 & 3 & 1 & 0 & 0 \\ 18 & 20 & 12 & 4 & 1 & 0 \\ 48 & 59 & 40 & 18 & 5 & 1 \end{matrix} ) .

The A-matrix for this Riordan array is then given by

( \begin{matrix}0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ) .

8 Conclusions

In this note, we have studied the enumeration of Motzkin-Schröder paths in the broader

context of Riordan arrays defined by an A-matrix of the form A = ( \begin{matrix}a & b & c \\ 1 & 1 & 1 \end{matrix} ). The

key equation for Riordan arrays defined by an A-matrix has allowed us to find generating functions for the resulting generalized lattice paths. In the case of the Motzkin-Schröder paths, this resulting generating function is also given by a defining recurrence. Because of the appearance of the generating function of the Catalan numbers (due to the quadratic nature of the equations), the generating functions studied all admit continued fraction expressions, and we conjecture that in each case, the Hankel transform of the expansions of these generating functions give Somos-4 sequences.

References

[1] P. Barry, Riordan Arrays: a Primer, Logic Press, 2017.

[2] P. Barry, Generalized Catalan numbers, Hankel transforms and Somos-4 sequences, J. Integer Sequences 13 (2010), Article 10.7.2.

[3] W. Y. C. Chen, S. H. F. Yan, and L. L. M. Yang, Weighted 2-Motzkin paths, Arxiv preprint arXiv:math/0410200 [math.CO], 2004. Available at https://arxiv.org/abs/

math/0410200.

[4] E. Deutsch and L. W. Shapiro, A bijection between ordered trees and 2-Motzkin paths and its many consequences, Discrete Math. 256 (2002), 655–770.

[5] T.-X. He, Matrix characterizations of Riordan arrays, Linear Alg. Appl. 465 (2015), 15–42.

[6] A. N. W. Hone, Elliptic curves and quadratic recurrence sequences, Bull. Lond. Math. Soc. 37 (2005), 161–171.

[7] Q. Hou and T. Mansour, Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials, Discr. Appl. Math. 154 (2006), 1183–1197.

[8] W. F. Klostermeyer, M. Mays, L. Soltes, and G. Trapp, A Pascal rhombus, Fibonacci Quart. 35 (1997), 318–328.

[9] A. E. Price and A. D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T -fraction) for the Ward polynomials, Arxiv preprint arXiv:2001.01468 [math.CO], March 10 2020. Available at https://arxiv.org/abs/

2001.01468.

[10] D. Merlini, D. G. Rogers, R. Sprugnoli, and M.C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math. 49 (1997), 301–320.

[11] J. Propp, The Somos sequence site, http://jamespropp.org/somos.html.

[12] J. L. Ramirez, The Pascal rhombus and the generalized grand Motzkin paths, Fibonacci Quart. 54 (2015), 99–104.

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

    cally at https://oeis.org, 2023.

[14] L. Shapiro, R. Sprugnoli, P. Barry, G.-S. Cheon, T.-X. He, D. Merlini, and W. Wang, The Riordan Group and Applications, Springer, 2022.

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

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

[17] H. S. Wall, Analytic Theory of Continued Fractions, Amer. Math. Soc., 2000.

[18] S.-L. Yang and Y.-Y. Gao, Pascal rhombus and Riordan array, J. Lanzhou Univ. Tech. 44 (2020), 150–154.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 11B37, 15B36, 11A55, 15A15, 15B05. Keywords: Schröder path, Motzkin path, horse path, lattice path, recurrence, Riordan array, continued fraction, Somos sequence.

(Concerned with sequences \underline{A000012}, \underline{A000045}, \underline{A000108}, \underline{A001006}, \underline{A006318}, \underline{A025235}, \underline{A059317}, \underline{A059345}, \underline{A059398}, \underline{A059841}, \underline{A060693}, \underline{A064189}, \underline{A071359}, \underline{A078481}, \underline{A084782}, \underline{A085139}, \underline{A102407}, \underline{A103210}, \underline{A128720}, \underline{A132276}, \underline{A132277}, \underline{A143013}, \underline{A174168}, \underline{A184019}, \underline{A190156}, \underline{A190252}, and \underline{A247333}.)

Received April 29 2022; revised version received May 3 2023. Published in Journal of Integer Sequences, May 9 2023.

Return to Journal of Integer Sequences home page.