Riordan Matrices and Lattice Path Enumeration

In this friendly survey, we look at some interactions between a certain class of infinite matrices called Riordan matrices and the class of combinatorial objects called lattice paths. There are a variety of interesting algebraic and combinatorial relationships between Riordan matrices and lattice path enumeration problems. This article attempts to introduce the reader to the concepts and techniques that may be used to explore these relationships.

The lattice paths considered in this article are presented as combinatorial objects which are subject to specific construction rules, and our interest is to enumerate and classify them with counting sequences. Riordan matrices are infinite matrices whose columns can be associated with a certain kind of sequence of generating functions. There are many interesting Riordan matrices that contain column entries or row sums associated with well-known counting numbers, such as the binomial coefficients, the ballot, Catalan, Motzkin, Schröder, Fine, Delannoy, and RNA numbers, and other counting numbers that can be found in Sloane’s On-line Encyclopedia of Integer Sequences S1. The aim of this article is to introduce the reader to Riordan matrices and to present examples of solutions to particular lattice path counting problems, where the lattice paths are enumerated by the column entries or row sums of Riordan matrices.

Algebraic combinatorics involves the use of techniques from algebra, topology, and geometry in the solution of combinatorial problems. Because of this interplay with many fields of mathematics, algebraic combinatorics is an area in which a wide variety of ideas and methods come together. Riordan arrays appear in algebraic combinatorics and are useful for proving combinatorial sums and identitites. They also appear in various counting problems in enumerative combinatorics. A certain subset of Riordan arrays called proper Riordan arrays, otherwise known as Riordan matrices, form the Riordan group, an infinite non-commutative matrix group, which is the main combinatorial device reported in this article. The Riordan group can be characterized as being algebraic and combinatorial. Thus, as a subfield of enumerative and algebraic combinatorics, the Riordan group brings together a wide variety of combinatorial methods and mathematical ideas. There are also some interesting mathematical contributions outside of combinatorics that touch on geometry, group theory, Lie algebra and groups, functional analysis, representation theory, and queuing theory. For a more thorough survey of contributions of the Riordan group to other areas of mathematics and combinatorics, see the monograph by Shapiro et al. SSB$^{+}$.

The algebraic concepts subsequently reported in this article involve finding inverse relations and multiplying, inverting, and manipulating Riordan matrices. The concepts covered herein involve using recurrence relations, generating functions, combinatorial statistics and explicit bijections to solve certain lattice path counting problems. However, the authors do not claim to solve all lattice path counting problems associated with Riordan matrices.

The article proceeds with an overview of the type of lattice paths under consideration, followed by an elementary introduction to generating functions. Riordan arrays are then formally introduced, followed by a section devoted to the algebra of the Riordan group. The last two sections of the paper feature specific demonstrations of how the Riordan group can be applied to lattice path enumeration problems, especially as related to generalized Catalan paths.

Lattice paths

The subject of counting paths (walks) on the lattice in Euclidean space is one of the most important areas of combinatorics. The lattice paths described in this article are defined on the integral lattice $\mathbb{Z}^{d}$, where $d\geq 1$, under the conditions that each path starts at some fixed origin, moves according to certain steps under specified rules and restrictions, and never crosses or touches certain coordinate axes or hyperplanes. For excellent introductions to lattice path combinatorics and enumeration, see the surveys by Humphreys H and Krattenthaler K.

A lattice path is a sequence of contiguous (unit) steps which traverses the $d$-dimensional integral lattice $\mathbb{\mathbb{Z} }^{d}$. More precisely, a lattice path in $\mathbb{Z} ^{d}$ with $k\geq 1$ unit steps is a sequence $\acute{s}_{1},\acute{s}_{2},\ldots ,\acute{s}_{k}\in \mathbb{Z} ^{d}$ such that for each $i,1\leq i\leq k$, $\acute{s}_{i}-\acute{s}_{i-1}\in \acute{S}\subset \mathbb{Z} ^{d}$. In this case, we refer to $\acute{S}$ as a step set. We will often refer to a lattice path simply as a path, where the path is encoded by a word based on an alphabet containing $\acute{S}$. Geometrically, a lattice path is represented by the edges between the consecutive vertices of the path. A path with no steps is a point. The length of a path is the number of unitary steps.

In this article, the paths are considered to be in $d$-dimensional Euclidean space and never pass below a specified hyperplane. Typically, in $\mathbb{Z}^2$, the paths never pass below the $x$-axis. The height of a path corresponds to the $y$ value of the endpoint $\left( x,y\right)$ of the path. In three dimensions the paths are considered to be in three-dimensional Euclidean space and often never pass below the $xy$-plane. The height of each path corresponds to the $z$ value of the endpoint $\left( x,y,z\right)$ of the path. Throughout this article, we will focus mainly on lattice paths in the plane, i.e., $d=2$. However, the step sets of particular higher dimensional paths defined in N2 will be mentioned in the last section. There are many types of path problems as well as methods and models for finding their solutions. Thus, there is a vast amount of literature on this topic from the self-avoiding walk problem to lattice path problems with infinite step sets.

Examples of lattice paths

This article will focus mainly on Dyck (Catalan) paths and related paths, such as Motzkin and Schröder paths, with a few other paths discussed briefly.

Example 1 (Dyck Paths).

A Dyck (Catalan) path is a lattice path in the first quadrant of $\mathbb{Z}^2$ which begins at the origin $\left( 0,0\right)$, ends at $\left( 2n,0\right)$, has the step set $\acute{S}=\left\{ \left( 1,1\right) ,\left( 1,-1\right) \right\}$, and never goes below the $x$-axis. These paths can be described as paths that consist of unit up steps with slope $1$, denoted by $U$, and unit down steps with slope $-1$, denoted by $D$. We refer to $n$ as the semi-length of the path. A Dyck path of semi-length $n$ is called a Dyck $n$-path. These paths are counted by the Catalan numbers, which are defined in the next section. The $5$ possible paths of length $6$ are depicted in Figure 1 and can also be encoded by the words

$$\begin{equation*} UUUDDD,UUDUDD,UUDDUD, \end{equation*}$$

$$\begin{equation*} UDUUDD,UDUDUD. \end{equation*}$$

Figure 1.

The $5$ Dyck paths of semi-length $3$.

Example 2 (Motzkin Paths).

A Motzkin path of length $n$ is a lattice path in $\mathbb{Z} ^{2}$ that begins at the origin $\left( 0,0\right)$, ends at $\left( n,0\right)$, has step set $\acute{S}=\{(1,1),(1,0), (1,-1)\}$ and never passes below the $x$-axis. These paths consist of unit up steps with slope $1$ denoted by $U$, unit down steps with slope $-1$ denoted by $D$, and unit horizontal (or level) steps with slope $0$ denoted by $H$. Motzkin paths are counted by the Motzkin numbers that are defined in the next section. The $4$ possible paths of length $3$ are shown in Figure 2 and the $9$ possible paths of length $4$ can be encoded by the words

$$\begin{equation*} UUDD,UHHD,UDUD,UDHH,UHDH, \end{equation*}$$

$$\begin{equation*} HUDH,HUHD, HHUD,HHHH. \end{equation*}$$

Figure 2.

The $4$ Motzkin paths of length $3$.

Example 3 (Schröder Paths).

A Schröder path is a path in the first quadrant of $\mathbb{Z}^2$ that begins at the origin $\left( 0,0\right)$, ends at $\left( 2n,0\right)$, with step set $\acute{S}=\left\{ \left( 1,1\right), \left( 1,-1\right), \left( 2,0\right) \right\}$ and never passes below the $x$-axis. These paths consist of $U$ steps, $D$ steps, and double horizontal or level steps denoted by $\widetilde{H}$. These paths are counted by the large Schröder numbers that are defined in the next section. The $6$ possible paths of length $4$ are depicted in Figure 3.

Figure 3.

The $6$ Schröder paths of length $4$.

Motzkin, Dyck, and Schröder paths are interesting combinatorial objects and they appear in a wide variety of combinatorial problems. Riordan arrays have been constructed to study these paths and many other types of lattice path counting problems.

Generating functions

In order to understand Riordan matrices, some working knowledge of generating functions is needed. In this article, Riordan arrays are defined in terms of ordinary generating functions.

Given a sequence $\left\langle b_{n}\right\rangle _{n\geq 0}$ of elements of a commutative ring, the ordinary generating function $\left( GF\right)$ for $\left\langle b_{n}\right\rangle _{n\geq 0}$ is the formal power series

$$\begin{equation*} b\left( z\right) =\sum _{n\geq 0}b_{n}z^{n}=b_{0}+b_{1}z+b_{2}z^{2}+\cdots \end{equation*}$$

