I need to know how to find the number of possible integer solutions to the following problem.

$$x_1 + x_2 + x_3 = 0 \text{ where }x_i \ge -5$$

Normally, I would do this problem by making it a distribution of identical objects problem by finding the amount of ways to fill each "box" with n different objects. However, I can't do that here (or at least I cannot figure out how to do it here). I know that the answer is

$$15+3-1\choose 15$$

I understand where the 3 and 1 come from, however, I do not understand where the 15 comes from (my only guess would be $5\cdot 3$, but I'm not sure). Thanks!


Let $y_i=x_i+5$. Our problem is equivalent to finding the number of non-negative solutions of $y_1+y_2+y_3=15$.

Or else let $z_i=x_i+6$. We want the number of positive solutions of $z_1+z_2+z_3=18$.

Both these problems are familiar to you.

I prefer the second. It is a standard "Stars and Bars" problem (look at the Wikipedia article).

We have $18$ candies in a row. There are $17$ "gaps" between them. We want to choose $2$ of these gaps to put a separator into. Then $z_1$ is the number of candies to the first separator, $z_2$ the number between the separators, and $z_3$ the rest.

There are $\dbinom{17}{2}$ ways to choose the $2$ gaps from the $17$ available. Alternately, you can write this as $\dbinom{17}{15}$, since in general $\dbinom{n}{k}=\dbinom{n}{n-k}$. Or else you can think of the gap choosing process as deciding on the $15$ places where the separators won't go.

The more common thing would be to say that the answer is $\dbinom{17}{2}$. But saying $\dbinom{17}{15}$ is entirely equivalent.

  • $\begingroup$ Can you explain the let statement in the beginning a bit more? I don't quite understand where that came from. Thanks $\endgroup$ – audiFanatic Oct 27 '12 at 21:33
  • 1
    $\begingroup$ Take any solution $(x_1,x_2,x_3)$ of the original problem. Since $y_i=x_i+5$, all the $y_i$ are $\ge 0$. And since $x_1+x_2+x_3=0$, we have $(y_1-5)+(y_2-5)+y_3-5)=0$, giving $y_1+y_2+y_3=15$. Conversely, suppose that we have a non-negative solution of $y_1+y_2+y_3=15$. We can rewrite this as $(x_1+5)+(x+2+5)+(x_3+5)=15$, which says $x_1+x_2+x_3=0$. Moreover, all the $x_i$ are $\ge -5$. So there is a one to one correspondence between solutions of the given problem and non-negative solutions of $y_1+y_2+y_3=15$. Thus the number of solutions to the two problems is the same. $\endgroup$ – André Nicolas Oct 27 '12 at 21:42
  • $\begingroup$ Perfect, I understand perfectly now! Thanks Andre $\endgroup$ – audiFanatic Oct 27 '12 at 22:02

This is not really a different solution to that of André Nicolas, but just a remark to say you do not need to prefer his second form of the equation. So, as he explained, by adding $5$ to each of $x_1,x_2,x_3$ translate to problem into counting the solutions of $y_1+y_2+y_3=15$ with integers $y_1,y_2,y_3\geq0$. Problems in this form are more common than those with conditions of being strictly positive; for instance this is how one counts the number of monomials in variables $a,b,c$ that have total degree $15$. So there is interest in being able to handle it (mentally) without transforming into a problem with strictly positive unknowns.

So instead of doing "stars and bars", think "bars and plusses". Imagine a solution of $y_1+y_2+y_3=15$ with the numbers $y_1,y_2,y_3\geq0$ written out in unary notation (repeated vertical bars); any possible number $0$ will have an empty representation. That gives (to the left of the "=" sign) a total of $15+2=17$ vertical strokes for the bars and the plus signs. So one can form any solution by taking $17$ strokes "|" and crossing any $2$ of them to form a "+"; this can be done in $\binom{17}2$ different ways, all giving valid solutions.


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.