July 2, 2012, midnight by Rosalind Team
Topics: Combinatorics, Phylogeny
Counting Trees
A natural question is to be able to count the total number of distinct unrooted binary trees having
$n$ leaves, where each leaf is labeled by some taxon. Before we can count all these trees, however, we need to have a notion of when two such trees are the same.Our tool will be the split. Recall from “Creating a Character Table” that removing any edge from a tree
$T$ separates its leaves into sets$S$ and$S^{\textrm{c}}$ , so that each edge of$T$ can be labeled by this split$S \mid S^{\textrm{c}}$ . As a result, an unrooted binary tree can be represented uniquely by its collection of splits.
Two unrooted binary trees
Let
Given: A positive integer
Return: The value of
5
15