= Labelled forest count with prescribed roots
{title2=$F(n,k)=kn^{n-k-1}$}
For a fixed set of $k<n$ roots among $n$ labelled <vertices>, the number of <forests> with exactly one root in each <graph component> is $kn^{n-k-1}$. Orient edges toward their roots. Repeatedly remove the smallest nonroot leaf and record its parent. This gives a code of length $n-k$ whose last entry is a root. Conversely, for any such code choose the smallest remaining nonroot absent from the remaining code, join it to the first entry, and delete it. There is always a choice because the final entry is a root. These inverse operations give $n^{n-k-1}$ choices for the earlier entries and $k$ for the last. For $k=n$, the empty forest is unique.
Back to article page
