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.

  • $\begingroup$ I think I figured it out. Will try to find some time and post the answer. $\endgroup$ 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.