Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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, rooting each subtree you come to at that point, and removing all edges along the path, you can change the vertebrate into a nonempty sequence of rooted labeled trees. This is a bijective correspondence, so the number $V_n$ of vertebrates on $n$ vertices which are labeled $\{1,\ldots,n\}$ is the same as the number of nonempty sequences of 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.)

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.