Go to main content

PDF

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.

Details

Files

Statistics

from
to
Export
Download Full History
Formats
Format
BibTeX
MARCXML
TextMARC
MARC
DublinCore
EndNote
NLM
RefWorks
RIS