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

combinatoricsnatural numbers

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?

Best Answer

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

Related Question