where $z$ is an indeterminate (or auxiliary variable). In some instances “aerated” $GFs$ are of interest. An aerated $GF$ is a $GF$ of the form

$$\begin{equation*} b\left( z^{2}\right) =\sum _{n\geq 0}b_{n}z^{2n}=b_{0}+b_{1}z^{2}+b_{2}z^{4}+\cdots \end{equation*}$$

where $\left\langle b_{0},0,b_{1},0,b_{2},\ldots \right\rangle$ is the associated sequence of aerated coefficients. In this article, we will only refer to the concept of aerated $GFs$ once in Example 13, but otherwise they may be encountered frequently in some lattice path enumeration problems.

Note that since $GFs$ are defined algebraically as formal power series, and not as real-valued functions, series convergence is not necessary for the existence of $GFs$. Nonetheless, convergence of $GFs$ is sometimes necessary for finding exact formulae and asymptotic estimates of the $n$th term of a sequence. See Wilf W2, for more details on algebraic and analytic properties of $GFs$.

Sequences of coefficients in combinatorics are sometimes called counting sequences and are often computed by recurrence relations. A recurrence relation (or recursion) recursively defines a sequence where the $n$th term of the sequence is expressed in terms of some previous $k$ terms, $k<n$. In turn, $GFs$ can be derived from their related recurrence relation. The famed Fibonacci numbers are computed by the following recurrence relation

$$\begin{equation*} F_{n+1}=F_{n}+ F_{n-1}\text{, }n\geq 1 \end{equation*}$$

with initial conditions $F_{0}=F_{1}=1$. The $GF$ for this sequence is perhaps one of the most recognized and studied $GFs$:

$$\begin{equation*} F\left( z\right) =\sum _{n\geq 0}F _{n}z^{n}=1+z+2z^{2}+3z^{3}+\cdots = \frac{1}{ 1-z-z^{2}} \end{equation*}$$

where $\left\langle F_{0},F_{1},F_{2},\ldots \right\rangle =\left\langle 1,1,2,\ldots \right\rangle$ are the popular Fibonacci numbers, which count various combinatorial objects including lattice paths. The $n$th Fibonacci number is given by

$$\begin{equation*} F_{n}=\left( \beta ^{n+1}-\alpha ^{n+1}\right) /\sqrt {5} \end{equation*}$$

where $\alpha =\left( 1-\sqrt {5}\right) /2$, $\beta =\left( 1+\sqrt {5}\right) /2$, and $\beta$ is known as the golden ratio.

Interestingly, with the same recurrence relation, if the initial conditions are $\hat{F}_{0}=0,\hat{F}_{1}=1$, then

$$\begin{equation*} \hat{F}_{n}=\left( \beta ^{n}-\alpha ^{n}\right) /\sqrt {5}\text{ and }\hat{F}\left( z\right) =z/\left( 1-z-z^{2}\right) . \end{equation*}$$

Some suggested exercises for the reader are to use the recursion to derive $F\left( z\right)$, and then to use $F\left( z\right)$ to derive the exact forumula of $F_{n}$ given above.

We now present three examples of $GFs$ that are commonly encountered in lattice path enumeration.

Example 4.

The Catalan $GF$ is defined by

$$\begin{align*} c\left( z\right)=\sum _{n\geq 0}{c_{n}z^{n}}&=1+z+2z^{2}+5z^{3}+\cdots \\ &=\frac{ 1-\sqrt {1-4z}}{2z} \end{align*}$$

where $\left\langle c_{n}\right\rangle _{n\geq 0}=\left\langle 1,1,2,5,\ldots \right\rangle$ are the Catalan numbers and $c_{n}= 1/\left( n+1\right) \left({{2n}\atop {n}}\right)$ is the $n$th Catalan number. They are computed recursively by $c_{0}=1$,

$$\begin{equation*} c_{n+1}=\sum _{k=0}^{n}{c_{k}c_{n-k}},\text{ }n\geq 1\text{.} \end{equation*}$$

The Catalan numbers appear in many combinatorial problems and have a variety of algebraic applications S2.

Next, we present the Motzkin and Schröder $GFs$ which have lattice path interpretations that are related to the Catalan numbers.

Example 5.

The Motzkin $GF$ is defined by

$$\begin{align*} m\left( z\right) =\sum _{n\geq 0}{m_{n}z^{n}}&=1+z+2z^{2}+4z^{3}+\cdots \\ &=\frac{1-z-\sqrt {1-2z-3z^{2}}}{2z^{2}} \end{align*}$$

where $\left\langle m_{n}\right\rangle _{n\geq 0}=\left\langle 1,1,2,4,\ldots \right\rangle$ are the Motzkin numbers. They are computed recursively by $m_{0}=1$, $m_{1}=1$,

$$\begin{equation*} m_{n}=m_{n-1}+\sum _{k=0}^{n-2}{m_{k}m_{n-2-k}},\text{ }n\geq 2 \end{equation*}$$

and are connected to the Catalan numbers by

$$\begin{equation*} m_{n}=\sum _{k=0}^{\left\lfloor n/2\right\rfloor }{\binom{n}{2k}c_{k}} \end{equation*}$$

where $\left\lfloor x\right\rfloor$ denotes the floor of $x$ (i.e., the greatest integer $\leq x$).

Example 6.

The Schröder $GF$ is defined by

$$\begin{align*} \widetilde{s}\left( z\right) =\sum _{n\geq 0}{\widetilde{s}_{n}z^{n}}&=1+2z+6z^{2}+22z^{3}+\cdots \\ & =\frac{ 1-z-\sqrt {1-6z+z^{2}}}{2z} \end{align*}$$

where $\left\langle \widetilde{s}_{n}\right\rangle _{n\geq 0}=\left\langle 1,2,6,22,\ldots \right\rangle$ are the large Schröder numbers. They are computed recursively by $\widetilde{s}_{0}=1,\widetilde{s}_{2}=2$,

$$\begin{equation*} \widetilde{s}_{n}=3\widetilde{s}_{n-1}+\sum _{k=1}^{n-2}{\widetilde{s}_{k}\widetilde{s}_{n-1-k}},\text{ }n\geq 2 \end{equation*}$$

and are connected to the Catalan numbers by

$$\begin{equation*} \widetilde{s}_{n}=\sum _{k=0}^{n}{\binom{2n-k}{k}c_{n-k}},n\geq 0. \end{equation*}$$

The Catalan, Motzkin, and Schröder $GFs$ appear in many combinatorial problems. For more properties and examples of $GFs$ and recurrence relations, see W2.

What are Riordan arrays?

The Riordan array concept was introduced in 1991 by Shapiro et al. SGWW. A Riordan array is a special infinite lower-triangular matrix where the column entries consist of coefficients of certain formal power series. Representing infinite matrices by coefficients of (formal) power series is not new and goes back to papers by Schur S and Jabotinsky J on Faber polynomials. Thus, Riordan arrays depend upon certain formal power series and $GFs$.

Suppose $g\left( z\right) =g_{0}+g_{1}z+g_{2}z^{2}+\cdots$ and $f\left( z\right) =f_{1}z+f_{2}z^{2}+\cdots$, where $g_{0}\neq 0$ and $g\left( z\right)$ and $f\left( z\right)$ are formal power series $\mathbb{C} \left[ \left[ \mathbb{Z} \right] \right]$. Then the infinite array

$$\begin{equation*} L=\left( l_{n,k}\right) _{n,k\geq 0}, \end{equation*}$$

with entries in $\mathbb{C}$ is called a Riordan array if the ordinary generating function for its $k$th column is the Cauchy (convolution) product of $g(z)$ and $f^k(z)$. That is, $L$ is a Riordan array if the $GF$ for the sequence $\langle l_{n,k}\rangle _{n\geq 0}$ of numbers in the $k$th column of $L$ is

$$\begin{equation*} g\left( z\right) \cdot f^{k}\left( z\right) \end{equation*}$$

for all $k\geq 0$. The constant coefficient $g_{0}=1$ is commonly used for combinatorial convenience. Note that $g\left( z\right)$ and $f\left( z\right)$ are sometimes abbreviated, respectively, as $g$ and $f$.

Since the column-generating functions of a Riordan array $L$ form a geometric sequence $g,gf,\ldots ,gf^{k},\dots$, we may denote the Riordan array $L$ in pair form as

$$\begin{equation*} L=\left( g\left( z\right) ,f\left( z\right) \right) =\left( \begin{array}{cccc} \mid & \mid & \mid & \\g & gf & gf^{2} & \cdots \\\mid & \mid & \mid & \end{array}\right) . \end{equation*}$$

