Description
Various enumerations of labeled trees and forests, due to Cayley, Moon, and other authors, are consequences of the following (\em coalescent algorithm) for construction of a sequence of random forests $(R_n, R_(n-1), \cdots, R_1)$ such that $R_k$ has uniform distribution over the set of all forests of $k$ rooted trees labeled by $\INn := \(1, \cdots , n\)$. Let $R_n$ be the trivial forest with $n$ root vertices and no edges. For $n \ge k \ge 2$, given that $R_n, \cdots, R_k$ have been defined so that $R_k$ is a rooted forest of $k$ trees, define $R_(k-1)$ by addition to $R_k$ of a single directed edge picked uniformly at random from the set of $n(k-1)$ directed edges which when added to $R_k$ yield a rooted forest of $k-1$ trees labeled by $\INn$. Variations of this coalescent algorithm are described, and related to the literature of physical processes of clustering and polymerization.