# Are there Prüfer sequences for rooted forests?

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$$?

• see for example Section 3 in Chapter 4 of my diploma thesis dmg.tuwien.ac.at/rubey – Martin Rubey Oct 1 at 20:07
• Well that is just perfect! Given that this is exactly what I'm looking for, can you make it an answer so I can accept it? – Chuck Newton Oct 1 at 20:12

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