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$?
-
5$\begingroup$ see for example Section 3 in Chapter 4 of my diploma thesis dmg.tuwien.ac.at/rubey $\endgroup$– Martin RubeyOct 1, 2018 at 20:07
-
4$\begingroup$ 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? $\endgroup$– Chuck NewtonOct 1, 2018 at 20:12
1 Answer
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}$.