# UVa 10007

## Contents

## 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