The $\left( n,k\right)$-th or generic element of $L$ can be obtained by extracting the $n$th coefficient of $gf^{k}$ and obtaining

$$\begin{equation*} l_{n,k} =\left[ z^{n}\right] g\left( z\right) \cdot f^{k}\left( z\right) \end{equation*}$$

where $\left[ z^{n}\right]$ denotes the operator for extracting the $n$th coefficient of a generating function. For instance, $\left[ z^{4}\right] F\left( z\right) =5=F_{4}$. For rules that govern the actions of $\left[ z^{n}\right]$, see SSB$^{+}$. The rules are sometimes called the method of coefficients and sometimes involve using the binomial theorem and Lagrange inversion formula to extract the coefficients.

Following the definition of $L$ and if, in addition, $f_{1}\neq 0$ is satisfied, then $L$ is invertible under matrix multiplication. The invertible Riordan arrays are called proper Riordan arrays or simply Riordan matrices. We note that Riordan matrices are also known as “recursive matrices” in the umbral calculus MRSV. Riordan matrices (arrays) are also defined by coefficients of exponential generating functions where one encounters the well-known derangement, partition (Bell), Bernoulli, Cauchy, Euler, and Stirling numbers; however, they are not described in this paper. For more information and examples of Riordan arrays and exponential formal power series see B.

Examples of Riordan arrays

Here we provide examples of Riordan arrays related to the Pascal, Catalan, Motzkin, and RNA sequences.

Example 7 (Pascal’s Triangle).

Pascal triangle, the most popular example, denoted by $P$ contains the well-known binomial coefficients. When written in infinite lower-triangular form,

$$\begin{equation*} P=\left( \frac{ 1}{ 1-z} ,\frac{z}{ 1-z} \right) =\left( \begin{array}{cccccc} 1 & & & & & \\1 & 1 & & & & \\1 & 2 & 1 & & & \\1 & 3 & 3 & 1 & & \\1 & 4 & 6 & 4 & 1 & \\\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right) \end{equation*}$$

where

$$\begin{equation*} p_{n,k} =\left[ z^{n}\right] \left( 1/\left( 1-z\right) \right) \left( z/\left( 1-z\right) \right) ^{k}=\binom{n}{k} \end{equation*}$$

is the $\left( n,k\right)$-th element of $P$. More generally, for integers $t\geq 1$

$$\begin{equation*} P^{t}=\left( 1/\left( 1-tz\right) ,z/\left( 1-tz\right) \right) \end{equation*}$$

is a generalized Pascal-Riordan matrix with generic element $\left({{n}\atop {k}}\right)t^{n-k}$. The entries of $P$ count certain lattice paths in $\mathbb{Z}^{2}$ with horizontal and diagonal steps that do not go above the line $y=x$ or below the $x-$axis SSB$^{+}$. A suggested exercise for the reader is to show that the entries of $P^{t}$ count the lattice paths in $\mathbb{Z}^{t}$ with different kinds of horizontal steps that come in $t$ different colors.

Example 8 (Aigner-Catalan Array).

The Aigner-Catalan array denoted by $C$ contains the well-known ballot numbers. $C$ is defined as

$$\begin{equation*} C=\left( c\left( z\right) ,zc\left( z\right) \right) =\left( \begin{array}{cccccc} 1 & & & & & \\1 & 1 & & & & \\2 & 2 & 1 & & & \\5 & 5 & 3 & 1 & & \\14 & 14 & 9 & 4 & 1 & \\\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right) \end{equation*}$$

where the leftmost column entries are the Catalan numbers, $c\left( z\right)$ is the Catalan $GF$,

$$\begin{equation*} \widetilde{c}_{n,k} =\left[ z^{n}\right] c\left( z\right) \left( zc\left( z\right) \right) ^{k}=\frac{k+1}{n+1} \binom{2n-k}{n-k} \end{equation*}$$

is the $\left( n,k\right)$-th element of $C$, and $\widetilde{c}_{n,k}$ are the well-known ballot numbers. The entries of $C$ count certain lattice paths in $\mathbb{Z}^{2}$ with horizontal and vertical steps that are restricted to lie on or below the line $y=x$ in the coordinate plane SSB$^{+}$.

Example 9 (Shapiro-Catalan Array).

The Shapiro-Catalan array denoted by $B$ is defined as

$$\begin{equation*} B=\left( c^{2}\left( z\right) ,zc^{2}\left( z\right) \right) =\left( \begin{array}{cccccc} 1 & & & & & \\2 & 1 & & & & \\5 & 4 & 1 & & & \\14 & 14 & 6 & 1 & & \\42 & 48 & 27 & 8 & 1 & \\\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right) \end{equation*}$$

where the leftmost column entries are the Catalan numbers (minus the leading $1$) and

$$\begin{equation*} b_{n,k} =\left[ z^{n}\right] c^{2}\left( z\right) \left( zc^{2}\left( z\right) \right) ^{k}=\frac{ k+1}{n+1} \binom{2n+2}{n-k} \end{equation*}$$

is the $\left( n,k\right)$-th element of $B$. The entries of $B$ count certain pairs of non-intersecting lattice paths in $\mathbb{Z}^{2}$ in the first quadrant.

Example 10 (Radoux-Catalan Array).

The Radoux-Catalan array denoted by $\tilde{A}$ is defined as

$$\begin{equation*} \tilde{A}=\left( c\left( z\right) ,zc^{2}\left( z\right) \right) =\left( \begin{array}{cccccc} 1 & & & & & \\1 & 1 & & & & \\2 & 3 & 1 & & & \\5 & 9 & 5 & 1 & & \\14 & 28 & 20 & 7 & 1 & \\\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right) \end{equation*}$$

where the leftmost column entries are again the Catalan numbers and

$$\begin{align*} a_{n,k} &=\left[ z^{n}\right] c\left( z\right) \left( zc^{2}\left( z\right) \right) ^{k}\\ &=\frac{ 2k+1}{ 2n+1} \binom{2n+1}{n-k} \end{align*}$$

is the $\left( n,k\right)$-th element of $\tilde{A}$. The entries of $\tilde{A}$ count certain Dyck paths A1.

The Catalan arrays $\tilde{A}$, $B$, and $C$ are of interest and appear in many combinatorial problems.

Example 11 (RNA Array N1).

The RNA array, denoted by $R^{\ast }$, is defined as

$$\begin{equation*} R^{\ast }=\left( s\left( z\right) ,zs\left( z\right) \right) =\left( \begin{array}{cccccc} 1 & & & & & \\1 & 1 & & & & \\1 & 2 & 1 & & & \\2 & 3 & 3 & 1 & & \\4 & 6 & 6 & 4 & 1 & \\\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right) \end{equation*}$$

where the leftmost column entries are the RNA numbers (or generalized Catalan numbers) which count RNA secondary structures from molecular biology S2, W1. The $GF$ for the RNA numbers is

$$\begin{align*} s\left( z\right) &=\sum _{n\geq 0}{s_{n}z^{n}}=1+z+z^{2}+\cdots \\ &=\frac{1-z+z^{2}-\sqrt {1-2z-z^{2}-2z^{3}+z^{4}}}{2z^{2}}, \end{align*}$$

and $\left\langle s_{n}\right\rangle _{n\geq 0}=\left\langle 1,1,1,2,4,8,\ldots \right\rangle$ W1. The RNA numbers are computed recursively

$$\begin{equation*} s_{n}{}_{+1}=s_{n}+\sum _{k=1}^{n}{s_{k-1}s_{n-k}},\text{ }n\geq 2 \end{equation*}$$

with $s_{0}=s_{1}=s_{2}=1$. They are also computed by the following sum

$$\begin{equation*} \sum _{k\geq 1}\frac{1}{ n-k }\binom{n-k}{k}\binom{n-k}{k-1}\left( k<n\right) . \end{equation*}$$

The entries of $R^{\ast }$ count certain Motzkin paths with certain restrictions N1. A problem of interest is to find a nice form for the generic element of $R^{\ast }$

$$\begin{equation*} {s}_{n,k} =\left[ z^{n}\right] s\left( z\right) \left( zs\left( z\right) \right) ^{k}. \end{equation*}$$

Example 12 (An Improper Riordan Array).

The array below denoted by $Q^{\ast }$ is an example of an improper Riordan array MRSV

$$\begin{equation*} Q^{\ast }=\left( q\left( z\right) ,z^{2}q\left( z\right) \right) =\left( \begin{array}{cccccc} 1 & & & & & \\1 & 0 & & & & \\2 & 1 & 0 & & & \\5 & 2 & 0 & 0 & & \\12 & 5 & 1 & 0 & 0 & \\\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right) \end{equation*}$$

