# Integer Programming Complexity

I would like to seek help on the complexity of the following problem. Given positive integers $m$, $n$ and $D$, find all sequences $0 \lt a_1 \lt a_2 \lt \dots \lt a_n$ are there such that:

1. each $a_i\in\{1, \dots, m\}$
2. $\sum_{i=1}^n a_i = D$

I want to know the complexity with respect to $m$, $n$, $D$. To what extend of $m$, $n$, $D$ that is computationally feasible?

Thanks very much.

This can be calculated using dynamic programming: for each $0 \leq T \leq D$ and $0 \leq \ell \leq n$, calculate $C(T,\ell)$, which is the number of solutions over $\{1,\ldots,m\}$ of $\sum_{i=1}^\ell a_i = T$. The base case is $C(0,0) = 1$ and $C(T,0) = 0$ if $T > \ell$. For $\ell > 0$, we have the formula $C(T,\ell) = \sum_{S=\max(T-m,0)}^{T-1} C(S,\ell-1)$. The answer is $C(D,n)$. This algorithm runs in time $O(mnD)$.

Equivalently, you are looking for the coefficient of $x^T$ in the generating function $(x+\cdots+x^m)^n = x^n\left(\frac{1-x^m}{1-x}\right)^n$. This expression can be massaged to give an explicit formula involving a double summation with alternating signs.