4
$\begingroup$

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!

2 Answers 2

5

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.

  • 0
    Can you explain the let statement in the beginning a bit more? I don't quite understand where that came from. Thanks2012-10-27
  • 1
    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.2012-10-27
  • 0
    Perfect, I understand perfectly now! Thanks Andre2012-10-27
0

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.