Motzkin paths, Schröder paths, the Motzkin numbers $M_n$, the large Schröder numbers $R_n$, and their generating functions

Put $U=(1,1)$, $D=(1,-1)$, $L=(1,0)$ and $L_2=(2,0)$, and recall the lattice paths of Lattice paths, step sets and step words. For a lattice path $v$ of length $\mathrm{\ell }$ write $h(i)$ for the second coordinate of $v(i)$ and $x(i)$ for its first coordinate.

Definition. Let $n\in \mathbb{N}$.

• A Motzkin path of length $n$ is a lattice path of length $n$ with steps in $\{U,D,L\}$ from $(0,0)$ to $(n,0)$ with $h(i)\ge 0$ for every $i\le n$. Write ${\mathrm{M}\mathrm{o}\mathrm{t}}_n$ for the set of them.
• A Schröder path of half-length $n$ is a lattice path with steps in $\{U,D,L_2\}$ from $(0,0)$ to $(2n,0)$, of any length, with $h(i)\ge 0$ for every index $i$. Write ${\mathrm{S}\mathrm{c}\mathrm{h}}_n$ for the set of them.

Each step of a Motzkin path advances the first coordinate by exactly $1$, so a Motzkin path of length $n$ automatically ends at first coordinate $n$; this is the same induction as in Diagonal lattice paths with steps $U=(1,1)$ and $D=(1,-1)$, and the height function. A Schröder path has a step of width $2$, so its length is not determined by $n$ and is recorded below.

Counting the steps of a Schröder path. Let $v\in {\mathrm{S}\mathrm{c}\mathrm{h}}_n$ have $k$ up steps, $k^{\mathrm{\prime }}$ down steps and $m$ level steps. Each $U$ raises $h$ by $1$, each $D$ lowers it by $1$ and each $L_2$ leaves it unchanged, so induction on the index (The principle of mathematical induction) gives $h(i)$ as the number of $U$ steps among the first $i$ minus the number of $D$ steps among them; from $h=0$ at the last index we get $k^{\mathrm{\prime }}=k$. Likewise the first coordinate of $v(i)$ is the number of $U$ and $D$ steps among the first $i$ plus twice the number of $L_2$ steps among them, so $2n=2k+2m$ and $m=n-k$. Hence

$0\le k\le n,\text{and }v\text{ has exactly }n+k\text{ steps},$

of which $2k$ are not level. In particular the length of a Schröder path of half-length $n$ is at most $2n$.

Both sets are finite, and the two counts are therefore defined. By For each start point the step word is a bijection onto $S^n$ the paths of a given length $\mathrm{\ell }$ from $(0,0)$ with steps in a three-element step set form a finite set of $3^{\mathrm{\ell }}$ elements. So ${\mathrm{M}\mathrm{o}\mathrm{t}}_n$ is a subset of a finite set and is finite (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$); and ${\mathrm{S}\mathrm{c}\mathrm{h}}_n$ is a subset of the union of the finitely many sets of paths of length $\mathrm{\ell }$ for $\mathrm{\ell }\le 2n$, which is finite by The sum rule: a finite disjoint union is finite with $\mid A\cup B\mid =\mid A\mid +\mid B\mid$ and $\mid {\bigcup }_{i\in I}{A}_i\mid ={\sum }_{i\in I}\mid A_i\mid$, and a sum over a finite index set splits along a partition because paths of different lengths are functions with different domains, so ${\mathrm{S}\mathrm{c}\mathrm{h}}_n$ is finite as well. Define

$M_n:=\mid {\mathrm{M}\mathrm{o}\mathrm{t}}_n\mid ,R_n:=\mid {\mathrm{S}\mathrm{c}\mathrm{h}}_n\mid$

(The cardinality $\mid A\mid$ of a finite set), the Motzkin numbers and the large Schröder numbers. Both are defined as counts, and every formula for them below is a theorem.

Small values, read off the definition. At $n=0$ both conditions leave only the empty path at $(0,0)$, so $M_0=1$ and $R_0=1$. For $M_1$: a single step from $(0,0)$ to $(1,0)$ must be $L$, since $U$ ends at height $1$ and $D$ at height $-1$, so $M_1=1$. For $M_2$: the words $LL$ and $UD$ qualify, and $DU$ fails the height condition at the middle vertex, so $M_2=2$. For $R_1$: a path from $(0,0)$ to $(2,0)$ is $L_2$ or $UD$, and $DU$ fails the height condition, so $R_1=2$.

The two generating functions. In $\mathbb{Q}\mathrm{⟦}x\mathrm{⟧}$ (Formal power series over a commutative ring and the coefficient-extraction functional $[x^n]$) put

$M(x):={\sum }_{n\ge 0}{M}_n{x}^n,R(x):={\sum }_{n\ge 0}{R}_n{x}^n,$

each count read as a rational coefficient exactly as in The Catalan generating function $C(x)={\sum }_{n\ge 0}{C}_n{x}^n$ in $\mathbb{Q}\mathrm{⟦}x\mathrm{⟧}$; two series are equal exactly when all their coefficients agree (Coefficient extraction is $R$-linear, separates formal series, shifts under multiplication by $x^k$, and converts products to finite convolution).

• The indeterminate marks length in $M(x)$ and half-length in $R(x)$. That is the indexing of the source, and it is what makes the two functional equations below differ in the power of $x$ multiplying the square: a $U$ and a $D$ consume two units of length but only one unit of half-length. Reading either series with the other convention gives a false equation.

• The letter $R$ for the large Schröder numbers is a deliberate departure. The source writes $S_n$; here $S$ already names a step set (Lattice paths, step sets and step words) and $S_a$ the periodic partial-sum function (Cyclic shifts of an integer word and its periodic partial-sum function), so the numbers are written $R_n$ and the paths ${\mathrm{S}\mathrm{c}\mathrm{h}}_n$. Nothing else about the source's convention is changed: $R_n$ counts the Schröder paths of half-length $n$, so $R_0=1$ and $R_1=2$.

• Why the finiteness clause treats the two cases differently. A Motzkin path of length $n$ has exactly $n$ steps, so one word length suffices. A Schröder path of half-length $n$ has $n+k$ steps, and $k$ is not determined by $n$; the bound $2n$ is what makes the union above finite, and it is attained exactly when the path has no level step.