Tree space
          hyperexponentialNo. of unrooted
          bifurcating trees

Number of rooted bifurcating trees with t taxa


    Taxonomists sometimes ask, If you want to find the shortest tree, why not write out all the possible trees & choose the shortest? The answer is that it's computationally impossible. The number of possible trees follows a hyper-exponential function as # trees = [(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 very rapidly exceeds the number of possible trees that it is possible to represent on a single 64-bit computer, or a network of such computers, or all computers available. With N = 52 taxa, a relatively modest phylogenetic study, the number of possible solutions (2.75 x 1080) exceeds Eddinger's Number, the estimated number of molecules in the Universe (~1080) !
 

All figures & text material © 2021 by Steven M. Carr