where $q\left( z\right)$ is the generating function

$$\begin{align*} q\left( z\right) &=\sum _{n\geq 0}q_{n}z^{n}=1+z+2z^{2}+5z^{3}+\cdots \\ &=\frac{ 1-z-\sqrt {1-2z-3z^{2}-4z^{3}}}{2z^{2}\left( 1+z\right)} . \end{align*}$$

Note that $\left[ z^{1}\right] z^{2}q\left( z\right) =0$. So, $Q^{\ast }$ is not a proper Riordan array. However, the entries of $Q^{\ast }$ count certain lattice paths in $\mathbb{Z}^{2}$ with steep and shallow diagonal steps MRSV.

We conclude the examples by noting some well-known combinatorial triangles that are not (ordinary) Riordan arrays, as defined in this article. The Narayana array denoted by $\tilde{T}$ contains the Narayana numbers $\tilde{T}_{n,k}$, $0\leq k<n$. $\tilde{T}$ is typically given as an example of an invertible, infinite lower-triangular array that is not a Riordan array.

$$\begin{equation*} \tilde{T}=\left( \begin{array}{cccccc} 1 & & & & & \\1 & 1 & & & & \\1 & 3 & 1 & & & \\1 & 6 & 6 & 1 & & \\1 & 10 & 20 & 10 & 1 & \\\vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right) \end{equation*}$$

and the generic element is

$$\begin{equation*} \tilde{T}_{n,k} =\frac{1}{n} \binom{n}{k}\binom{n}{k+1}. \end{equation*}$$

$\tilde{T}$ is not a Riordan array since the $k$th column is not defined by ordinary generating functions of the form $gf^{k}$. Although $\tilde{T}$ is not Riordan, there are interesting combinatorial interpretations of $\tilde{T}$: the entries count the total number of Dyck $n$-paths with $k$ peaks, the row sums are the Catalan numbers $c_{n+1}$, and the diagonal sums are the RNA numbers $s_{n}$ (minus the leading $1$). Suggested exercises for the reader are to verify the row sums and diagonal sums. (The diagonal sums, sometimes called slices, move upward left-to-right within the array in a north-east direction.)

Finally, we make a brief note of the Stirling triangle, which contains the Stirling numbers of the second kind $S(n,k)$, the number of partitions of an $n$-set into $k$ blocks (nonempty subsets). The Stirling triangle is not a Riordan array, as we have defined in this article. However, since the exponential generating function for $S(n,k)$ is of the form $gf^k/k!$ where $g$ and $f$ are exponential generating functions and $k\geq 0$, the Stirling triangle is a so-called exponential Riordan array. For more information on exponential generating functions and exponential Riordan arrays, see B.

Algebra of the Riordan group

As mentioned earlier, the set of Riordan matrices form the Riordan group, which we will define and discuss in more detail in this section. We note that the Riordan group is also known as the Sheffer or 1-umbral group JLN. See SSB$^{+}$ for a connection between the Sheffer and Riordan groups. For an excellent introduction to the Riordan group and Riordan arrays, see Barry 4.

We now introduce Riordan matrix multiplication, starting with multiplication by a column vector. If $L=(g(z),f(z))$ is a Riordan matrix and $h\left( z\right)$ is the $GF$ associated with the infinite column vector $h=\left( h_{k}\right) _{k\geq 0}^{\top }$, where $\top$ denotes the transpose, then one can show that the matrix product $Lh$ is an infinite column vector whose associated $GF$ is $g\left( z\right) \cdot h\left( f\left( z\right) \right)$, where $g\cdot h$ denotes a Cauchy product and $h\left( f\right)$ denotes composition of $GFs$ SGWW. This statement is known as the fundamental theorem of Riordan arrays (FTRA) and it allows us to define multiplication of Riordan arrays in the following way.

Suppose $(g(z),f(z))$ is a Riordan matrix and $h(z)$ is a $GF$. We define the product

$$\begin{equation*} (g(z),f(z))\otimes h\left( z\right)\coloneq g\left( z\right) \cdot h\left( f\left( z\right) \right). \end{equation*}$$

Here, we have introduced the $\otimes$ symbol for use when writing the matrix product of a Riordan matrix, in terms of its associated generating function pair, and a column vector, in terms of its associated generating function. Note that the product represents the usual matrix multiplication. Next, we give some examples of properties of Riordan matrix-vector multiplication before moving on to multiplication of two Riordan matrices.

For example, the product of Pascal’s Triangle $P$ and $h\left( z\right) =1/\left( 1-z\right)$ associated with column vector $\left( 1,1,\ldots \right) ^{\top }$ is

$$\begin{align*} P\otimes h\left( z\right)&= \left( 1/\left( 1-z\right) ,z/\left( 1-z\right) \right) \otimes 1/\left( 1-z\right)\\ &= 1/\left( 1-2z\right). \end{align*}$$

This example is the well-known result where the row sums of $P$ are

$$\begin{equation*} \left[ z^{n}\right] 1/\left( 1-2z\right) =2^{n}\ \text{ for $n\geq 0$}. \end{equation*}$$

We now give some important $GFs$ of various sums of Riordan matrices that are obtained by multiplying by different column vectors SSB$^{+}$.

$$\begin{equation*} \begin{array}{l} \text{Row sums: }\\\left( g\left( z\right) ,f\left( z\right) \right) \otimes 1/\left( 1-z\right) = g\left( z\right) /\left( 1-f\left( z\right) \right) \\\text{Diagonal sums: }\\\left( g\left( z\right) ,zf\left( z\right) \right) \otimes 1/\left( 1-z\right) = g\left( z\right) /\left( 1-zf\left( z\right) \right) \\\text{Alternate sums: }\\\left( g\left( z\right) ,f\left( z\right) \right) \otimes 1/\left( 1+z\right) = g\left( z\right) /\left( 1+f\left( z\right) \right) \\\text{Weighted sums: }\\\left( g\left( z\right) ,f\left( z\right) \right) \otimes z/\left( 1-z\right) ^{2} = \displaystyle \frac{g\left( z\right)f\left( z\right)}{ \left( 1-f\left( z\right) \right)^{2}}\end{array} \end{equation*}$$

Recall that diagonal sums move upward left-to-right within the array in a north-east direction. For instance, in $P$ the fifth diagonal sum is $8=1+4+3+0+0+0$. The diagonal sums of all entries of a Riordan array $L=(g(z),f(z))$ are computed by the row sums of the “vertically stretched” Riordan array $\left( g\left( z\right) ,zf\left( z\right) \right)$. Vertically stretched Riordan arrays are not invertible because in this case the first three coefficients of $zf(z)$ are $f_{0}=0$, $f_{1}=0$ and $f_{2}\neq 0$. See Example 12 for an example of a vertically stretched Riordan array, and for a broader introduction to stretched Riordan arrays, see 4. Some suggested exercises are to show that the diagonal sums of $P$ are the Fibonacci numbers and the weighted row sums starting with leading coefficent $1$ are given by the $GF$ $g\left( z\right) /\left( 1-f\left( z\right) \right) ^{2}$. Weighted row sums correspond to the first moments or the expected value of each row of the Riordan matrix. For example, the first moments of $R^{\ast }$ are the bisected Fibonacci numbers given by $GF$ $1/\left( 1-3z+z^{2}\right)$ N1. A straight forward calculation shows

$$\begin{equation*} \left( s\left( z\right) ,zs\left( z\right) \right) \otimes 1/\left( 1-z\right) ^{2}=1/\left( 1-3z+z^{2}\right) \end{equation*}$$

where $s\left( z\right)$ is the RNA $GF$. However, the bisection formula can be applied to the Fibonacci generating function $F\left( z\right)$. For more information on the bisection formula, see SSB$^{+}$. The result is

$$\begin{equation*} s\left( z\right) /\left( 1-zs\left( z\right) \right) ^{2}=\left( F\left( \sqrt {z}\right) -F\left( -\sqrt {z}\right) \right) /2\sqrt {z}. \end{equation*}$$

This gives a nice relationship between the Fibonacci and RNA $GFs$.

Since FTRA is based on the usual row-by-column matrix multiplication, it can be extended to the matrix product of two Riordan matrices. Let $L=\left( g\left( z\right) ,f\left( z\right) \right)$ and $N=\left( h\left( z\right) ,l\left( z\right) \right)$ be Riordan matrices. Then the matrix product $LN$ is also a Riordan matrix which can be described as follows:

