One well-known, extremely slick proof of Cayley's tree enumeration theorem is the use of Prüfer sequences. Cayley also proved a version for forests, namely that the number of forests with $n$ labelled vertices that consist of $s$ distinct trees such that $s$ specified vertices belong to distinct trees is $sn^{n-s-1}$; see <https://core.ac.uk/download/pdf/82105567.pdf> . Is there a generalization of Prüfer sequences that corresponds to this quantity? Or more generally, is there a nice way to enumerate all $sn^{n-s-1}$ such forests, given $s$ and $n$?



Are there Prüfer sequences for rooted forests?
We can prove this using ordinary Prüfer sequences; no generalization is needed.


First I'll describe 
Prüfer's correspondence, as a bijection from trees on $\{0,1,2,\ldots,n\}$, where $n\ge1$, to
sequences $a\_1 \ldots a\_{n-1}$ of elements of $\{0,1,2,\ldots,n\}$:
If $n=1$ then $a\_1\ldots a\_{n-1}$ is empty. Otherwise we let $b\_1$ be the greatest leaf of the tree and let $a\_1$ be the unique vertex adjacent to $b\_1$. (Prüfer's correspondence is usually described with the least leaf instead of the greatest leaf, but the greatest leaf works better in this application.) We then remove $b\_1$ and its incident edge from the tree and let $b\_2$ be the greatest leaf of the remaining tree, and let $a\_2$ be the vertex adjacent to $b\_2$. We continue in this way until only two vertices remain and we have constructed $a\_1,a\_2,\dots, a\_{n-1}$.


To prove Cayley's formula it is enough to count forests of $s$ trees with vertex set $\{1,2,\dots,n\}$ in which vertices $1,2,\dots, s$ are all in different trees. By adding a new vertex 0 adjacent to vertices $1, 2, \dots, s $ but no others, we see that the problem is equivalent to counting trees with vertex set $\{0,1,\dots,n\}$ in which vertex 0 is adjacent to vertices $1, 2, \dots, s $ but no others.


I claim that the Prüfer codes for these trees are the sequences $a\_1 a\_2 \ldots a\_{n-1}$ such that
(1) $a\_i\in \{1,2,\dots, n\}$ for $i=1,2,\dots, n-s-1$; (2) $a\_{n-s}\in\{1,2,\ldots,s\}$; and (3) $a\_i = 0$ for $i=n-s+1, n-s+2, \ldots, n-1$. The Prüfer code for any such tree has these properties because in the
process of Prüfer's correspondence, no element of $\{0,1,2,\ldots,s\}$ will be
the greatest leaf until all other vertices have been removed. Thus the
last $s-1$ values of $ b\_i$ will be (in order) $s, s-1, s-2, \ldots, 2$. (The
two remaining vertices, 1 and 0, are never $b\_i$.) The corresponding
values of $a\_i$ are 0 since these vertices are adjacent only to 0 (after
the earlier $b\_i$'s have been removed), and no other vertices are adjacent to 0 so no other $a\_i$ is 0. Moreover, $a\_{n-s}$ must be an
element of $\{1,2,\ldots,s\}$ since after $b\_{n-s}$ is removed, the only
remaining vertices are $0,1,\ldots, s$, (and $b\_{n-s}$ can't be adjacent to
0).


Conversely, any sequence satisfying (1), (2), and (3) is the Prüfer code for
a tree of the kind that we want to count. This requires some additional
justification, which I'll omit. The number of such sequences is clearly $sn^{n-s-1}$.


