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

234 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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