Tricky problem. The most tricky part is to efficiently count the number of sums with given length knowing that each element must be bigger than smallest value (sv) in the top sum and every element must not be greater than maximum number on dice. Having calculated the number of these sums the rest is rather easy as the count for given length (gl) of elements greater than the smallest value in the top sum.

number_of_sums * C(n, gl) * (C(n-k, 0) * (sv - 1)^0 + C(n-k, 1) * (sv- 1)^1 + C(n-k, 2) * (sv-1)^2 + ... + C(n-k, n - k) * (sv-1)^(n-k))