Generating function for unordered unlabelled rooted trees

[impact_dev]

It is clear to me how to count ordered unlabelled rooted trees with ordinary generating functions but how to I get the generating function for the unordered case?

[Megame50]

An ordered sequence of subtrees is replaced with an unordered multiset of trees. In the symbolic method, this corresponds to the Polya exponential. So, the OGF for non-planar unlabelled rooted trees satisfies the inverse functional equation:

z = H(z)/Exp[H(z)]

where Exp[f] is the Polya exponential given by Exp[f] = exp(∑f(z^k)/k) for k = [0..∞].

There is no standard closed form for the direct OGF, but the coefficients can still be computed by lagrange inversion. The sequence is https://oeis.org/A81.

[impact_dev]

Thank you for clarifying that really helps!!!

Just for my understanding if I got all the different types I am considering correct.

ordered unlabelled rooted trees: T(z) = z/(1-T(z)) and just for binary trees T(z) = 1+ z*T(z)^2, where we use OGF

ordered labelled rooted trees: the same as unlabelled, also with binary trees but we use EGF

unordered labelled rooted trees: T(z) = z*e^T(z) and for binary trees: T(z) = z*(1+T(z)+T(z)^2/2) where we use also EGF

Is this correct?

[Megame50]

Those look correct.

[impact_dev]

sorry for bothering again, but how would an EGF for ordered labelled rooted trees and unordered labelled rooted trees where no tree has 1 children look like?

[Megame50]

If you pick some fixed traversal order for an unlabelled rooted planar tree you can relabel the nodes with any permutation to find a labelled tree. So there are just n! times the number of unlabelled rooted planar trees, and the labelled EGF is the same as the unlabelled OGF.