Counting Unrooted Binary Trees

https://rosalind.info/problems/cunr/

ROSALIND | Counting Unrooted Binary Trees

Problem

Two unrooted binary trees T1T1 and T2T2 having the same nn labeled leaves are considered to be equivalent if there is some assignment of labels to the internal nodes of T1T1 and T2T2 so that the adjacency lists of the two trees coincide. As a result, note that T1T1 and T2T2 must have the same splits; conversely, if the two trees do not have the same splits, then they are considered distinct.

Let b(n)b(n) denote the total number of distinct unrooted binary trees having nn labeled leaves.

Given: A positive integer nn (n≤1000n≤1000).

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

Sample Dataset

5

Sample Output

15

 

 이 문제는 unrooted binary tree의 leaf의 개수를 주고 구별되는 트리의 가짓수가 몇 개 있는지 출력하는 문제이다. 이 문제는 unrooted binary tree에서 leaf를 하나 더 늘리고 싶을 때, 하나의 edge를 골라 split하고 새로운 node를 연결하여 leaf의 개수를 늘린다는 발상을 가지면 풀 수 있다. 그렇기에 b(n)을 일종의 점화식으로 나타낼 수 있는데, leaf가 n-1개일 때의 가짓수에 그 때의 edge를 곱하면 구할 수 있다. b(n) = b(n-1) * (n-1의 edge수)이다. 

 edge의 개수는 leaf가 3일때 3개이고 leaf가 하나씩 늘때마다 2개씩 늘어나는 등차수열의 형식이다. 그러므로 edge의 개수는 = 2*n-3이다. 그러므로 b(n) = (2(n-1)-3) * b(n) = (2n-5) * b(n-1) 이다. 

 이를 간단하게 코드로 만들면 끝이다.

a=int(input())

b=1
for i in range(3,a+1):
    b*=2*i-5
print(b%1000000)