2
$\begingroup$

Let be B(z) the exponential generating function for the number $b_n$ of different rooted unordered binary trees with exactly n leaves labeled only at their leaves (so the internal nodes are unlabeled). Then it's a well know result that $b_n = 1\cdot3\cdot\ldots\cdot(2n-3)=(2n-3)!!$ (see eg. Schröder "Vier combinatorische Probleme"). The EGF satisfies the recursion

$B(z) = z + \frac{1}{2}B(z)^2$.

There is one tree with one leave and every tree is built up from two (smaller) trees where the order doesn't matter (because the trees are unplane).

My question:

So $B(z) = z + z^2 + 3z^3 + 15z^4 + 105z^5 + ...$

And therefore $z + \frac{1}{2}B(z)^2 = z + \frac{1}{2}(z^2 + 2z^3 + 7z^4 + 36z^5 + ...) \neq B(z)$

So the recursion is not satisfied? Where is my mistake?

Thanks a lot!

1 Answers 1

4

Since $B(z)$ is an exponential generating function $B(z) = \sum_n b_n \frac{z^n}{n!}$, and not $\sum_n b_n z^n$.

With correct definition the series expansion for $B(z)$ should read:

$ B(z) \sim z+\frac{z^2}{2}+\frac{z^3}{2}+\frac{5 z^4}{8}+\frac{7 z^5}{8}+\frac{21 z^6}{16}+\frac{33 z^7}{16}+O\left(z^8\right) $ and this satisfies the recurrence equation:

In[200]:= With[{b = Sum[(2 n - 3)!!/n! z^n, {n, 1, 8}] + O[z]^8},   z + 1/2 b^2 - b]  Out[200]= SeriesData[z, 0, {}, 8, 8, 1] 
  • 0
    Uh yes, thanks a lot! I totally forgot that I've to deal with labeled structures.2011-10-07