Find the ordinary generating funtion for thenumber of at most binary trees on n unlabelled nodes.

Question

An at most binary tree is an unordered rooted tree in whic each node has at most two children.

I want to find the ordinary generating function for the number of at most binary trees on n unlabelled nodes.

I am trying to solve this problem using the theory of species. I am thinking the following way.:

Let $t_n$ be thenumber of trees with n vertices and let $T(x) = \sum_n t_n x^n$ be their ordinary generating function. We first pick the root of the tree and then any of the remaining branches must be an at most binary unorderedrooted tree. Thus, the generating function fo any of the branches is $(1+T(x) + T(x)^2/2)$. THus, multiplying our choice for root and the remaining branches, we have that $T(x) = x(1+T(x)+T(x)^2/2)$. From here I should just solve the recurrence and find the ordinary generating function.

I'm not sure if this reasoning is right, but in a previous problem I found the exponential generating fucntion for thenumber of at most binary trees on n laelled nodes, but I got a very similar result.

I am wondering if they way I approached this problem is right and, if not, if anyone could give me a hint for it. Thanks!

Answer 1

Your $t_n$ are the Wedderburn–Etherington numbers, OEIS A001190. Specifically, $t_n=a_{n+1}$, where the $a_n$ are the Wedderburn-Etherington numbers. The OEIS entry has copious references but neither a closed form nor an explicit generating function. It does note that the generating function $A(x)$ for the $a_n$ satisfies

$$A(x)=x+\frac12\left(A(x)^2+A(x^2)\right)$$

and

$$A(x)=1-\sqrt{1-2x-A(x^2)}\;.$$

Since $a_0=0$, $T(x)=\frac{A(x)}x$. For $n\ge 1$ the Wedderburn–Etherington numbers satisfy the recurrences

$$\begin{align*} a_{2n-1}&=\sum_{k=1}^{n-1}a_ka_{2n-k-1}\\ a_{2n}&=\frac{a_n(a_n+1)}2+\sum_{k=1}^{n-1}a_ka_{2n-k}\;, \end{align*}$$

With base case $a_1=1$. This yields the recurrences

$$\begin{align*} t_{2n}&=\sum_{k=0}^{n-1}t_kt_{2n-k-1}\\ t_{2n-1}&=\frac{t_{n-1}(t_{n-1}+1)}2+\sum_{k=1}^{n-1}t_{k-1}t_{2n-1-k} \end{align*}$$

for $n\ge 1$, with base case $t_0=1$.

Answer 2

With this question we run into the problem of determining exactly what the notation is supposed to mean and which family of trees from among the many possibilities is being referenced. I would like to help clarify this.

It appears that these at most binary trees are not ordered trees or plane trees so that two trees that have the same pair of subtrees but in opposite order are considered to be the same. This yields the unlabeled species

$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}\mathfrak{M}_{=1}(\mathcal{T}) + \mathcal{Z}\mathfrak{M}_{=2}(\mathcal{T}).$$

Here we have the convention that the species operator $\mathfrak{M}_{=q}$ represents the symmetric group acting on the $q$ slots, so that the cycle index $Z(S_q)$ is used. These are multisets as opposed to sets (operator $\mathfrak{P}_{=q}$.) Translating to generating functions we thus obtain

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

where we have used the fact that $Z(S_2) = \frac{1}{2} (a_1^2 + a_2).$ Now we introduce the function $$A(z) = z + z T(z)$$ which is a shifted version of $T(z)$ with a singleton added and get the functional equation

$$(A(z)-z)/z = z + A(z) - z + \frac{1}{2} z ((A(z)-z)^2/z^2 + (A(z^2)-z^2)/z^2) \\ = A(z) + \frac{1}{2} z (A(z)^2/z^2-2zA(z)/z^2+1 + A(z^2)/z^2-1) \\ = A(z) + \frac{1}{2} z (A(z)^2/z^2-2zA(z)/z^2 + A(z^2)/z^2).$$

Multiply by $z$ to get

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

This finally yields

$$\bbox[5px,border:2px solid #00A000]{ A(z) = z + \frac{1}{2} (A(z)^2 + A(z^2)).}$$

We have the functional equation of the ordinary generating function of the Wedderburn-Etherington numbers and may continue as in OEIS A001190.

Remark. Using the terminology from Harary and Palmer, Graphical Enumeration we see that taking $z+zT(z)$ corresponds to planting the trees from $T(z)$ and adding the single node planted tree on one node. Hence $A(z)$ counts the species of planted unordered at most binary trees.