pimenta's blog

Number of labeled trees with N vertices and max. degree K
By pimenta, 9 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pimenta (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

http://codeforces.com/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?)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply