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^2M^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+zP^2+zP^3+\cdots=\frac{z}{1-P}\quad\text{and therefore}\quad 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+zQ^2\quad\text{and therefore}\quad 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.
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^kM^{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\ge1}{z^{2k}M^{2k+1}}=\sum_{k\ge0}{z^{2k}M^{2k+1}}=\frac1{\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\ge0}Q^{2k+1}=z^2\sum_{k\ge0}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.
The trinomial coefficients (notation from Comtet [1]) are given by \[\binom{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=\dfrac{v}{1+v+v^2}\) as we first did in [7]. Using this substitution, all generating functions become much easier, like \[Q(z)=v,\quad \frac1{\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{aligned} \frac1{\sqrt{1-2z-3z^2}}&=\frac1{2\pi i}\oint \frac{dz}{z^{n+1}}\frac1{\sqrt{1-2z-3z^2}}\\ &=\frac1{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}\\ &=\frac1{2\pi i}\oint \frac{dv}{v^{n+1}}(1+v+v^2)^{n}=[v^n](1+v+v^2)^{n}\\ &=\binom{n,3}{n}; \end{aligned}\] and \[\begin{aligned} Q^j&=\frac1{2\pi i}\oint \frac{dz}{z^{n+1}} v^j\\ &=\frac1{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\\ &=\frac1{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}\\ &=\binom{n-1,3}{n-j}-\binom{n-1,3}{n-j-2}. \end{aligned}\]
1970-2025 CP (Manitoba, Canada) unless otherwise stated.