Ways to sum to $n$ with $m$ integers that are $\le k$

Question

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?

Answer 1

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)$.

Answer 2

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.

Answer 3

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$$