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
    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.