UVa 10007
From Algorithmist
Contents |
[edit] 10007 - Count the Trees
[edit] Summary
The task is to find the count of rooted labeled binary trees on N vertices.
[edit] Explanation
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
.
[edit] Implementations
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.
[edit] Input
1 2 10 25 0
[edit] Output
1 4 60949324800 75414671852339208296275849248768000000
