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