Blogrolling On III

August 6, 2007 · Filed under Uncategorized

Note that if we always set $x = 1$, $J(x,y)$ has a non-zero imaginary part when $-1 < y < 3$. If $y = 2$, and thus $z = 2x$, the coefficients take the form

$C_{i} = 2^i S_i$

for the Schroeder numbers $S_i$. Then $J$ is a cubed root of unity $\omega$, and the generating function corresponds to the rule

$J = 1 + 2J + J^2$

Can we prove a law $J^4 = J$? Similarly, if $y = 3$ and $J = -1$ the rule would be $J = 1 + 3J + J^2$. Can we interpret these rules in terms of trees? Let’s write the first rule as $J = 1 + J + J + J^2$. This looks a lot like the Motzkin rule, except for the extra factor of $J$. What if we distinguished left and right branches for Motzkin trees? That is, take a full binary rooted tree template and count whole trees with 0, 1 or 2 branches that may be fitted to the template. Then the desired rule works by differentiating left and right unary branches from the root. Instead of a fivefold bijection of the set of Motzkin trees, there is now a fourfold mapping, and the series

$1 + 4 + 24 + 176 + 1440 + \cdots = \omega$

Motzkin numbers $M_i$ are also given in terms of trinomial coefficients $T(n,1)$. The $T(n,0)$ coefficients go back to Euler. These are the number of permutations of $n$ ternary symbols (-1, 0, or 1) which sum to 0. A general $T(n,k)$ is the number of permutations of these symbols that sum to $k$.

Advertisement