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 . 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
    see for example Section 3 in Chapter 4 of my diploma thesis – Martin Rubey Oct 1 at 20:07
  • 4
    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

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.