$$\begin{align*} LN &=\left( g\left( z\right) ,f\left( z\right) \right) \otimes \left( h\left( z\right) ,l\left( z\right) \right)\\ &=\left( g\left( z\right) \cdot h\left( f\left( z\right) \right) ,l\left( f\left( z\right) \right) \right) . \end{align*}$$

Note that, in the context of this article, a product of Riordan matrices, expressed without the “$\otimes$” symbol may be interpreted as the usual matrix multiplication.

Example 13.

An exercise for the reader is to show that $PC_{0}=M$ where $P$ is Pascal’s Triangle, $C_{0}=\left( c\left( z^{2}\right) ,zc\left( z^{2}\right) \right)$ is the “aerated” version of the Aigner-Catalan Riordan matrix from Example 8, and $M=\left( m\left( z\right) ,zm\left( z\right) \right)$ is the Motzkin Riordan matrix from Example 5. The entries of $C_{0}$ and $M$ count certain partial Motzkin paths 4, N2.

The set of all Riordan matrices forms a group under the operation of matrix multiplication SGWW. The identity element is $(1,z)$. This is the usual identity with ones along the main diagonal. The inverse of $(g(z),f(z))$ is $\left( 1/g(\bar{f}(z)),\bar{f}(z)\right)$ where $\bar{f}(z)$ is the compositional inverse of $f(z)$ such that $f(\bar{f})=z=\overline{f}\left( f\right)$. For example, the inverse of Pascal’s Triangle is

$$\begin{equation*} P^{-1}=\left( 1/\left( 1+z\right) ,z/\left( 1+z\right) \right) \end{equation*}$$

and the $(n,k)$th element of $P^{-1}$ is

$$\begin{equation*} [z^n]\frac{1}{1+z}\left(\frac{z}{1+z}\right)^k=(-1)^{n-k}\binom{n}{k}. \end{equation*}$$

A slightly more complicated example, where the compositional inverse is not as obvious to compute, is

$$\begin{equation*} \left( \left( 1-z\right) ,z\left( 1-z\right) \right) ^{-1}=C, \end{equation*}$$

where $C=\left(c(z),zc(z)\right)$ is the Aigner-Catalan array of Example 8. In many instances, finding $\bar{f}(z)$ can be laborous and complicated.

Example 14.

A nice application of $P$ and $P^{-1}$ involves the FTRA and the notion of binomial inversion (transform) of sequences. If $A\left( z\right)$ is the $GF\mathbf{\ }$of the generic sequence $\left\langle a_{n}\right\rangle _{n\geq 0}$, then the $GF$ of the binomial transform $\left\langle b_{n}\right\rangle _{n\geq 0}$ is given by

$$\begin{align*} B\left( z\right)& = P\otimes A\left( z\right)\\ &=\left( 1/\left( 1-z\right) \right) A\left( z/\left( 1-z\right) \right). \end{align*}$$

Similarly,

$$\begin{align*} A\left( z\right)& = P^{-1}\otimes B\left( z\right)\\ & = \left( 1/\left( 1+z\right) \right) B\left( z/\left( 1+z\right) \right). \end{align*}$$

As a result of this we have the classical binomial transform of sequences

$$\begin{equation*} b_{n}=\sum _{k=0}^{n}{\binom{n}{k}a_{k}}\Longleftrightarrow a_{n}=\sum _{k=0}^{n}{\binom{n}{k}\left( -1\right) ^{n-k}b_{k}}. \end{equation*}$$

Example 15.

Let $S$ and $W$ denote, respectively, column vectors associated with the sequences $\left\langle s_{n}\right\rangle _{n\geq 0}$ and $\left\langle w_{n}\right\rangle _{n\geq 0}$. Then $PW=S\Longleftrightarrow P^{-1}S=W$, where $P$ is Pascal’s Triangle. Suppose we want to find $W$ such that $S$ is the RNA numbers described in Example 11. Then, by the FTRA

$$\begin{align*} P^{-1}\otimes s\left( z\right)& = \left( 1/\left( 1+z\right) \right) s\left( z/\left( 1+z\right) \right) \end{align*}$$

where $s\left( z\right)$ is the RNA $GF$. Thus, $P^{-1}\otimes s\left( z\right)$ equals

$$\begin{equation*} \frac{ 1+z+z^{2}-\sqrt {1+2z-z^{2}-6z^{3}-3z^{4}}}{2z^{2}\left( 1+z\right)}= w\left( z\right) \end{equation*}$$

where $w\left( z\right)$ is the $GF$ associated with

$$\begin{equation*} \left\langle w_{n}\right\rangle _{n\geq 0}=\left\langle 1,0,0,1,-1,2,-1,1,3,-5,13,-13,\ldots \right\rangle . \end{equation*}$$

This curious sequence is not in the OEIS database S1. A suggested exercise is to show that $P\otimes w\left( z\right) =s\left( z\right)$. This gives a nice relationship between Pascal’s triangle and the RNA numbers. An interesting open problem is to find a combinatorial interpretation of this multiplication that involves lattice paths or RNA secondary structures from molecular biology.

There are many important subgroups of the Riordan group. We list a few special subgroups below:

$$\begin{equation*} \begin{array}[t]{ll} \text{Appell subgroup:} & \left( g(z),z\right) \\\text{associated subgroup} & \left( 1,f(z)\right) \\\text{Bell subgroup} & \left( g(z),zg\left( z\right) \right) \\\text{checkerboard subgroup} & \left( g_{e}(z),f_{o}\left( z\right) \right) \\\text{derivative subgroup} & \left( f^{\prime }(z),f\left( z\right) \right) \\\text{hitting time subgroup} & \left( zf^{\prime }(z)/f\left( z\right) ,f\left( z\right) \right) \end{array} \end{equation*}$$

Note that $g_{e}$ and $f_{o}$ are even and odd functions, respectively. $f^{\prime }(z)$ is the first derivative of $f\left( z\right)$. $P,B,C,C_{o},M$, and $R^{\ast }$ are elements of the Bell subgroup. In addition, $C_{o}$ is an element of the checkerboard subgroup and $P$ the hitting time subgroup. Interestingly, one can use the fact that

$$\begin{equation*} \left( g(z),f\left( z\right) \right) =\left( g(z),z\right) \otimes \left( 1,f\left( z\right) \right) \end{equation*}$$

to show that the Riordan group is a semi-direct product of the associated and Appell subgroups. For more algebraic properties of the Riordan group, see JLN.

Finally, we mention that Riordan matrices have recursive formulas for their entries, known as “formation rules.” A formation rule is a recurrence relation which describes how each entry in a Riordan matrix $L$ can be expressed as a linear combination of entries in the preceding rows. One common formation rule is denoted by $\left[ Z;A\right]$, which represents two recurrence relations that define the way entries of $L$ are computed. “$Z$” is a sequence of coefficients for a recurrence relation that describes the entries of the leftmost or zeroth column of $L$ and “$A$” is a sequence of coefficients for a recurrence relation that describes the entries of all other columns of $L$.

More precisely, the $Z$-sequence $Z=\left\langle z_{0},z_{1},\ldots \right\rangle$ $\left( z_{0}\neq 0\right)$ characterizes the zeroth column of $L=(\ell _{n,k})_{n,k\geq 0}$. This means every element $\ell _{n+1,0}$ can be expressed as a linear combination of all the elements in the preceding row by

$$\begin{equation*} \ell _{n+1,0}=z_{0}\ell _{n,0}+z_{1}\ell _{n,1}+\cdots =\sum _{j\geq 0}z_{j}\ell _{n,j}. \end{equation*}$$

The $A$-sequence $A=\left\langle a_{0},a_{1},\ldots \right\rangle$ $\left( a_{0}\neq 0\right)$ characterizes the other columns of $L$. In this case every element $\ell _{n+1,k+1}$ can be expressed as a linear combination of the elements in the preceding row, starting from the preceding column by

$$\begin{equation*} \ell _{n+1,k+1}=a_{0}\ell _{n,k}+a_{1}\ell _{n,k+1}+\cdots = \sum _{j\geq 0}a_{j}\ell _{n,k+j}. \end{equation*}$$

The $GFs$ of the $A$- and $Z$-sequences, respectively, are

$$\begin{equation*} A(z)=z/\bar{f}(z)\text{ and }Z\left( z\right) =1/\bar{f}(z)\left( 1-1/g\left( \bar{f}(z)\right) \right) \end{equation*}$$

