pimenta's blog

By pimenta, 8 years ago,

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!

• 0

 » 8 years ago, # |   0 Auto comment: topic has been updated by pimenta (previous revision, new revision, compare).
 » 8 years ago, # | ← Rev. 3 →   0 http://codeforces.com/blog/entry/20335There 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?)
•  » » 8 years ago, # ^ |   0 Thanks!
•  » » 8 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 8 years ago, # | ← Rev. 2 →   0 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.