Ways to sum to $n$ with $m$ integers that are $\le k$ Given three natural numbers $n$, $m$ and $k$, how many ways are there to write $n$ as the sum of $m$ natural numbers in the set $\{0, 1, \ldots, k\}$, where order does matter?
I've seen the "Ways to sum $n$ with $k$ numbers", but never where the different numbers are restricted by an upper bound.
I'm not even sure how to proceed with this question. I have a python script to calculate this (in essence, it tries the $(k+1)^m$ possible sums, computes them, and returns the number of sums whose result is $n$). I do have some recurrence equations, but I'm almost 100% sure they don't help that much. By fixing the first number of the sum to be $0, 1, \ldots, k$, and writing $P(n, m, k)$ as the solution of the problem:
P(n, m, k) = P(n,     m - 1, k) + # If the first number is 0
             P(n - 1, m - 1, k) + # If the first number is 1
             ...
             P(n - k, m - 1, k) + # If the first number is k

and
P(n, 1, k) = 0 if n > k
             1 if n <= k

Can this be solved in a more elegant way than brute force?
 A: There are many known formulas for the restricted integer composition problem. The one you have given,
$$p(n,m,k)=\sum_{i=0}^k p(n-i,m-1,k)$$
characterizes restricted integer compositions as extended binomial coefficients. If $k=1$, this is simply the formula for the binomial coefficients ($C(m,n)=C(m-1,n)+C(m-1,n-1)$). So, your problem can be seen as a natural generalization of binomial coefficients and your numbers generate a Pascal triangle like array.
This sequence may also be of relevance http://oeis.org/A008287

EDIT 
To compute the number $p(n,m,k)$ based upon the above recurrence, set up a (sufficiently) large matrix $T(i,j)$, with all elements initialized to zero. Set $T(0,0)=1$. Then, for $i>0$, compute $T(i,j)=\sum_{i=0}^k T(i-1,j-i)$, until you arrive at your desired row $m$ and column $n$. This should be pretty fast, there is no need for exhaustive enumeration. For instance, a python script to compute $p(n,m,k)$ would be 

  n=8; m=6; k=9
  T=[[0 for i in xrange(100)] for j in xrange(100)] # enough memory
  T[0][0]=1
  for j in xrange(1,m+1):
      for i in xrange(n+1):
          for r in xrange(k+1):
             if i-r>=0: T[j][i]+=T[j-1][i-r]
  print T[m][n]


Runtime is $O(mnk)$.
A: There is a generating function for the sequence :
\begin{align*}
  G(x,y) &= \frac{1}{1-y\left(1+x+x^2+\cdots+x^k\right)} \\
  &= \frac{1-x}{1-(x+y)+y\, x^{k+1}}
\end{align*}
where $P(n,m,k)$ is given by the coefficient $\left[x^n\, y^m\right]$
E.g. $$P(8,6,9) = [x^8\, y^6] \frac{1-x}{1-(x+y)+y\, x^{10}} = 1287$$
A: It is not exactly what you want, but it is at least related:
OEIS A048887: Array T read by antidiagonals, where T(m,n) = number of compositions of n into parts <= m
What is missing is the condition that only those compositions are counted, which consist of exactly $m$ numbers, the above counts all.
So it could at least serve as an upper boundary. 
BTW I wondered how the Online Encyclopedia of Integer Series handles multidimensional series, that is an answer: a series in two dimensions is given in (anti-) diagonal enumeration.