where $\bar{f}(z)$ is the compositional inverse of $f\left( z\right)$ 4. For example, the formation rule of the Shapiro-Catalan Riordan matrix $B$ is $\left[ 2,1;1,2,1\right]$ where $Z\left( z\right) =2+z$ and $A\left( z\right) =1+2z+z^{2}$. In general, the entries are computed by $\ell _{n+1,0}=2\ell _{n,0}+\ell _{n,1}$ and $\ell _{n+1,k+1}=\ell _{n,k}+2\ell _{n,k+1}+\ell _{n,k+2}$. See MRSV, R for more information on the $A$- and $Z$-sequences.

Riordan matrix method and lattice path counting

One can use Riordan matrices to solve many kinds of lattice path enumeration problems. A typical method for using Riordan matrices to count lattice paths, as well as other combinatorial objects, is outlined by the following steps:

(1)

Count a few cases for the objects and observe some counting numbers.

(2)

Set up the counting numbers as a lower-triangular matrix $M$.

(3)

Find a pattern in the way the entries of $M$ are computed.

(4)

Use the pattern (formation rules) to conjecture/define $M$ as a Riordan matrix $L$.

(5)

Find the generic element of $L$.

(6)

Use the generic element or formation rules to prove combinatorially that $L$ counts the objects.

(7)

Compute $L\otimes \left( 1/\left( 1-z\right) \right)$ to find the total number of combinatorial objects.

We now apply the Riordan matrix method to a particular lattice path counting problem. The problem was previously solved in N2. However, in this survey we provide more details and improve the presentation of the solution.

We wish to count paths in $\mathbb{Z} ^{2}$ that begin at the origin $\left( 0,0\right)$, remain in the upper $xy$ plane, follow the step set

$$\begin{equation*} \acute{S}=\left\{ N\left( 0,1\right),S\left( 0,-1\right),R\left( 1,0\right),\overline{L}\left( -1,0\right)\right\} \end{equation*}$$

with north $\left( N\right)$, south $\left( S\right)$, right $\left( R\right)$, and left $\left( \overline{L}\right)$ unit steps, and satisfy the following restrictions: (1) no path passes below the $x$-axis, (2) there are no paths with consecutive $N$ and $S$ steps, i.e., there are no $NS$ steps, (3) no paths begin with an $\overline{L}$ step, (4) all $\overline{L}$ steps touch and remain on the $x$-axis. Then, we call these paths $NSR\overline{L}$ paths. Let $R_{1}^{\ast }=\left( \rho _{n,k}\right) _{n,k\geq 0}$ where $\rho _{n,k}$ denotes the number of $NSR\overline{L}$ paths of length $n$ that end at height $k$. Recall that the height corresponds to the $y$ value of the endpoint $\left( x,y\right)$ of the path. A typical path of length $10$ and height $1$ is denoted by the word

$$\begin{equation*} R\overline{L}RR\overline{L}NRS\overline{L}N. \end{equation*}$$

We want to find the total number of $NSR\overline{L}$ paths. Start by counting the number of $NSR\overline{L}$ paths of length $n$ that end at height $k$ for the first few cases where $n,k\leq 5$ and obtain the following lower-triangular matrix

$$\begin{equation*} R_{1}^{\ast }=\left( \begin{array}{cccccc} 1 & & & & & \\1 & 1 & & & & \\2 & 2 & 1 & & & \\5 & 4 & 3 & 1 & & \\12 & 10 & 7 & 4 & 1 & \\\mathbf{29} & \mathbf{25} & \mathbf{18} & \mathbf{11} & \mathbf{5} & \mathbf{1}\end{array}\right) . \end{equation*}$$

Then, we find the following patterns for the entries of $R_{1}^{\ast }$. We observe that the leftmost (or zeroth) column entry $\mathbf{29}$ is computed by

$$\begin{equation*} \mathbf{29}=\underline{2}\cdot 12+\underline{1}\cdot 4+\underline{1}\cdot 1+\underline{1}\cdot 0+\underline{1}\cdot 0. \end{equation*}$$

All other leftmost column entries seem to follow this same pattern (formation rule), that is, the same linear combination of respective entries from the preceding rows. We now observe the other columns entries. Observe that $\mathbf{18}$ is computed by

$$\begin{equation*} \mathbf{18}=\underline{1}\cdot 10+\underline{1}\cdot 7+\underline{1}\cdot 1+\underline{1}\cdot 0+\underline{1}\cdot 0. \end{equation*}$$

All other bold entries in the other columns (not the leftmost) seem to follow this pattern. Thus, we conjecture this pattern (formation rule) and make the assumption that the $\left( n,k\right)$-th entry of $R_{1}^{\ast }$ is formed by the following recurrence relations. The leftmost or zeroth column is formed for $\rho _{0,0}=1$, $\rho _{1,0}=1$, and $n\geq 1$

$$\begin{equation*} \rho _{n+1,0}=2\rho _{n,0}+\sum _{k\geq 1}{\rho _{n-k,k}}. \end{equation*}$$

The other columns are formed for $n,k\geq 1$

$$\begin{align*} \rho _{n+1,k}&=\rho _{n,k-1}+\sum _{j\geq 0}{\rho _{n-j,k+j}}\\ &=\rho _{n,k-1}+\rho _{n,k}+\cdots . \end{align*}$$

As previously computed, one can easily confirm $\rho _{5,0}=29$ and $\rho _{5,2}=18$.

From the recurrence relations, we will derive explicit $GFs$ whose coefficients are the column entries of $R_{1}^{\ast }$. Following the matrix formation rules, the definition of a Riordan matrix, and making adjustments to properly align the coefficents, the $k$th column $GF$ of $R_{1}^{\ast }$ is defined for $k\geq 1$ as

$$\begin{equation*} g\cdot f^{k}=zgf^{k-1}+z\left( gf^{k}+zgf^{k+1}+z^{2}gf^{k+2}+\cdots \right) . \end{equation*}$$

Solving for $f$ gives

$$\begin{equation*} f=zf^{2}+\left( z-z^{2}\right) f+z. \end{equation*}$$

Now, we solve $f$ in terms of $f\left( z\right)$ and apply the quadratic formula to obtain $f\left( z\right) =zs\left( z\right)$ where $s\left( z\right)$ is the RNA $GF$. Similarily, the leftmost column $GF$ of $R_{1}^{\ast }$ is defined as

$$\begin{equation*} g=1+z\left( 2g+zgf+z^{2}gf^{2}+\cdots \right) . \end{equation*}$$

Using geometric series and simplifying,

$$\begin{equation*} \begin{array}[t]{ccc} g & = & 1+2zg+z^{2}gf+z^{3}gf^{2}+\cdots \\& = & 1+2zg+z^{2}gf\cdot \left( 1+zf+z^{2}f^{2}+\cdots \right) \\& = & 1+2zg+z^{2}gf\cdot \left( 1/\left( 1-zf\right) \right) \\& = & \left( 1-zf\right) /\left( 1-2z-zf+z^{2}f\right) .\end{array} \end{equation*}$$

Now, we solve $g$ in terms of $g\left( z\right)$ and substitute $f\left( z\right) =zs\left( z\right)$ to obtain

$$\begin{equation*} g\left( z\right) =\left( 1-z^{2}s\left( z\right) \right) /\left( 1-2z-z^{2}s\left( z\right) +z^{3}s\left( z\right) \right) . \end{equation*}$$

Simplifying,

$$\begin{equation*} g\left( z\right) = \frac{ 1-z}{2z} \left(\frac{ 1-3z+z^{2}-\sqrt {\triangle }}{ -1+3z-z^{2}}\right), \end{equation*}$$

where $\triangle =1-2z-z^{2}-2z^{3}+z^{4}$. This confirms the pattern (formation rule) and we conjecture that $R_{1}^{\ast }$ is the Riordan matrix defined by the $GFs$ derived from the recurrence relations. Thus,

$$\begin{equation*} R_{1}^{\ast }=\left( \frac{ 1-z}{ 2z} \left( \frac{1-3z+z^{2}-\sqrt {\triangle }}{ -1+3z-z^{2}} \right) ,zs\left( z\right) \right) . \end{equation*}$$

