Counting restricted compositions

Question

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 compositions 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 compositions 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 $$

I wonder whether there is a more combinatorial solution to this problem. Perhaps some closed formula exists?

Answer 1

Assuming $N=2n$, note that without $N/2$ condition the number of solutions is ${N+S-1}\choose{S-1}$. You only need to subtract the cases where $x_i>n$ for some $i$. Hence the closed form is ${N+S-1}\choose{S-1}$-$S\cdot$ ${N+S-n-2}\choose{S-1}$. You don't need to add the cases where $x_i$ and $x_j$ are both larger than $n$ since that's impossible. Similarly you can compute the closed form for $N=2n+1$.

Answer 2

Have a look to this related post where it is explained that $$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right.$$

is given by $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s} {r}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m \hfill \\ k \hfill \\ \end{gathered} \right)\left( \begin{gathered} s + m - 1 - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} $$ You will find there also a recurrence formula.

In your case, clearly $$ s = N\quad r = \left\lfloor {N/2} \right\rfloor \quad m = S $$