I am wondering how to enumerate rooted labeled trees without the Langrange inversion formula. Because each tree is a collection of other trees, the recursive generating function becomes $$C(x) = x + xC(x) + xC(x)^2 … = \sum_n x[C(x)]^n/{n!} = xe^{C(x)}$$
From my notes, I am told that we may be able to utilize the function $G(x)$ which counts the number of forests on n vertices => $xG(x) = C(x)$ I can been trying to fiddle around with these functions as well as taking derivatives/log of both, but I can't seem to isolate $C(x)$ to get a functional equation to extract coefficients. Any help would be appreciated!
Best Answer
Here's another proof, I believe due to Jim Pitman.
A rooted forest is a disjoint union of rooted trees, which we will think of as a digraph with edges always directed toward the roots. Given a rooted forest $F$ on $n$ vertices with $k$ components, we would like to add an edge while still having a forest. To do this, choose any vertex $x$ and any of the $k-1$ roots $y$ not in the same component as $x$ and add the edge $y \rightarrow x$. There are thus $n(k-1)$ ways of doing this, and the resulting forest now has $k-1$ components. If we start from forest with $n$ isolated vertices, we see that we can add $n-1$ edges in
$$n(n-1)\cdot n(n-2) \cdot \ldots \cdot n(1) = (n-1)! \cdot n^{n-1}$$ ways. In this expression each tree has been counted $(n-1)!$ ways since the order in which we added edges does not matter, so dividing this out gives the desired formula.