Phylogenetic Tree Counting

The number of possible phylogenetic trees varies depending on whether the trees are rooted or unrooted and the number of distinct sequences (taxa), represented by '$n$'.

Unrooted Phylogenetic Trees Formula

For $n$ distinct sequences, the number of possible unrooted binary phylogenetic trees is given by the formula:

$ \text{Number of unrooted trees} = (2n - 5)!! $

This formula is valid for $n \ge 3$. The double factorial $k!!$ involves multiplying integers down to 1 with the same parity as $k$. For instance, $3!! = 3 \times 1$.

Rooted Phylogenetic Trees Formula

For $n$ distinct sequences, the number of possible rooted binary phylogenetic trees is calculated using:

$ \text{Number of rooted trees} = (2n - 3)!! $

This formula applies for $n \ge 2$. It's worth noting that $(2n-3)!! = (2n-3) \times (2n-5)!!$.

Calculating Trees for Four Sequences

We need to calculate the number of rooted and unrooted trees for $n = 4$ different sequences.

• Unrooted Trees Calculation: Applying the formula $(2n - 5)!!$ with $n=4$: $ (2 \times 4 - 5)!! = (8 - 5)!! = 3!! = 3 \times 1 = 3 $ Thus, there are 3 possible unrooted trees.
• Rooted Trees Calculation: Applying the formula $(2n - 3)!!$ with $n=4$: $ (2 \times 4 - 3)!! = (8 - 3)!! = 5!! = 5 \times 3 \times 1 = 15 $ Thus, there are 15 possible rooted trees.

The question asks for the number of rooted and unrooted trees, in that specific order (respectively). Therefore, the result is 15 rooted trees and 3 unrooted trees.