# A bijection between Motzkin paths and 3-colored signed Dyck path homomorphs

The generating function $m=m(z)$ for the Motzkin numbers satisfies the functional equation $$m=1+zm+z^2m^2$$ (a Motzkin path $P$ with unit steps $u,d,l$ (up, down, level) is either empty or $lP'$ or $uP'dP''$). A simple manipulation yields $$m(1-3z)=m-3zm=1-2zm+z^2m^2=(1-zm)^2,$$ so that $$\frac{zm}{(1-zm)^2}=\frac{z}{1-3z},$$ i.e. $$\frac{z}{(1-z)^2}\circ(zm)=\frac{z}{1-3z},$$ where $\circ$ denotes the composition of functions. Inverting the left factor on the left, we obtain $$zm=\left(zC(-z)^2\right)\circ\frac{z}{1-3z}=\frac{z}{1-3z}C\left(-\frac{z}{1-3z}\right)^2,$$ where $C=C(z)$ is the generating function for the Catalan numbers.

My question is: Is there a known bijective proof of this last equation? That would possibly involve some inclusion-exclusion argument or an involution on $3$-colored signed Dyck path homomorphs (i.e. Dyck paths where each edge is replaced with a path each of whose non-initial steps is assigned one of $3$ colors, while the initial step has weight $-1$). Of course, this is just one choice, the combinatorial classes involved may be different.

• I think I figured it out. Will try to find some time and post the answer. Mar 3 '18 at 15:47

Consider a set $\mathcal{T}$ of certain incomplete ternary trees with edges labeled $1$ and $-1$, defined as follows:

• Every vertex has outdegree $1$ or $2$.

• A vertex of outdegree $2$ has only left and right children, with both outgoing edges labeled $-1$.

• A vertex of outdegree $1$ with the middle child has the outgoing edge labeled $1$.

• A vertex of outdegree $1$ with the left or right child may have either label, $1$ or $-1$, on the outgoing edge.

Check: These trees have the generating function $$F(z)=\frac{1}{1-3z}C\left(-\frac{z}{1-3z}\right)^2.$$ The edges of the original incomplete binary tree are blown up into paths whose initial step has label $-1$ while the subsequent steps are labeled $1$. Then a path labeled with all $1$'s is attached before the root of the original tree.

To find the coefficient $[z^n]F(z)$, consider the following bijection.

Define with weight of the tree $T\in\mathcal{T}$ as the product of its edge labels. Define a bijection $\phi$ on $\mathcal{T}$ as follows:

• If a tree $T\in\mathcal{T}$ has a vertex of outdegree $1$ with a left or right child, find the first such edge, say, in preorder, and switch the sign of its label.

• Otherwise, let $\phi(T)=T$.

Then the $[z^n]F(z)$, i.e. the sum of the weights of all trees on $n$ edges, is just the sum of the weights of the fixed points of $\phi$ with $n$ edges.

But what are the fixed points of $\phi$? Those are the trees where

• each vertex of degree $1$ only has the middle child (with the outgoing edge labeled $1$), and

• each vertex of degree $2$ has both left and right children (with the outgoing edges labeled $-1$).

Thus, every such tree is a Motzkin tree with an even number of edges labeled $-1$, so its weight is $1$. Therefore, $[z^n]F(x)$ is just the number of Motzkin trees on $n$ edges, i.e. $F(z)=m(z)$.