Grand Motzkin paths and $\{0,1,2\}$-trees — a simple bijection

1. Introduction

Motzkin paths appear first in [6]. In the encyclopedia [9] they are enumerated by sequence A001006, with many references given. They consist of up-steps $U=(1,1)$, down-steps $D=(1,-1)$ and horizontal (flat) steps $F=(1,0)$. They start at the origin and must never go below the $x$-axis. Usually one requires the path to end on the $x$-axis as well, but occasionally one uses the term Motzkin path also for paths that end on a different level. Figure 1 shows all Motzkin paths of 4 steps (=length 4).

The enumeration of Motzkin paths is done using the generating function $M=M(z)$ and a decomposition according to the first return to the $x$-axis, viz. $$M=1+zM+z^2{M}^2,$$ this can be found in many books, e.g. in [5]. Solving, $$M(z)=\frac{1-z-\sqrt{1-2z-3z^2}}{2z^2}.$$

The other combinatorial structure that plays a role in this note are ordered trees. They are enumerated by an equation for the generating function (according to the number of nodes) $$P=z+zP+z{P}^2+z{P}^3+\cdots =\frac{z}{1-P}\text{andtherefore}P=P(z)=\frac{1-\sqrt{1-4z}}{2}.$$ The subclass of $\{0,1,2\}$-trees of interest only allows outdegrees $0,1,2$ and so we get again a generating function $$Q=z+zQ+z{Q}^2\text{and therefore}Q=Q(z)=\frac{1-z-\sqrt{1-2z-3z^2}}{2z}=zM(z).$$ So there should be a bijection of $\{0,1,2\}$-trees with $n+1$ nodes (= $n$ edges) and Motzkin paths of length $n$; the simplest I know is from [3]:

One runs through the $\{0,1,2\}$-tree in pre-order; if one sees an edge for the first time, one translates a single edge (degree 1) into a flat step, a left edge into an up-step and a right edge into a down-step. It is easy to see that the process is reversible, which is the desired bijection.

2. Grand Motzkin paths

As a first step, we need the generating function of Motzkin paths, ending on level $k$, not just the usual case $0$. This is a standard argument, by decomposing such a path according to the last time you visit level $0$, then an up-step, and we wait until we visit level $1$ for the last time, and so one.

From this we find the generating function as $z^k{M}^{k+1}$. This is well-known.

Now we come to Grand Motzkin paths, a notation I picked up from [4]. This more general family has the same steps as Motzkin paths, returns to the $x$-axis at the end, but the condition that the paths must stay (weakly) above the $x$-axis is dropped.

Let $k$ be the unique negative number such that the Grand Motzkin paths reaches the level $-k$ when going from left to right; for $k=0$ they are just ordinary Motzkin paths. We consider the first such point $(a,-k)$ and the last such point $(b,-k)$; it is possible that $a=b$. Then the paths decomposes canonically into 3 parts:

This decomposition produces the generating function of such paths as a product of 3 terms: The first part corresponds to $z\cdot z^{k-1}{M}^k$ (the last step must be a down-step), the second part to $M$, and the third part again to $z\cdot z^{k-1}{M}^k$ (the first step must be an up-step). The product is then $z^{2k}{M}^{2k+1}$. Summing over all possible values of $k$, the enumeration of Grand Motzkin paths is done via the generating function $$M+\sum _{k\ge 1}{z}^{2k}{M}^{2k+1}=\sum _{k\ge 0}{z}^{2k}{M}^{2k+1}=\frac{1}{\sqrt{1-2z-3z^2}}.$$

In the world of $\{0,1,2\}$-trees, we form a new super-root, with $2k+1$ successors, each of which is a $\{0,1,2\}$-tree. The generating function is then $$z\sum _{k\ge 0}{Q}^{2k+1}=z^2\sum _{k\ge 0}{z}^{2k}{M}^{2k+1}=\frac{z^2}{\sqrt{1-2z-3z^2}}.$$

The previous bijection takes over to the new situation: if a grand Motzkin path consists of $2k+1$ ordinary Motzkin paths, then each of them corresponds to a $\{0,1,2\}$-tree as before. The extra factor $z^2$ stems from the fact that for $\{0,1,2\}$-trees, the edges correspond to the steps. And now, there is the super-root, which should not be counted when considering the corresponding Grand Motzkin path.

The paper [8] has a correspondence between Grand Motzkin paths and $\{0,1,2\}$-trees with a super-root with an odd number of successors. However the arguments are perhaps less direct than the present ones.

3. Trinomial coefficients and enumeration

The trinomial coefficients (notation from Comtet [1]) are given by $$(\genfrac{}{}{0ex}{}{n,3}{k})=[z^k](1+z+z^2{)}^n.$$

These coefficients are intimately related to the Motzkin-world, as we will discuss for the reader’s benefit. We use the substitution $z={\displaystyle \frac{v}{1+v+v^2}}$ as we first did in [7]. Using this substitution, all generating functions become much easier, like $$Q(z)=v,\frac{1}{\sqrt{1-2z-3z^2}}=\frac{1+v+v^2}{1-v^2}.$$

Coefficients can be extracted via contour integration, which is a variant of the Lagrange inversion formula. See [2] and [7] as illustrations of the technique. Note that when $z$ runs around the origin in a small circle, $v$ runs around the origin once as well, in a deformed circle. We will show two sample computations: $$\begin{array}{rl}\frac{1}{\sqrt{1-2z-3z^2}}& =\frac{1}{2\pi i}\oint \frac{dz}{z^{n+1}}\frac{1}{\sqrt{1-2z-3z^2}}\\ & =\frac{1}{2\pi i}\oint \frac{dv(1-v^2)}{(1+v+v^2{)}^2}\frac{(1+v+v^2{)}^{n+1}}{v^{n+1}}\frac{1+v+v^2}{1-v^2}\\ & =\frac{1}{2\pi i}\oint \frac{dv}{v^{n+1}}(1+v+v^2{)}^n=[v^n](1+v+v^2{)}^n\\ & =(\genfrac{}{}{0ex}{}{n,3}{n});\end{array}$$ and $$\begin{array}{rl}{Q}^j& =\frac{1}{2\pi i}\oint \frac{dz}{z^{n+1}}{v}^j\\ & =\frac{1}{2\pi i}\oint \frac{dv(1-v^2)}{(1+v+v^2{)}^2}\frac{(1+v+v^2{)}^{n+1}}{v^{n+1}}{v}^j\\ & =\frac{1}{2\pi i}\oint \frac{dv(1-v^2)}{v^{n+1-j}}(1+v+v^2{)}^{n-1}\\ & =[v^{n-j}](1+v+v^2{)}^{n-1}-[v^{n-j-2}](1+v+v^2{)}^{n-1}\\ & =(\genfrac{}{}{0ex}{}{n-1,3}{n-j})-(\genfrac{}{}{0ex}{}{n-1,3}{n-j-2}).\end{array}$$