# Counting restricted partitions

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.

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.