The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation $$T_n=1+xT_n^n.$$ This usually applies for $n\ge 0$, but the functional equation can be extended to negative $n$. Writing $$T_{-n}=1+xT_{-n}^{-n},$$ we obtain, by dividing through by $T_{-n}$, that $$T_{-n}^{-1}=1-x(T_{-n}^{-1})^{n+1},$$ i.e. $$T_{-n}(x)=\frac{1}{T_{n+1}(-x)}.$$ What would be a natural way to interpret this combinatorially? I.e. what are "$n$-ary trees" for negative $n$, why do we get the extra 1 degree, etc.

  • $\begingroup$ I don't follow the transformations in the question, but from the functional equation it's quickly apparent that $T_{-1}$ gives Catalan numbers with alternating sign. Maybe there's a useful intuition based on anti-trees which contribute -1 to the g.f. coefficient? $\endgroup$ – Peter Taylor Dec 10 '19 at 23:29
  • $\begingroup$ @PeterTaylor Just divide through by $T_{-n}$ and subtract the term with the $x$. I edited the question to include this now. $\endgroup$ – Alexander Burstein Dec 10 '19 at 23:38

Your Answer

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

Browse other questions tagged or ask your own question.