Counting Trees with a Given Degree Sequence

ID: 15565

Type: Default

1000ms

256MiB

You are given a tree with n nodes labeled v₁, v₂, ..., v_n. The degree of the i-th node is given as d_i. Your task is to determine the number of different trees that can have this degree sequence.

Recall that a sequence of degrees d₁, d₂, ..., d_n can form a tree if and only if:

\sum_{i=1}^{n} d_i = 2(n-1)

When the sequence is valid, the number of labeled trees with the given degree sequence is given by the formula:

\frac{(n-2)!}{\prod_{i=1}^{n} (d_i-1)!}

For the special case when n = 1, the tree is valid only if d₁ = 0, and the answer is 1.

inputFormat

The first line contains an integer n representing the number of nodes.

The second line contains n space-separated integers d₁, d₂, ..., d_n, where d_i is the degree of node v_i.

outputFormat

Output a single integer, the number of different trees that have the given degree sequence. If the sequence is invalid, output 0.

sample

3
1 1 2

#P2290. Counting Trees with a Given Degree Sequence

Counting Trees with a Given Degree Sequence