# Enumerating Rooted labeled trees without Lagrange inversion formula

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!

• The solution to $C(x) = x \exp(C(x))$ is a new transcendental function, you won't find a "nice" formula for it, it is related to Lambert's W function <en.wikipedia.org/wiki/Lambert_W_function> – vonbrand Feb 15 '13 at 20:21
• BTW, why restrict yourself from using one of the most useful tools to handle this type of equations? – vonbrand Feb 15 '13 at 20:22
• Well based on the notes, we're not suppose to have covered the LIF so the problems should be doable without. I actually asked this problem to give me some intuition for other problems and the counting proofs are great! – Azhuang Feb 17 '13 at 7:07

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.

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.)

• There is a detailed presentation of this argument in Miklós Bóna, Introduction to Enumerative Combinatorics, McGraw-Hill, 2007, pp. 266-8. – Brian M. Scott Feb 16 '13 at 0:27
• I would suggest a few improvements on this very nice answer. First, "rooting each subtree you come to at that point, and removing all edges along the path" sounds wrong: the tree is not rooted to begin with, so what is a subtree? I think you mean "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 lies on the path". Next, I'd replace "nonempty sequence of rooted labeled trees" by "nonempty sequence of vertex-disjoint rooted labeled trees". – darij grinberg Jun 2 '15 at 14:08

Pitman gave a wonderful solution.

Talking about "Joyal point of view" one could give up those vertebrates and talking only about functions and labeled trees. And in case we haven't rooted trees there'll be $n^2$ functions for each tree. Otherwise, if the problem concerns labeled rooted trees, then we'll have $n$ functions associated to every such tree.

(So there are $n^{n-2}$ labeled trees and $n^{n-1}$ labeled rooted trees)

Talking on the base set $[n]={1,2,...,n}$

It's not that obvious how you build the function(s) starting from a labeled tree (rooted or not). But it's similar. For example, in the case of "unrooted" labeled trees we'll have "n X n" = $n^2$ unique paths, from each vertex to each vertex (including from a vertex to itself). Such a path, with the vertices M = {$v_1, ..., v_k$} like this $v_1$ -> $v_2$ ->...-> $v_k$ will build partially a function $f(v_i)=v_{i+1}$, where $v_{k+1}$ is $v_1$. For the "subtrees" (having the ROOT in the paths' vertices it's simple).

Conversely, having a function, you must build a tree ... There is a unique (nonempty) set $M$ with maximum elements such as $f$ is bijective on $M$ ... If we write the elements of $M$ increasingly $M = \{i_1, i_2,...,i_2\}$ then $f(i_1)$ -> $f(i_2)$ -> ... -> $f(i_k)$ will be the path .. for the rest is much more simple... (and we'll have finally $n^2$ functions giving the same tree). The operations are inverse to one another...

In the case of rooted labeled trees we'll have $n$ unique paths joining the root with every other vertex (including the root itself). The rest is just the same.

Anyway, here are only the main STEPS. A rigorous demonstration it's much more longer than this, because you must justify all, major or minor "tricks" or statements.

What is interesting in my case (what I'm looking for) is the possibility to follow similar steps (in the "Joyal style", using functions) to prove the Moon theorem, I mean enumerating labeled trees having given (fixed) degrees, so $d(x_i)= d_i$ for $i \in [n]$, of course with $\sum d_i = 2(n-1)$...

... and find the well known multinomial coefficient $\binom{n-2}{d_1 -1 \; d_2 -1 \; ... \; d_n -1}$