UVa 10007

From Algorithmist
Jump to navigation Jump to search

10007 - Count the Trees[edit]

Summary[edit]

The task is to find the count of rooted labeled binary trees on N vertices.

Explanation[edit]

Counts of unlabeled rooted binary trees with N vertices are exactly the famous Catalan numbers, i.e.,

.

Once we have an unlabeled rooted binary tree with N vertices, there are exactly N! ways to add the labels. We can do this for each of the trees, thus the final answer is given by the formula

.

Implementations[edit]

As the example I/O shows, this is intended to be a BigNum problem. You only need to implement integer multiplication, as the answer can be obtained by multiplying the numbers (N+2) to 2N.

As the set of possible inputs is limited, it is possible to precompute the answers in some scripting language that supports big integers (Python, bc) and submit a program that has the answers hard-wired as string constants.

Input[edit]

1
2
10
25
0

Output[edit]

1
4
60949324800
75414671852339208296275849248768000000

Reference[edit]

  1. http://mathworld.wolfram.com/CatalanNumber.html