We now give combinatorial arguments that show that the entries of $R_{1}^{\ast }$ model the lattice path counting problem earlier described in this section. We want to find the total number of $NSR\overline{L}$ paths of length $n$ ending at height $k$. We will connect the entries of $R_{1}^{\ast }$ to the paths by showing the paths satisfy the recurrence relations. To do this we consider the following combinatorial arguments. Consider an $NSR\overline{L}$ path of length $n$ ending at height $k$. To form a new path of length $n+1$ of height $k$, we consider the following cases. Case 1: Given a path of length $n$ ending at height $k-1$, there is one choice to move the path up to height $k$, a north step $N$. Thus, if the last step is $N$, there are $1\cdot \rho _{n,k-1}$ possibilities to construct a new path ending at height $k$. In this case, all paths with last step $N$ are counted by $\rho _{n,k-1}$. Case 2: Given a path of length $n$ ending at height $k$, there is one choice for the path to remain at height $k$, a right step $R$. Thus, if the last step is $R$, there are $1\cdot \rho _{n,k}$ possibilities to construct a new path ending at height $k$. In this case, all paths with last step $R$ are counted by $\rho _{n,k}$. Case 3: For $j\geq 0$, given a path of length $n-j$ ending at height $k+j$, there is one choice of $j$ south steps to move the path down to height $k$. Thus, there are $1\cdot \rho _{n-j,k+j}$ possibilities to construct a new path ending at height $k$. In this case, all paths with $j$ south steps are counted by $\rho _{n-j,k+j}$. For $k>0$ there are no paths with a last left step $\overline{L}$ since $\overline{L}$ steps touch and remain on the $x$-axis. Now, summing all cases gives all possible ways to construct a new path of lenth $n+1$ ending at height $k$. Therefore, the recurrence relation for the other columns of $R_{1}^{\ast }$ counts all $NSR\overline{L}$ paths of length $n$ ending at height $k\geq 1$. By similar arguments, we can show that the leftmost column of $R_{1}^{\ast }$ counts all paths of length $n$ ending at height $k=0$. This proves the formation rule and gives $R_{1}^{\ast }$ a $NSR\overline{L}$ lattice path interpretation.

To find the total number of $NSR\overline{L}$ paths, we apply the FTRA and compute the row sums by

$$\begin{equation*} R_{1}^{\ast }\otimes \left( 1/\left( 1-z\right) \right) . \end{equation*}$$

Simplifying, the total number of $NSR\overline{L}$ paths is given by

$$\begin{align*} R_{1}^{\ast }\otimes \left( 1/\left( 1-z\right) \right) &=\left( 1-z\right) /\left( 1-3z+z^{2}\right)\\ &=\sum _{n\geq 0}{\rho _{n}z^{n}}\eqcolon BF \left( z\right) \end{align*}$$

where the $n$th coefficient is computed by the following sums A2

$$\begin{equation*} \left[ z^{n}\right] BF \left( z\right) =1+\sum _{k=0}^{n}F _{2k}=\sum _{k=0}^{n}{\binom{2n-k}{k}}. \end{equation*}$$

For example,

$$\begin{align*} \left[ z^{3}\right] BF \left( z\right) &=1+\sum _{k=0}^{3}F _{2k}\\ &=13=\rho _{3}. \end{align*}$$

Thus, the total number of $NSR\overline{L}$ paths are counted by the bisected Fibonacci numbers with generating function $BF \left( z\right)$. The number of Dyck paths of length $2n$ and height at most $3$ are also counted by these bisected Fibonacci numbers. A suggested exercise is to find an explicit bijection between these two sets of paths. See OEIS S1 sequence number $A001519$ for other combinatorial objects enumerated by the counting numbers $\left\langle \rho _{n}\right\rangle _{n\geq 0}$.

Generalized Catalan paths and Riordan matrices

The Riordan matrix method can be readily used to study statistics on lattice paths and other combinatorial objects. In this final section, we give some illustrations of how Riordan matrices can be leveraged to study statistical distributions of generalized lattice paths and to observe combinatorial relationships among higher-dimensional lattice paths.

A frequent example of lattice paths are the so-called Catalan paths, which are equivalent to ballot numbers and Dyck paths. A Catalan path is a path starting from the origin $(0,0)$, using $n$ steps of the form $(1,0)$ and $n$ steps of the form $(0,1)$, that does not go above the line $y=x$. Catalan paths are equivalent to Dyck $n$-paths, as described in Example 1. The number of Dyck $n$-paths that end at height $k$ is given by the $(n,k)$th entry of the (aerated) Catalan matrix $C_0=\left(c(z^2),zc(z^2)\right)$.

Catalan paths can be generalized in a variety of ways to obtain other interesting lattice paths associated with well-known combinatorial sequences. For instance, $t$-Dyck paths are paths of length $tn$ from $(0,0)$ to $(tn,0)$, where $t> 0$, that use up steps $U$ of the form $(1,1)$ and down steps $D$ of the form $(1,-t+1)$ and do not go below the $x$-axis. When $t=2$, we have Dyck paths while the paths we obtain when $t=3$ are called ternary paths which are counted by the ternary numbers $\frac{1}{2n+1}\left({{3n}\atop {n}}\right)$ with generating function $T(z)$ satisfying $T(z)=1+zT^3(z)$.

A $t$-Dyck path can also be thought of as a path starting from the origin $(0,0)$ that uses $n$ steps of the form $(1,0)$ and $(t-1)n$ steps of the form $(0,1)$ that does not go above the line $y=(t-1)x$. In general, $t$-Dyck paths are counted by the Fuss–Catalan numbers $\frac{1}{(t-1)n+1}\left({{tn}\atop {n}}\right)$.

One may be interested in enumerating certain properties of these generalized lattice paths, such as the number of peaks, valleys, returns, or hills. A return in a Dyck path is a non-origin point on the path that intersects the $x$-axis. The Riordan matrix $C=\left(c(z), zc(z)\right)$, from Example 8, counts the number of Catalan paths of length $2(n+1)$ having exactly $k+1$ returns to the $x$-axis. A quick computation of $(c(z),zc(z))\otimes \frac{1}{1-z}$ verifies that the row sums of $\left(c(z), zc(z)\right)$ indeed count the total number of Catalan paths of length $2(n+1)$. Moreover, the computation of

$$\begin{equation*} \frac{[z^n]\left(c(z),zc(z)\right) \otimes \frac{1}{(1-z)^2}}{[z^n]c(z)} \end{equation*}$$

produces the average number of returns among Dyck $n$-paths. An exercise for the reader is to perform this computation and show that the average number of returns among Dyck $n$-paths approaches $3$ as $n\to \infty$.

Similarly, the total number of returns among ternary paths of length $3n$ is given by

$$\begin{equation*} \left(1,z\left(T(z)\right)^2\right)\otimes \frac{z}{(1-z)^2}=z\left(T(z)\right)^4. \end{equation*}$$

Hence, the expected number of returns among ternary paths is

$$\begin{equation*} \frac{[z^n]z\left(T(z)\right)^4}{[z^n] T(z)}=\frac{2n}{n+1}, \end{equation*}$$

which approaches 2 as $n\to \infty$. Furthermore, one can use these methods to show that the probability that a randomly chosen ternary path has exactly $k$ returns approaches $\frac{4k}{3^{k+1}}$ and that the expected number of returns among nontrivial $t$-Dyck paths approaches $\frac{t+1}{t-1}$ with variance $\frac{2t}{(t-1)^2}$. Ultimately, these results lead to the fact that the number of returns among $t$-Dyck paths approaches a negative binomial distribution with parameters $2$ and $\frac{t-1}{t}$. CM

A hill in a $t$-Dyck path is a subsequence of the form $U^{t-1}D$ such that the preceding sequence of steps form a $t$-Dyck path. The number of Dyck $n$-paths having exactly $k\geq 0$ hills is given by the Riordan array $\left(\tilde{f}(z),z\tilde{f}(z)\right)$ where

$$\begin{equation*} \tilde{f}(z)=\frac{1-\sqrt {1-4z}}{z\left(3-\sqrt {1-4z}\right)}=\frac{c(z)}{1+zc(z)} \end{equation*}$$

is the $GF$ for the Fine numbers $\langle \tilde{f}_n \rangle _{n\geq 0}= \langle 1,0,1,2,6,18,57,186,\dots \rangle$. Dyck paths having no hills, known as Fine paths, are counted by the Fine numbers. The reader may verify as an exercise that the total number of hills among Dyck $n$-paths is given by

$$\begin{equation*} [z^n]\left(\tilde{f}(z),z\tilde{f}(z)\right) \otimes \frac{z}{(1-z)^2}=c(z)-1, \end{equation*}$$

which implies that the expected number of hills among Dyck $n$-paths is exactly $1$. This result suggests that there is a bijection between the set of Dyck $n$-paths and the set of hills among all Dyck $n$-paths. One nice bijection can be described as follows. Given the hill $\underline{UD}$ in a Dyck $n$-path of the form $S_1\underline{UD}S_2$, where $U$ is an up step, $D$ is a down step, and $S_1,S_2$ are Dyck paths of semilength at most $n$, map the hill $\underline{UD}$ to the Dyck $n$-path $US_1DUS_2$. It should be clear that the mapping is injective, and since every Dyck $n$-path can be described in the latter form, the mapping is surjective.

