2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ you might be interested to know that the formula you gave is "nearly" correct: see the answer below. $\endgroup$ – G Cab Jan 27 '17 at 13:51
  • $\begingroup$ @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. $\endgroup$ – SchrodingersCat Jan 27 '17 at 15:11
  • $\begingroup$ @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. $\endgroup$ – Phicar Jan 27 '17 at 15:19
  • $\begingroup$ 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. $\endgroup$ – G Cab Jan 27 '17 at 15:28
  • $\begingroup$ @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. $\endgroup$ – Phicar Jan 27 '17 at 17:55
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What is the $b$ in your formula $N_b$? Can you please check it? $\endgroup$ – SchrodingersCat Jan 27 '17 at 16:32
  • $\begingroup$ @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. $\endgroup$ – G Cab Jan 27 '17 at 22:00
  • $\begingroup$ 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. $\endgroup$ – SchrodingersCat Jan 28 '17 at 3:57

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.