This site is not maintained. Click here for the new website of Richard Dawkins.

Comment

← Tree of Life Project Aims for Every Twig and Leaf

God fearing Atheist's Avatar Jump to comment 4 by God fearing Atheist

Comment 1 by Jos Gibbons :

Does anyone know an approximate formula for the number of possible trees for N species with N large?

My first stab is an algorithm (assuming a binary tree):-

1) Start with one species (LUCA), and N-1 unassigned species.

2) Assign a species as a branch of each existing branch, and decrement the unassigned species.

In this case, there is one branch which forks in two, and there are N-2 unassigned species.

3) In general goto 2. If there are 2 assigned species, there are two branches from which the third species can branch, making 2 trees of 3 species, and N-3 left to assign.

Each tree of 3 species can have a branch at 3 places, giving 6 trees of 4 species in total.

Each tree of 4 species can have a branch at 4 places, giving 24 trees of 5 species in total.

" " " 5 " " " " " " 5 " " 120 trees " 6 " " "

Thf. N species = 1 * 2 * 3 * 4 * 5 * 6 * ... * N = N!

This is probably taught in Computer Science 101, so I'm about to Google it ...

Mon, 04 Jun 2012 22:18:51 UTC | #945588