Bijective Proof Involving the Motzkin Numbers

In answering a question involving tree counting, I ran across the Motzkin numbers, which I had never encountered before. The problem involved counting the number of rooted, ordered trees with $n$ nodes, subject to the condition that no nodes has degree greater than 3. Basically, I solved the problem by finding a recurrence, computing some terms, and sticking the result in OEIS. This turned up the Motzkin numbers, except that I had $T_n=M_{n-1}.$ (Now that I think of it, the correspondence would have been perfect if I'd changed to counting trees with $n$ edges.) Except for the difference in index, the two sequences had the same initial values, and satisfied the same recurrence, so they are identical.

Anyway, I see on Wikipedia that one way to define $M_n$ is

the Motzkin number for $n$ gives the number of routes on the upper right quadrant of a grid from coordinate $(0, 0)$ to coordinate $(n, 0)$ in $n$ steps if one is allowed to move only to the right (up, down or straight) at each step but forbidden from dipping below the $y = 0$ axis.

I have been trying to find a bijective proof that the number of such paths equals the number of admissible trees with $n$ edges, but I'm not having any luck. I can see that going up corresponds to a node with two children, going straight to an node with one child, and going down to a node with no child, but I can't figure out how to make the correspondence in detail.

I've drawn the $9$ trees with $4$ edges, and I've been comparing them to the paths pictured on Wikipedia, and I can match up some of them, but not all. For example, there are only two trees that have two nodes of degree $3$, and there are only two paths shown that go up twice, so the pairs must correspond. However, the two trees are symmetric, in that they correspond if left and right are interchanged, and I see no such symmetry in the path.

I've also thought about traversing the tree by depth-first search say, and somehow encoding the edges as Up, Straight, or Down, but I haven't been able to make that work out.

I've tried to find a proof on the Web, but everything I run across seems to be dealing with much more advanced problems.

Please give me a proof, or a hint, or a reference.

• Can you get your hands on a copy of Enumerative Combinatorics Volume 2 by R.P. Stanley ? ... Page 238, Exercise 6.38 ... He gives $13$ examples that enumerate the Motzkin numbers. Example $b$ are the paths you describe & $i$ is the rooted plane trees where each vertex has at most $2$ successors. Commented Feb 21, 2018 at 0:48
• @DonaldSplutterwit Not easily, anyway. It looks like the library only has volume 1. Thanks. Commented Feb 21, 2018 at 0:57

A bijection from Motzkin trees to Motzkin paths can be defined recursively as follows. Denote the up, down and level steps by $U$, $D$ and $L$ respectively.

• A singleton tree (i.e. a tree with $1$ vertex) is mapped to a path of length $0$, i.e. $f(\bullet)=\bullet$.

• If a tree $T$ has the root of degree $1$ with the subtree $T_1$, then $f(T)=Lf(T_1)$.

• If a tree $T$ has the root of degree $2$ with the left subtree $T_1$ and the right subtree $T_2$, then $f(T)=Uf(T_1)Df(T_2)$.

So, if there are no vertices of degree $1$, i.e. we start with a binary tree, then the image is a Dyck path, since there no $L$ steps.

From this recursive description of the Motzkin trees and Motzkin paths, it's easy to see that the ordinary generating function $m=m(x)$ for $M_n$ satisfies $$m=1+xm+x^2m^2,$$ i.e. $$m=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}.$$

Bonus: Here is a related neat result. From the functional equation above, it follows that $$(1-3x)m=m-3xm=1-2xm+x^2m^2=(1-xm)^2,$$ so that $$\frac{m}{(1-xm)^2}=\frac{1}{1-3x}.$$ Try to prove this bijectively.

• Actually, I started by getting the generating function, but I couldn't simplify the formula I got for the coefficients, and resorted to OEIS. I don't understand the point of the bonus, I'm afraid. The only use I know for the generating function is to get at the coefficients. Does the equation in the bonus somehow lead to a simpler recurrence or something like that? Commented Feb 22, 2018 at 15:51
• A generating function identity always corresponds to a bijection between the combinatorial classes, and certain operations on functions correspond to certain related operations on the objects of the underlying combinatorial class. Rather than a simpler recurrence, it's another way to understand the structure of the objects under consideration. Just in terms of generating functions, we have $\left(\frac{x}{(1-x)^2}\right)\circ(xm)=\frac{x}{1-3x}$. Taking the inverse of the left factor, we get $xm=(xC(-x)^2)\circ\left(\frac{x}{1-3x}\right)$, where $C(x)$ is the Catalan generating function. Commented Feb 22, 2018 at 22:19
• I'm sorry, but I can't follow this at all. Is the $\circ$ supposed to represent multiplication? This sounds very interesting though. Where can I read more about it? Commented Feb 22, 2018 at 22:46
• The operation $\circ$ represents the composition of functions. I.e. you plug the function on the right into the function on the left. Try searching for "formal power series", for example. To see that $xC(-x)^2$ is the inverse (not the reciprocal, but the compositional inverse) of $\frac{x}{(1-x)^2}$, solve $t=\frac{x}{(1-x)^2}$ for $x$ to get $x=1-C(-t)=-(-t)C(-t)^2=tC(-t)^2$. Commented Feb 22, 2018 at 22:57

I think what you are looking for is this:

Kuznetsov, A.; Pak, I.; and Postnikov, A. "Trees Associated with the Motzkin Numbers." J. Combin. Th. Ser. A 76, 145-147, 1996.

• Thanks, but I don't think this is it. It looks to me like the paper defines the Motzkin number as the tree count I'm interested in, and then establishes a bijection with a different kind of tree, not with the paths in the Wikipedia definition. Still, I'll look the paper more closely. Maybe I'll learn enough to solve my problem. Commented Feb 21, 2018 at 0:43
• @saulspatz Try the Donaghey, Shapiro reference at the Wikipedia page for Motzkin numbers. Commented Feb 22, 2018 at 6:06

I found the answer to this in Analytic Combinatorics, by Flajolet and Sedgewick, in the subsection titled "Tree codes and Łukasiewicz words," pp. 74ff. For any rooted, ordered tree (or "plane tree") orient all the edges to point from parent to child. Then traverse the tree in preorder (that is depth first search, and record the out-degrees of the nodes, in the order visited. It is well known, and trivial to prove, that this degree sequence uniquely determines (the isomorphism class of) the tree.

A walk in the plane called the Dyck path of the tree is constructed by starting at $(0,0)$ and associating with the out-degree $d$ a displacement of $(1, d-1)$. Since the sum of the out-degrees is $n-1,$ the path ends with $y=-1,$ and it is easy to show that this is the only time it dips below the $y-$axis. Because the last displacement is necessarily $(1,-1),$ it is customary to omit it, resulting in a walk in the first quadrant, beginning at $(0,0)$ and ending with $y=0.$ Since in the instant case, the only possible out-degrees are $0,1,2,$ we get precisely the paths in the definition of the Motzkin numbers, and it is obvious that the correspondence is a bijection.