1
$\begingroup$

The problem of enumerating all lists of integers such that the list sums to a known value $k$ is well known and takes exponential time to compute.

If the problem is restricted so that the integers must be greater than $\sqrt{k}$, I feel like the runtime should now be quadratic. Is there a proof of this? More generally, if I restrict the integers to be greater than $l$, how is the runtime affected?

$\endgroup$
1
  • 1
    $\begingroup$ I think you're not interested so much in the runtime, but rather in the number of such sequences. $\endgroup$ Jul 27 at 17:26
3
$\begingroup$

The number of sequences of non-negative integers of length $\ell$ summing to $m$ is $\binom{m+\ell-1}{\ell-1}$. This shows that the number of sequences of integers, each at least $t$, summing to $k$ is $$ \sum_{\ell=1}^{\lfloor k/t \rfloor} \binom{k-\ell t}{\ell - 1}. $$ For example, if $t = \lfloor \sqrt{k}+1 \rfloor$, then we can choose $\ell \approx \sqrt{k}/2$ to get at least $\binom{\Theta(k)}{\Theta(\sqrt{k})}$ many sequences, which is $\exp \Theta(\sqrt{k} \log k)$; this is tight up to the hidden constant.

$\endgroup$
1
  • $\begingroup$ they are called compositions of $m$ in combinatorics parlance $\endgroup$
    – Nikos M.
    Jul 27 at 20:11

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.