SME
Evolutionary Biology · Problem type
Counting possible trees
Use this for “How many rooted trees can five species form?”
Table
Taxa (n)
Rooted trees (R)
This is an example. Type your own values to start a new problem.
R
=
(2
×
n
−
3)!!
U
Unrooted trees
calculated
Formulas
R
=
(2
×
n
−
3)!!
105 = (2 × 5 − 3)!!
U
=
(2
×
n
−
5)!!
15 = (2 × 5 − 5)!!
Assumptions
•
Every branch point splits in two, and only the branching order counts, not branch lengths.
•
A rooted tree of n − 1 taxa has 2n − 3 branches, its root’s stem included, where the next taxon can join.
•
So the counts multiply: a double factorial takes every other number, 7!! = 7 × 5 × 3 × 1.
•
An unrooted tree of n taxa can be rooted on any of its 2n − 3 branches, so unrooted trees number R ÷ (2n − 3) = (2n − 5)!!.
Step-by-step
WE KNOW
n = 5
FIND
rooted trees (R), unrooted trees (U)
Step 1 · Find rooted trees (R)
Use R = (2 × n − 3)!!
Each taxon added in turn can join any branch of the tree before it, so the choices multiply.
R
=
(2
×
5
−
3)!!
R
=
7!!
R
=
7
×
5
×
3
×
1
R
=
105
Step 2 · Find unrooted trees (U)
Use U = (2 × n − 5)!!
An unrooted tree has two fewer branches for each added taxon to join.
U
=
(2
×
5
−
5)!!
U
=
5!!
U
=
5
×
3
×
1
U
=
15
Check
Put the numbers back in. Both sides should match.
105 = (2 × 5 − 3)!! ✓
15 = (2 × 5 − 5)!! ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.