How many non-negative integer solutions are there for $a+b+c+d=25$ if $a\geq 1, b\geq 2,c\leq 6,d\leq 14$

So first I let $x= a-1$, $y=b-2$ and get:


And if all are non-negative I get that there are ${n+k-1\choose k-1} ={25\choose 3}$ solutions

Then I need to subtract the solutions where $c\geq 7,d\geq 15$

Let $z= c-7$ then $x+y+z+d=15$ and there are ${18\choose 3}$ non negative solutions

Let $w= d-15$ then $x+y+c+w=7$ and there are ${10\choose 3}$ non negative solutions.

And combining $z= c-7, w=d-15$ gives $x+y+z+w=0$, which will have only $1$ solution

So there are ${25\choose 3}-{18\choose 3}-{10\choose 3}-1$ solutions.

Does this seem correct?

  • 1
    $\begingroup$ You need to consider the case where $c\ge7,d\le14$, and $c\le6,d\ge15$. After doing so, use some Inclusion-Exclusion Principle to get the number of solution. $\endgroup$ – sentheta Apr 21 '20 at 3:11
  • $\begingroup$ So I shouldnt remove all cases where $d\geq 15, c\geq 7$. I've removed some cases twice right? $\endgroup$ – AColoredReptile Apr 21 '20 at 3:20
  • $\begingroup$ Yes, it is removed twice so you need to have it in the total sum. $\endgroup$ – sentheta Apr 21 '20 at 3:25
  • 1
    $\begingroup$ Shouldn't it be $\binom{25}3-\binom{18}3-\binom{10}3+1$? $\endgroup$ – bof Apr 21 '20 at 3:59

Your solution is almost correct.

You subtract the case $"c\geq 7\; and\;d\geq 15"$ once in the case $c\geq 7$ and once in the case $d\geq 15$. So, you need to add the $1$ at the end.

Here for reconfirmation of the result the same calculation using generating functions:

$$[x^{22}]\frac{1}{1-x}\cdot\frac{1}{1-x}\cdot\frac{1-x^7}{1-x}\cdot\frac{1-x^{15}}{1-x} = [x^{22}]\frac{1-x^7-x^{15}+x^{22}}{(1-x)^4}$$ $$=[x^{22}](1-x^7-x^{15}+x^{22})\sum_{n \geq 0}\binom{n+3}3x^n$$ $$=\binom{25}3 - \binom{18}3-\binom{10}3 + \binom{3}3$$


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.