Hi,

I'm trying to solve this problem, which asks the number of labeled trees with *N* vertices and maximum degree *K* (modulo 10^{9} + 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 *n*^{n - 2}. Then *f*(*n*, *n* - 1) = *n*^{n - 2}.

Thanks in advance for any help!

Auto comment: topic has been updated by pimenta (previous revision, new revision, compare).http://codeforces.com/blog/entry/20335

There are at least 4 solutions there, including one which works in

O(nlog^{2}n) (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

vcontains in sequence exactlydegree_{v}- 1 times. That means you should calculate numberf(K) of sequences of numbers from 1 tonhaving lengthn- 2, such that every number contains at mostK- 1 times. It can be done with some combinatorics or dynamic programming.