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.
 A: 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)$.
