Hi,
I'm trying to solve this problem, which asks the number of labeled trees with N vertices and maximum degree K (modulo 109 + 7), where 1 ≤ N ≤ 100 and 1 ≤ K ≤ N.
What I have so far:
If f(n, k) is the answer, then f(n, k) = f(n, k - 1) + g(n, k), where g(n, k) is the number of labeled trees with n vertices, at least one vertex with degree k and no vertex with degree larger than k. But, is there a formula for g(n, k)?
f(n, 2) = n! / 2, because this is the case of a "list" tree. The answer is the number of permutations (n!), removing duplicates ( / 2), such as 1<->2<->3 and 3<->2<->1 (for f(3, 2)).
And, of course, f(n, 1) = 0, f(1, k) = 1, f(2, k) = 1 and f(n, n) = f(n, n - 1).
There is also Cayley's formula: the number of labeled trees with n vertices is nn - 2. Then f(n, n - 1) = nn - 2.
Thanks in advance for any help!
Auto comment: topic has been updated by pimenta (previous revision, new revision, compare).
http://codeforces.me/blog/entry/20335
There are at least 4 solutions there, including one which works in O(nlog2n) (apparently for any modulo, as I've just learned. How did I miss that post 5 weeks ago?)
Thanks!
Well, actually it's easy for the generating polynomial exponentiation to work with 10^9+7.
Just use Number Theoretic Transform with Chinese remainder theorem. Just compute it for 2 primes of form 2^b+1 (where b<60 is the desired bits in maximum of N). You will have to use __int128 in c++ or BigInteger in Java though for the last few computations. See the codeforce discussion here.
There is bijection between labeled trees and Prufer sequences. Every vertex v contains in sequence exactly degreev - 1 times. That means you should calculate number f(K) of sequences of numbers from 1 to n having length n - 2, such that every number contains at most K - 1 times. It can be done with some combinatorics or dynamic programming.