Editing Phylogenetic tree (section)

=== Enumerating trees ===
[[File:Number of trees as a function of the number of leaves.svg|thumb|upright=1.35|Increase in the total number of phylogenetic trees as a function of the number of labeled leaves: unrooted binary trees (blue diamonds), rooted binary trees (red circles), and rooted multifurcating or binary trees (green: triangles). The Y-axis scale is [[Logarithmic scale|logarithmic]].]]
The number of possible trees for a given number of leaf nodes depends on the specific type of tree, but there are always more labeled than unlabeled trees, more multifurcating than bifurcating trees, and more rooted than unrooted trees. The last distinction is the most biologically relevant; it arises because there are many places on an unrooted tree to put the root. For bifurcating labeled trees, the total number of rooted trees is:

:<math> (2n-3)!! = \frac{(2n-3)!}{2^{n-2}(n-2)!} </math> for <math>n \ge 2</math>, <math>n</math> represents the number of leaf nodes.<ref name="Felsenstein1978">{{Cite journal |last=Felsenstein |first=Joseph |date=1978-03-01 |title=The Number of Evolutionary Trees |url=https://academic.oup.com/sysbio/article/27/1/27/1626689 |journal=Systematic Biology |language=en |volume=27 |issue=1 |pages=27–33 |doi=10.2307/2412810 |issn=1063-5157 |jstor=2412810}}</ref>

For bifurcating labeled trees, the total number of unrooted trees is:<ref name="Felsenstein1978"/>

:<math> (2n-5)!! = \frac{(2n-5)!}{2^{n-3}(n-3)!} </math> for <math>n \ge 3</math>.

Among labeled bifurcating trees, the number of unrooted trees with <math>n</math> leaves is equal to the number of rooted trees with <math>n-1</math> leaves.<ref name="Felsenstein">Felsenstein J. (2004). ''Inferring Phylogenies'' Sinauer Associates: Sunderland, MA.</ref>

The number of rooted trees grows quickly as a function of the number of tips. For 10 tips, there are more than <math>34 \times 10^6</math> possible bifurcating trees, and the number of multifurcating trees rises faster, with ca. 7 times as many of the latter as of the former.

{| class=wikitable sortable style=text-align:right
|+ Counting trees.<ref name="Felsenstein1978"/>
! Labeled<br>leaves !! Binary<br>unrooted trees !! Binary<br>rooted trees !! Multifurcating<br>rooted trees !! All possible<br>rooted trees
|-
| 1 || 1 || 1 || 0 || 1
|-
| 2 || 1 || 1 || 0 || 1
|-
| 3 || 1 || 3 || 1 || 4
|-
| 4 || 3 || 15 || 11 || 26
|-
| 5 || 15 || 105 || 131 || 236
|-
| 6 || 105 || 945 || 1,807 || 2,752
|-
| 7 || 945 || 10,395 || 28,813 || 39,208
|-
| 8 || 10,395 || 135,135 || 524,897 || 660,032
|-
| 9 || 135,135 || 2,027,025 || 10,791,887 || 12,818,912
|-
| 10 || 2,027,025 || 34,459,425 || 247,678,399 || 282,137,824
|-
|}