4
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ "that is the asymptotic number of rooted forests" - you mean unrooted? $\endgroup$ – Fedor Petrov Apr 4 '18 at 8:11
  • 3
    $\begingroup$ Incidentally, there is a stronger statement: for fixed k, the number of labelled forests with k components is asymptotic to $n^{n-2} (1/2)^k/k!$. $\endgroup$ – Brendan McKay Apr 4 '18 at 8:42
  • 1
    $\begingroup$ Indeed, the ADE satisfied by $F$ is not very beautiful - didn't try to massage it, though: $x^{4} F'\left(x\right)^{3} - x F\left(x\right)^{3} - {\left(x^{3} F\left(x\right) + 4 x^{2}\right)} F'\left(x\right)^{2} - 2 F\left(x\right)^{2} - {\left(x^{2} F\left(x\right)^{2} + 2 x F\left(x\right) - 2\right)} F'\left(x\right) + {\left(x^{2} F\left(x\right) - {\left(x^{4} F\left(x\right) + x^{3}\right)} F'\left(x\right) + x\right)} F''\left(x\right)$. $\endgroup$ – Martin Rubey Apr 4 '18 at 9:20
5
$\begingroup$

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}$.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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