4
$\begingroup$

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. My question is: Is there a generalization of this formula for forests?

Let $f_{n,k}$ denote the number of forests with $k$ connected components on $n$ vertices. For example, $f_{n,1} = n^{n-2}$ by Cayley's formula and $f_{n,n-1} = \binom{n}{2}$. Is there a known closed formula for $f_{n,k}$? If not, is there an asymptotic formula?

$\endgroup$
5
$\begingroup$

A formula as a single sum is $$f_{n,k} = \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}.$$ This formula can be found in J. W. Moon's Counting Labelled Trees, Theorem 4.1. He attributes it to A. Rényi, Some remarks on the theory of trees, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 4 (1959), 73--85.

To prove it, let $T= \sum_{n=1}^\infty n^{n-1} x^n/n!$ be the exponential generating function for rooted trees and let $U=\sum_{n=1}^\infty n^{n-2} x^n/n!$ be the exponential generating function for unrooted trees. It is well known that $$T^k = k! \sum_{n=k}^\infty \binom nk k n^{n-k-1}\frac{x^n}{n!}.\tag{$*$}$$ Then $U = T-T^2/2$ so the exponential generating for forests of $k$ trees is $$\sum_{n=k}^\infty f_{n,k} \frac{x^n}{n!} = \frac{U^n}{n!}=\frac{(T-T^2/2)^k}{k!},$$ and the formula for $f_{n,k}$ follows by expanding the right side by the binomial theorem and using $(*)$.

$\endgroup$
2
$\begingroup$

A straightforward formula: $f_{n,k}$ is the coefficient of $x^n$ in $$\frac{n!}{k!}\cdot\left( \sum_{i=1}^{\infty} \frac{i^{i-2}x^i}{i!}\right)^k$$ (clearly, the sum here can be restricted to first $n$ terms).

$\endgroup$
1
$\begingroup$

I doubt that more than https://oeis.org/A105599 is known.

The formula given in Bollobas is $$ \frac{1}{m!}\sum_{j=0}^m \left(-\frac{1}{2}\right)^j \binom{m}{j}\binom{n-1}{m+j-1}n^{n-m-j}(m+j)!, $$ where $n$ is the number of vertices and $m$ is the number of components.

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