More generally speaking, similar methods on the generalized Fine array $\left(\tilde{f}_t(z),z\tilde{f}_t(z)\right)$, where $\tilde{f}_t(z)$ is the $GF$ for the number of $t$-Dyck paths having no hills, can be used to show that the number of hills among $t$-Dyck paths of length $tn$ has expected value

$$\begin{equation*} \frac{2((t-1)n+1)^{\underline{t-2}}}{t(tn-1)^{\underline{t-2}}}, \end{equation*}$$

where $t^{\underline{j}}\coloneq t(t-1)\cdots (t-j+1)$, and approaches a negative binomial distribution with parameters $2$ and $\frac{t^{t-1}}{t^{t-1}+(t-1)^{t-2}}$ CM.

As mentioned previously, lattice paths from $(0,0)$ to $(n,0)$ that use up steps of the form $(1,1)$, down steps of the form $(1,-1)$, and level steps of the form $(1,0)$ are known as Motzkin paths, which are counted by the Motzkin numbers. When we allow two possible colors for the level step, the resulting paths, which we will call $2$-colored Motzkin paths, are counted by the Catalan numbers with generating function $c^2(z)$. In fact, the $(n,k)$th entry of the Bell subgroup Riordan matrix $B=\left(c^2(z), zc^2(z)\right)$, from Example 9 is the number of these $2$-colored Motzkin paths of length $n$ having terminal height $k$. Recall that a formation rule for $\left(c^2(z), zc^2(z)\right)$ is $[2,1;1,2,1]$. Another lattice path interpretation of the array $\left(c^2(z), zc^2(z)\right)$ is the number of Dyck paths of length $2n+1$ that go from $(0,0)$ to $(2n+1, 2k+1)$.

On the other hand, ternary paths of length $3n+1$ that go from $(0,0)$ to $(3n+1,3k+1)$ are counted by the Bell subgroup matrix $\left(T^3(z), zT^3(z)\right)$ where $T(z)$ is the $GF$ for the ternary numbers. The formation rule for $\left(T^3(z), zT^3(z)\right)$ is $[3,3,1;1,3,3,1]$. Given this formation rule, it is not hard to see that the $(n,k)$th entry of $\left(T^3(z), zT^3(z)\right)$ also counts paths from $(0,0)$ to $(n,k)$ that never go below the $x$-axis and use the following 8 types of steps: $U(1,1)$, $L_1(1,0)$, $L_2(1,0)$, $L_3(1,0)$, $D_1(1,-1)$, $D_2(1,-1)$, $D_3(1,-1)$. There is a natural bijection between these paths and the aforementioned ternary paths.

More generally, the Bell subgroup matrix whose formation rule is determined by the $t$th row of Pascal’s triangle will count lattice paths of length $tn+1$ that go from $(0,0)$ to $(tn+1,tk+1)$ and use up steps of the form $(1,1)$ and down steps of the form $(1,-t+1)$ that never go below the $x$-axis. And furthermore, this same matrix will count paths from $(0,0)$ to $(n,k)$ that never go below the $x$-axis and use $2^t$ possible steps, each of the form $L_i(1,-k+1)$ where $k=0,1,\dots t$ for some $i$ between $1$ and $\binom{t}{k}$. Given that there are natural bijections between these two different path interpretations, it would be interesting to explore through the Riordan matrix method how certain statistics may translate between these lattice path interpretations and how the resulting statistical distributions compare.

As a final illustration of the vast connections between lattice path enumeration and Riordan matrices, we present two open problems related to higher-dimensional lattice paths and generalized Riordan arrays.

Consider the generalized Riordan matrix

$$\begin{equation*} R_{t}^{\ast }=\left( \left( \left( 1-z\right) /\left( 1-zs\left( z\right) \right) \right) ^{t}s\left( z\right) ,zs\left( z\right) \right) \end{equation*}$$

where $s\left( z\right)$ is the RNA $GF$. Note that $R^{\ast }$ and $R_{1}^{\ast }$ are special cases where $t=0$ and $t=1$, and for $t=2$, we have

$$\begin{equation*} R_{2}^{\ast }=\left( \left( 1-2z+z^{2}\right) /\left( 1-3z+z^{2}\right) ,zs\left( z\right) \right) . \end{equation*}$$

Interesting open problems are to find lattice path interpretations of the generalized Riordan matrix $R_{t}^{\ast }$ for $t\geq 2$. In Figure 4, there is a nice example of an infinite two-dimensional array made up of products of Riordan matrices that involve Pascal’s triangle $P$ and the “aerated” Aigner-Catalan matrix $C_0=(c(z^2),zc(z^2))$. The infinite array denoted by $£_{t,\nu }=P^{t}C_{0}E^{\nu }$ constructed in N2 is a triple product of Riordan matrices where $E^{\nu }=\left( 1/\left( 1-z\right) ^{\nu },z\right)$. Some interesting matrices that appear in $£_{t,\nu }$ are the Pascal, Catalan, Motzkin, hexagonal (Hex), and directed animal arrays. Solutions of certain higher-dimensional lattice path counting problems are known for the first two columns of this infinite two-dimensional array, but less is known about the remaining columns. Thus, $£_{t,\nu }$ is of combinatorial interest. See N2 for more information on Riordan matrices and generalized lattice paths.

Figure 4.

Each entry is a product of Riordan matrices $£_{t,\nu }=P^{t}C_{0}E^{\nu }\text{ }$, where $P$ is Pascal’s triangle, $C_0$ is a special Shapiro-Catalan array and ${E}$ is the lower-triangular array whose entries equal $1$.

$$\begin{equation*} \begin{array}{lllllll} C_{0} & \rightarrow & C_{0} {E} & \rightarrow & C_{0} {E}^{2} & \rightarrow & \cdots \\\downarrow & & \downarrow & & \downarrow & & \\PC_{0} & \rightarrow & PC_{0} {E} & \rightarrow & PC_{0} {E}^{2} & \rightarrow & \cdots \\\downarrow & & \downarrow & & \downarrow & & \\P^{2}C_{0} & \rightarrow & P^{2}C_{0} {E} & \rightarrow & P^{2}C_{0}{E}^{2} & \rightarrow & \cdots \\\downarrow & & \downarrow & & \downarrow & & \\P^{3}C_{0} & \rightarrow & P^{3}C_{0} {E} & \rightarrow & P^{3}C_{0}{E}^{2} & \rightarrow & \cdots \\\downarrow & & \downarrow & & \downarrow & & \\\vdots & & \vdots & & \vdots & & \end{array} \end{equation*}$$

$£_{t,\nu }$ is the Riordan matrix

$$\begin{equation*} £_{t,\nu }=\left( k_{t}\left( z\right) /\left( 1-zk_{t}\left( z\right) \right) ^{\nu },zk_{t}\left( z\right) \right) \end{equation*}$$

where

$$\begin{align*} k_{t}\left( z\right) &=\left( 1-tz-\sqrt {1-2tz+\left( t^{2}-4\right) z^{2}}\right) /2z^{2} \\ &=\left( 1/\left( 1-tz\right) \right) c\left( \left( z/\left( 1-tz\right) \right) ^{2}\right) \end{align*}$$

and $c\left( z\right)$ is the Catalan $GF$. Thus, $£_{t,\nu }$ is a generalized Catalan Riordan matrix. See Figure 4 for the first few entries of $£_{t,\nu }$. Surprisingly, by moving down the leftmost column of $£_{t,\nu }$ a solution of Sands’s problem is found in N2. In addition, Sands’s problem was extended to higher dimensions in $\mathbb{Z} ^{d}$ for $d>3$ where there are countably many step directions and the paths never pass below the $\left( d-1\right) th$ hyperplane $x_{1}+\cdots +x_{d-1}=0$. The height of each higher-dimensional path corresponds to the value $x_{d}$ of the endpoint $\left( x_{1},\ldots ,x_{d}\right)$ of the path. The step sets of the higher-dimensional paths are defined in N2. Another subclass of paths called generalized (or partial-t) Motzkin walks are also counted by the entries of the leftmost column. In the same paper N2, higher-dimensional path results were also obtained by moving down the first column of $£_{t,\nu }$. By moving down the first column, surprisingly, a more restrictive subset of Sands type paths called power walks are obtained. These paths are generalized to higher dimensions and a Motzkin analog is given N2. An interesting open problem is to find a higher-dimensional lattice path interpretation of the matrix entries $P^{t}C_{0}E^{2}$ of the second column of $£_{t,\nu }$. There is not much known about $£_{t,\nu }$ for column entries for $\nu \geq 2$.