

Number of rooted
bifurcating trees with t taxa
A seemingly
obvious question is, If you want to find the best tree, why
not write out all the possibilities & choose the shortest?
The answer is that it's computationally impossible. My PhD
thesis computation in 1983 with RFLP maps from N =
6 species of frogs (>100 trees) was worked out as a
hand calculation on paper; without a shortcut, there would have
been > 10,000. The evolutionary geneticist Joe
Felsenstein (1942 - ) showed that the number of possible
trees follows a hyper-exponential function, as #
trees for t taxa = (2t-3)! / [ (2t-2)(t-2)! ].
The Branch & Bound algorithm begins to require too
much computer time to be practical at about t = 20, and
the number of possible trees very rapidly exceeds what is
possible to represent on a single 64-bit computer, or a
network of such computers, or all computers
available, or all computers anywhere. With N = 52
taxa, a modest phylogenetic study by current standards, the
number of possible solutions (2.75 x 1080)
exceeds Eddinger's Number, the estimated number of
molecules in the Universe (~1080) !