Bijective Proof Involving the Motzkin Numbers

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.