# Number of non-negative solutions of an equation with restrictions

Q: Find the number of non-negative solutions of the equation $$r_1+r_2+r_3+\ldots +r_{2n+1}=R$$ when $0 \le r_i \le \min(N,R)$ and $0\le R\le (2n+1)N$.

My Attempt: I tried the stars and bars method but it did not work properly. If the upper-bound for $r_i$ was not there, then the answer would have been $\binom{2n+1+R-1}{R}=\binom{2n+R}{R}$.

But how do I deal with this problem in the given situation?

EDIT: For the problem, you can simply consider $R$ as fixed and I wish to calculate the number of non-negative solutions to the given equation only.

Let $$A_k = \{(r_1,\cdots ,r_{2n+1}):\sum _{i\in[2n+1]} r_i=k,0\leq r_i \leq min \{N,k\}\},$$ So you want $$\sum _{k = 0}^{(2n+1)N}|A_k|,$$ notice that it does not matter the restriction $r_i\leq min \{N,k\}$ because $r_i\leq k$ so you just have to worry about $r_i\leq N.$
You will have to use inclusion exclusion in the following way:
Let $C_k = \{(r_1,\cdots ,r_{2n+1}):\sum _{i\in[2n+1]} r_i=k,r_i\geq 0\}$(all the possibilities) and $B_{k,j}=\{(r_1,\cdots , r_{2n+1}):r_{j}>N,\sum r_i=k\},$(the ones you do not want) so that you have $$A_k=C_k\setminus \bigcup _{j=1}^{2n+1} B_{k,j},$$ then by inclusion-exclusion principle you have $$|A_k|=|C_k|-\sum _{l = 1}^{2n+1}(-1)^{l-1}\sum _{a_1<a_2< \cdots <a_l}|\bigcap_{s\in [l]} B_{k,a_s}|,$$ it is clear that, by stars and bars argument (as you noticed), $|C_k|=\binom{k+2n}{2n}$ and intersection of the $B_{k,a_l}$ is just imposing conditions as follows, elements in $\bigcap_{s\in [l]} B_{k,a_s}$ look like $$(r_1,\cdots ,r_{a_1},\cdots ,r_{a_2},\cdots,r_{a_l},\cdots ,r_{2n+1})=(r_1,\cdots ,r^*_{a_1}+N+1,\cdots ,r^*_{a_2}+N+1,\cdots,r^*_{a_l}+N+1,\cdots ,r_{2n+1}),$$ so it is just a rename, namely, $r_{a_s}=N+1+r^*_{a_s}$ for the special ones and $r_i=r^*_i$ for the remaining (hence $0\leq r^*_{i}$).
So $$k=\sum _{i=1}^{2n+1}r_i=(N+1)l+\sum _{i=1}^{2n+1}r^*_i,$$ hence $k-(N+1)l=\sum _{i=1}^{2n+1}r^*_i$ so use stars and bars again and you will get it.

By using also Hockey stick identity, answer should look like : $$\sum _{l=0}^{2n+1}(-1)^l\binom{2n+1}{l}\binom{(N+1)(2n+1-l)}{2n+1}.$$
EDIT: An intermediate step in between the answer for fixed $R$ and the answer for every $R$ is $$\sum _{k = 0}^{(2n+1)N}\underbrace{\sum _{l=0}^{2n+1}(-1)^l\binom{2n+1}{l}\binom{k-(N+1)l+2n}{2n}}_{\text{This would be the answer for fixed R}}$$

• you might be interested to know that the formula you gave is "nearly" correct: see the answer below. – G Cab Jan 27 '17 at 13:51
• @Phicar Thanks for your answer. By the time I am writing this, I have not completed reading your total answer. But I would like to point out that I want an expression for $|A_k|$ in general, not the summation of $|A_k|$ as you have mentioned. My question formulation might have misled you, I regret it. Please consider this revision. – SchrodingersCat Jan 27 '17 at 15:11
• @GCab What do you mean by "nearly"? SchrodingersCat: You still can deduce it from the part i start calculating $|A_k|$ but the answer in the spoiler section is not going to be good for you tho. I will edit it in a while, i suggest you specify that $R$ is fixed then in the question. – Phicar Jan 27 '17 at 15:19
• I mean that the inclusion\exclusion approach is valid, and that the "structure" of the resulting formula is on the target, but something is missing: see the formula in my answer. – G Cab Jan 27 '17 at 15:28
• @GCab I guess the confusion is that you have $R$ fixed and for the question i understood $R$ was moving. SchrodingersCat: I edited it, from the edition you get my original answer by commuting the sums and using Hockey stick identity. – Phicar Jan 27 '17 at 17:55

So we have $$\left\{ \begin{gathered} 0 \leqslant R \leqslant \left( {2n + 1} \right)N \hfill \\ 0 \leqslant r_{\,i} \leqslant \min (N,R) \hfill \\ r_{\,1} + r_{\,2} + \cdots + r_{\,2n + 1} = R \hfill \\ \end{gathered} \right.$$ understanding (from the context) that the $r_i$ are integers.
The formulation that you give for the bounds is quite peculiar, since from it we get $$r_{\,\text{avg}} = \frac{R} {{2n + 1}} \leqslant N\quad \quad M = \min (N,R) = \left\{ {\begin{array}{*{20}c} N & {\left| {\;\frac{R} {{2n + 1}} \leqslant N \leqslant R} \right.} \\ R & {\left| {\;R \leqslant N} \right.} \\ \end{array} } \right.$$ Now, if the variables are upper limited to $M=N$, then the average will definitely be not greater than $N$, while if $M=R$, then the upper bound is implied by the sum.

In any case, your question turns down to finding (apart the change in denominating the parameters) $$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.$$ where $N_{\,b} (s,r,m)$ is given by the closed summation

$$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)}$$

as explained in this post and in in this other one.

• What is the $b$ in your formula $N_b$? Can you please check it? – SchrodingersCat Jan 27 '17 at 16:32
• @SchrodingersCat, the $b$ in $N_b$ does not stand for a parameter or anything to be accounted for: it is just a suffix to distinguish this $N$ among others N's (and that then I had to keep to avoid confusion). Can you pls. clarify the meaning of $R$ and $N$ ? I do not get the Phicar's comment about "moving" and " fixed" R. – G Cab Jan 27 '17 at 22:00
• Actually R and N are as I have mentioned in the question. Now R takes integral values from $0$ to $2n+1$. Phicar's answer initially had all solutions for all equations with the different R. But I wanted the number of solutions for any particular value of R. That's what he meant. – SchrodingersCat Jan 28 '17 at 3:57