2
$\begingroup$

Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$: $$ N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq \frac{N}{2} $$

Two partitions are considered distinct if any of the summands has distinct values in them. For example, if $N = 4$ and $S = 3$ then there are 6 possible partitions: $$(1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2, 0), (2, 0, 2), (0, 2, 2)$$

I've derived a dynamic programming solution. Let $d_{ns}$ be the number of above defined partitions of number $n$ with $s$ summands (each not greater than $\frac{N}{2}$). Then $$ d_{0s} = 1, ~~~ s \geq 0 $$ $$ d_{n0} = 0, ~~~ n > 0 $$ $$ d_{ns} = \sum_{k = 0}^{\max \left(n, \frac{N}{2} \right)}d_{n-k,s-1}, ~~~ sn > 0 $$

It works fine but i consider this approach to be too slow from algorithmic point of view. It requires roughly $O(N^2 S)$ operations.

So here's my question. Can this computation be done faster? Perhaps via some other recurrence or some smarter way to fill the dynamic programming table for recurrence described above.

$\endgroup$
2
$\begingroup$

First, let us note that the number of ways to write $N$ as a sum of $S$ non-negative integers is exactly $\binom{N+S-1}{N}$. Indeed, the partition $N=x_1+\cdots+x_S$ corresponds to the string $\ast^{x_1}|\ast^{x_2}|\cdots|\ast^{x_S}$ (where $\ast^x$ means $x$ many stars), which contains $N$ stars and $S-1$ bars, and conversely any such string corresponds to a partition.

In your case you have the additional constraint that all $x_i$s are at most $N/2$. Note that at most one $x_i$ can be more than $N/2$. If $x_i > N/2$, then the number of ways to fill the rest of the $x_j$s is exactly $\binom{N-x_i+S-2}{S-1}$. Therefore the number of ways to write $N$ as a sum of $S$ non-negative integers which are at most $N/2$ is $$ \binom{N+S-1}{S-1} - S\sum_{x=\left\lceil \frac{N+1}{2} \right\rceil}^N \binom{N-x+S-2}{S-2} = \binom{N+S-1}{S-1} - S\sum_{y=0}^{\left\lfloor \frac{N-1}{2} \right\rfloor} \binom{y+S-2}{S-2} = \binom{N+S-1}{S-1} - S \binom{\left\lfloor \frac{N-1}{2} \right\rfloor+S-1}{S-1}. $$ You can calculate this closed form using $O(S)$ arithmetic operations.

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