Exponential Generating Function for certain trees

combinatoricsgenerating-functionstrees

I am trying to find the exponential generating function for rooted labeled plane trees with each vertex in the tree having an even number of children.

I am hoping to do this with Lagrange inversion but I have not been successful. I have seen it demonstrated for rooted labeled plane trees with no restrictions, but I am not sure how to account for this new condition requiring even numbers of children. Can someone show how I might do this?

Best Answer

Small hint:

The normal egf equation is $$ T(x)=x\Big(1+T(x)+T(x)^2/2!+T(x)^3/3!+\dots\Big)=x\exp T(x) $$ The $1$ accounts for the tree with only the root vertex, the $T(x)$ for trees where the root has one child, and in general $T(x)^k/k!$ accounts for trees where the root has $k$ children. How should you modify this if you only want to count trees where the root has an even number of children, instead of any $k$?

Related Solutions

[Math] Recursive Generating function for enumerating leaf labeled binary trees

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]

Combinatorics – Number of Labeled, Unordered Rooted Trees with n Vertices and k Leaves

Use the analytic method. Your class is a root connected to a non-empty set of trees, or a leaf. Use $\mathcal{Z}$ (and $z$) for inner nodes, $\mathcal{Y}$ (and $y$) for leaves; use $\mathcal{E}$ for the class with one empty object: $$ \mathcal{T} = \mathcal{Z} \star (\mathfrak{S}(\mathcal{T}) \smallsetminus \mathcal{E}) + \mathcal{Z} \mathcal{Y} $$ This translates to: $$ T(z, y) = z (e^{T(z, y)} - 1) + z y $$ Just need to get $T(z, y)$ (or the coefficients) out of this...

Best Answer

Related Solutions

[Math] Recursive Generating function for enumerating leaf labeled binary trees

Combinatorics – Number of Labeled, Unordered Rooted Trees with n Vertices and k Leaves

Related Question