  The Robinson-Foulds (RF) distance is by far the most widely used measure of
dissimilarity between trees. Although the distribution of these distances has
been investigated for twenty years, an algorithm that is explicitly polynomial
time has yet to be described for computing this distribution (which is also the
distribution of trees around a given tree under the popular Robinson-Foulds
metric). In this paper we derive a polynomial-time algorithm for this
distribution. We show how the distribution can be approximated by a Poisson
distribution determined by the proportion of leaves that lie in `cherries' of
the given tree. We also describe how our results can be used to derive
normalization constants that are required in a recently-proposed maximum
likelihood approach to supertree construction.
