Skip to main content
1 of 3
Ira Gessel
  • 17k
  • 1
  • 58
  • 80

Here's an explanation of the combinatorial meaning of $T_{-n}(x)$.

The combinatorial interpretation $T_n(x)$ is that it counts $n$-ary trees. More precisely, it counts ordered trees in which every vertex has 0 or $n$ children, and each internal vertex (with $n$ children) is weighted $x$ and each leaf is weighted 1. Let's mark each edge from a vertex to its $i$th child with $i$, and then delete all the leaves (together with their incident marked edges). The original tree can easily be reconstructed from this reduced tree. What we now have is an ordered tree in which the edges from each vertex to its children are marked with some subset of $[n]=\{1,2,\dots,n\}$ in increasing order from left to right.

If we remove all the marks we obtain an underlying ordered tree. Given an ordered tree, how many ways are there to mark it to obtain a tree counted by $T_n(x)$? For each vertex with $k$ children, we can assign marks to the edges to its children in $\binom{n}{k}$ ways. So for an ordered tree with $m$ vertices, if the numbers of children of the vertices are $k_1,k_2,\dots, k_m$ then the number of ways of marking this tree is $\binom{n}{k_1}\binom{n}{k_2}\cdots \binom{n}{k_m}$. So the coefficient of $x^m$ in $T_n(x)$ is the sum of these products of binomial coefficients over all ordered trees on $m$ vertices. If $m>0$ and we replace $n$ by $-n$ this product of binomial coefficients becomes $$\binom{-n}{k_1}\binom{-n}{k_2}\cdots \binom{-n}{k_m}=(-1)^{m-1}\binom{n+k_1-1}{k_1}\binom{n+k_2-1}{k_2}\cdots \binom{n+k_m-1}{k_m},$$ since $k_1+\cdots k_m = m-1$. But $\binom{n+k-1}{k}$ is the number of ways of marking the edges from a vertex to its $k$ children with elements of $[n]$ so that the marks are weakly increasing from left to right, but with repeated marks allowed. Thus $1-T_{-n}(-x)$ counts ordered trees (with at least one vertex) in which the edges joining each vertex to its children are marked with elements of $[n]$ so that the marks are weakly increasing from left to right. I'll call these trees $n$-colored trees. (Such trees have appeared in various places in the literature; the only reference I can recall offhand is to a paper of mine and S. Seo, A refinement of Cayley's formula for trees, https://doi.org/10.37236/1884.)

Thus if we set $U_n(x) = 1-T_{-n}(-x)$ then $U_n(x)$ is the generating function for nonempty $n$-colored trees. It is also not hard to prove this algebraically. In the defining equation $T_{-n}(x) =1-xT_{-n}(-x)^{-n}$, we replace $T_{-n}(x)$ with $1-U_n(x)$ and we obtain $$U_n(x) =\frac{x}{\bigl(1-U_n(x)\bigr)^n}$$ from which the combinatorial interpretation of $U_n(x)$ is clear.

Alex's identity $$ T_{-n}(x)=\frac{1}{T_{n+1}(-x)} $$ may be rewritten as $$T_{n+1}(x)=\frac{1}{1-U_n(x)}.$$ I'm sure that there is a reasonably straightforward bijective proof of this identity, but I didn't work it out. (This post is long enough!)

Ira Gessel
  • 17k
  • 1
  • 58
  • 80