Enumerating Rooted labeled trees without Lagrange inversion formula

Question

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!

Answer 1

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.

Answer 2

Usually, you would use the Lagrange inversion formula together with the functional equation $C(x)=x e^{C(x)}$ to extract the coefficients from $C(x)$. But if you don't want to do that, here is a combinatorial argument to count labeled rooted trees, from Joyal (1981), p. 16:

Call a vertebrate an unrooted labeled tree with two (possibly coincident) distinguished points, a red one and a black one. By following a path from the red point to the black point, removing all edges along the path, so that the tree becomes a forest; and then rooting each connected component of this forest at its only vertex which had lain on the path previously formed by the removed edges, you can change the vertebrate into a nonempty sequence of rooted labeled trees. This is a bijective correspondence, so $V_n$, the number of vertebrates on $n$ vertices which are labeled $\{1,\ldots,n\}$, is the same as the number of nonempty sequences of vertex-disjoint rooted trees on vertices labeled $\{1,\ldots,n\}$.

Let $n\ge 1$. The number of ways of arranging the roots of $k$ rooted trees into a sequence is $k!$, which is the same as the number of ways of arranging the roots of $k$ rooted trees into a permutation. So, $V_n$ is also the number of sets of rooted trees on vertices labeled $\{1,\ldots,n\}$ together with a permutation acting on their roots. But every self-map on $\{1,\ldots,n\}$ gives such a structure (composed of trees of elements which coalesce under the action of the self-map and eventually fall into cycles), and conversely. This is a bijective correspondence, so $V_n$ equals the number of self-maps on $\{1,\ldots,n\}$, which is $n^n$.

Each rooted tree on labeled vertices $\{1,\ldots,n\}$ gives $n$ different vertebrates, by coloring the root black and any of $\{1,\ldots,n\}$ red. This is an $n$-to-$1$ correspondence, so, if $n\ge 1$, the number of rooted trees on $n$ vertices is $n^n/n=n^{n-1}$.

Joyal also uses similar reasoning to give a combinatorial proof of the Lagrange inversion formula (pp. 21-24.)