Counting Rooted Binary Trees solved by 330

July 2, 2012, midnight by Rosalind Team

Topics: Combinatorics, Phylogeny

From Unrooted to Rooted Treesclick to expand

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?

Problem

As in the case of unrooted trees, say that we have a fixed collection of n taxa labeling the leaves of a rooted binary tree T. You may like to verify that (by extension of “Counting Phylogenetic Ancestors”) such a tree will contain n1 internal nodes and 2n2 total edges. Any edge will still encode a split of taxa; however, the two splits corresponding to the edges incident to the root of T will be equal. We still consider two trees to be equivalent if they have the same splits (which requires that they must also share the same duplicated split to be equal).

Let B(n) represent the total number of distinct rooted binary trees on n labeled taxa.

Given: A positive integer n (n1000).

Return: The value of B(n) modulo 1,000,000.

Sample Dataset

4

Sample Output

15

Please login to solve this problem.

Welcome to Rosalind!

Rosalind is a platform for learning bioinformatics through problem solving.
Please login with Google/Twitter/Facebook or register a new account.