Skip to main content

Is there a formula for the number of labeled forests with $k$ components on $n$ vertices?

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?

Zur Luria
  • 1.6k
  • 12
  • 19