count the number of series of length k of sum M let $N,k, M$ be positive whole numbers such that $M \leq kN$ what is the number of sequences $\{x_i\}_{i=1}^k$ such that $\forall i \; 0\leq x_i\leq N$ and $\sum_{i=1}^kx_i = M$
 A: Define $f_{N}(M,k)$ to be the number of sequences of length $k$ that sum to $M$ and have terms bounded by $N$. It's easy to see that:
$$f_N(M,k) = \begin{cases}
\sum\limits_{x=0}^{\min(M, N)} f_N(M-x,k-1) & \text{if } k > 0 \text{ and } M\geq 0\\
                                          1 & \text{if } k = 0 \text{ and } M=0\\
                                          0 & \text{otherwise} \end{cases}$$
You can compute this efficiently with Dynamic Programming, or you can work out what the generating function turns out to be:
$$ G(x, y) = \sum_{k=0}^\infty \sum_{m=0}^\infty f_{N}(m,k)x^my^k$$
I will leave this as a hint, because it's very tedious to do the expansion and work out the generating function, but in the end, if you're successful, you should get some kind of polynomial in $x$ and $y$ such that the coefficient of $x^My^k$ is the correct answer.
edit
I'm coming back to this answer to adjust it. The answer to the question is the coefficient of $x^M$ in the expression $(1 + x + x^2 + \dots + x^N)^k$, and if you want to compute this exactly, you need to find the Discrete Fourier Transform of the polynomial $(1+x+x^2+\dots+x^N)$, which can be done in $\mathcal{O}(N \log N)$, then exponentiate each point in the DFT to the power $k$ using repeated squaring (overall, this will be $\mathcal{O}(N \log k)$ time), and then invert the result (find the inverse DFT) in order to get the coefficients again. Then, you can just look at the coefficient of $x^M$ and you have your answer. I think this is the most computationally efficient method, but I'm probably wrong, as the polynomial we're dealing with is very special. Overall, this algorithm is $\mathcal{O}(N\log N + N\log k)$, but I think there might be an $\mathcal{O}(N)$ algorithm if you're careful enough.
