The Number of Evolutionary Trees

Felsenstein, J. (Department of Genetics, University of Washington, Seattle, Washington 98195) 1978. The number of evolutionary trees. Syst. Zool. 27:27–33.—A simple method of counting the number of possible evolutionary trees is presented. The trees are assumed to be rooted, with labelled tips but unlabelled root and unlabelled interior nodes. The method allows multifurcations as well as bifurcations. It makes use of a simple recurrence relation for T(n,m), the number of trees with n labelled tips and m unlabelled interior nodes. A table of the total number of trees is presented up to n = 22. There are 282,137,824 different trees having 10 tip species, and over 8.87 × 1023 different trees having 20 tip species. The method is extended to count trees some of whose interior nodes may be labelled. The principal uses of these numbers will be to double-check algorithms and notation systems, and to frighten taxonomists.