1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.