July 2, 2012, midnight by Rosalind Team

**Topics**:
Combinatorics,
Phylogeny

## From Unrooted to Rooted Trees

Recall that a rooted binary tree is a binary tree for which the root is the only node of degree 2. Such a tree differs from an unrooted binary tree only in the existence of the root.

Different phylogenetic methods may be better suited to rooted or unrooted trees. If a method produces an unrooted tree, then the root (i.e., the common ancestor of all taxa) could theoretically be placed anywhere. Thus, there will be more rooted binary trees than unrooted binary trees on the same number of taxa. The question is: how many more rooted trees are there?

As in the case of unrooted trees, say that we have a fixed collection of

Let

Given: A positive integer

Return: The value of

4

15