Asymptotics of unrooted labeled forests

Question

It is well known that the number of unrooted labeled trees on vertex set $[n]={1,2,...,n}$ is $n^{n-2}$. Let $U(z)$ be the exponential generating function of the sequence of these numbers. Then $F(z)=\text{exp}(U(z))$ is the exponential generating function for the number of unrooted forests of $[n]$.

My question is, how do you prove that $n![z^n]F(z) \sim e^{1/2} n^{n-2}$. In other words, that is the asymptotic number of unrooted forests on $[n]$. I found this result on page 406 of the Flajolet-Sedgewick book, without proof.

If that helps, $U(z)= T(z) - T(z)^2 /2$ , where $T(z)$ is the exponential generating function for the numbers of rooted trees. But while $T(z)$ satisfies the relation $T=z \ \text{exp}(T)$, I could not find such a relation for F.

Answer 1

The idea in the book by Flajolet-Sedgewick is to use singularity analysis. The generating function $F(z)=\exp(U(z))$ with $U=T-T^2/2$ inherits the dominant singularity $e^{-1}$ of $T(z)=-W(-z)$, where $W$ is the Lambert $W$ function. From the local expansion of $T(z)$ $$T(z)=1-\sqrt{2}\sqrt{1-ze}+\frac{2}{3}(1-ze)-\frac{11\sqrt{2}}{36}(1-ze)^{3/2}+O((1-ze)^2),\quad z\rightarrow e^{-1}$$ follows that of $F$: $$F(z)=e^{1/2}\left(1-(1-ze)+\frac{2\sqrt{2}}{3}(1-ze)^{3/2}+O((1-ze)^2)\right).$$ From there, singularity analysis is straightforward. The asymptotic behaviour of the coefficients comes from the term in $(1-ze)^{3/2}$, leading to $$[z^n]F(z)\sim \frac{e^{1/2}}{\sqrt{2\pi}}n^{-5/2}e^{n}.$$ That coefficient is the number of unrooted labeled trees divided by $n!$, so that multiplying by Stirling's formula gives the desired $e^{1/2}n^{n-2}$.

Answer 2

Here's a proof, following section 4.3 of J.W. Moon's book "Counting Labelled Trees".

First, we have the following formula of Rényi (see this post for a proof and reference) for $f_k(n)$, the number of forests on $n$ vertices consisting of $k$ unrooted trees.

$$ f_k(n)= \binom nk \sum_{i=0}^k \left(-\frac12\right)^i (k+i)\,i!\, \binom{k}{i}\binom{n-k}{i} n^{n-k-i-1}.$$

Note that $U^k/k!$ is the generating function for forests of $k$ trees, so we have:

\begin{align} \sum_{n=k}^\infty f_k(n)\frac{x^n}{n!} &= \frac{U^k}{k!}\\ &=\frac{1}{k!}(T-T^2/2)^k\\ &=\frac{1}{k!}\sum_{i=0}^k\binom{k}{i}(-1/2)^iT^{k+i}. \end{align}

Thus $f_k(n)$ is the coefficient of $x^n$ on the right hand side. This can be determined using the following formula:

$$\frac{T^k}{k!} = \sum_{n=k}^\infty\binom{n}{k}kn^{n-k-1}\frac{x^n}{n!}.$$

To prove this, apply the Lagrange–Bürmann formula to $f(x)=T(x)$, $\phi(x)=e^T$, and $H(T)=T^k$ (see also section 4.2 of Moon's book).

To determine asymptotics, we only need to compute the coefficient of $n^{n-h}$ in the formula for $f_k(n)$. Denote this by $c(k,h)$. Then "after some simplification":

$$c(k,1)=\frac{1}{k!}\sum_{i=0}^k(-1/2)^i\binom{k}{i}(k+i)=0,$$

and

$$c(k,2)=-\frac{1}{k!}\sum_{i=0}^k(-1/2)^i(k+i)\binom{k}{i}\binom{k+i}{2}=\frac{(1/2)^{k-1}}{(k-1)!}.$$

Thus $\lim_{n\rightarrow\infty}\frac{f_k(n)}{n^{n-2}}=\frac{(1/2)^{k-1}}{(k-1)!}.$

The result follows after applying Tannery's theorem to sum these limits over all $k$:

$$\lim_{n\rightarrow\infty}\frac{N(n)}{n^{n-2}}=\sum_{k=1}^\infty\frac{(1/2)^{k-1}}{(k-1)!}=e^{1/2},$$

where $N(n)$ is the total number of rooted forests on $n$ nodes, as desired.