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

4 Answers 4

8
$\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$
2
$\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$
0
$\begingroup$

The one below is not really a closed formula, but I post it for the sake of completeness.

$$\frac{n!}{k!} \sum_{\substack{n_1+\dots+n_k=n \\ n_i\geq 1}} \prod\limits_{j=1}^m \frac{n_j^{n_j-2}}{n_j!}$$

The subscript of the summation is a fixed-length integer partition of $n$ with a lower bound on the terms; a quick google search only lead me to two separate questions dealing with fixed-length partitions and with lower bounds.

The original Russian paper, where the formula appears, can be found here, and an English transcript here.

(Britikov, V. E. Asymptotics of the number of forests made up of nonrooted trees. (Russian) Mat. Zametki 43 (1988), no. 5, 672–684, 703; translation in Math. Notes 43 (1988), no. 5-6, 387–394)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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