4
$\begingroup$

How many possible solutions are there for this equation:

$|x_1| + x_2+x_3 = 16$ ; $x_1 \in Z$ $x_2,x_3 \in N$

I know it's a simple combinatorics question but I'm still having trouble figuring it out.

Since $x_1$ is an integer, there could be infinite solutions for this equation (I know this is probably not true but that is how I see it).

I know that in the case that $x_1 = 0$ there could be ${16+2-1 \choose 2-1}$ possible solutions.

The other case is when $x_1$ is non zero, when it is positive, the total # of combinations is:

${16+3-1 \choose 3-1}$ and another case where $x_1$ is negative.

Hence: ${16+2-1 \choose 2-1} + 2 \cdot {16+3-1 \choose 3-1}$

However, I checked and in my book it says that the solution is: ${16+2-1 \choose 2-1} + 2 \cdot {15+3-1 \choose 3-1}$

I'm having trouble understanding the ${15+3-1 \choose 3-1}$ part, can anyone please explain this to me?

I also noticed that this same question was posted in this site but wasn't explained appropriately, so I posted again.

Many thanks.

$\endgroup$
  • $\begingroup$ One thing I could not make out: If $x_1=0$ then you write of $17$ solutions which actually include cases where $x_2=0,x_3=16$ and $x_2=16,x_3=0$. But $x_2,x_3 \in \mathbb{N}$ and $\mathbb{N}$ does not contain $0$. Than why so? $\endgroup$ – SchrodingersCat Dec 8 '15 at 19:12
  • $\begingroup$ @Aniket Actually, $\mathbb{N}$ containing $0$ is a pretty common practice. Not as common as it not, but not completely foreign. $\endgroup$ – MCT Dec 8 '15 at 19:28
1
$\begingroup$

If $x_1 = 0$ then there are $15$ pairs for $x_2, x_3$.

If $x_1 = \pm 1$ then there are $14$ pairs.

If $x_1 = \pm 2$ then there are $13$ pairs.

if $x_1 = \pm 13$ then there are $2$ pairs.

if $x_1 = \pm 14$ then there is $1$ pair.

So it's a stars and bars problem for the second part. Each bin contains at least one of the $15$ object (because you're already handled the zero case) and there are three bins. This is expressed (verbatim!) as

$${15 + 3 - 1 \choose 3-1},$$

and you get the factor of $2$ from the absolute value.

$\endgroup$
  • $\begingroup$ Is that not the expression for a nonnegative composition, when we want a strictly positive composition? $\endgroup$ – Kevin Long Dec 8 '15 at 19:44
  • $\begingroup$ I think so @KevinLong, in the sense that we're looking at the natural numbers? Is that what you're getting at? $\endgroup$ – John Dec 8 '15 at 19:55
  • $\begingroup$ Ah, @John, if I follow, I'm being close-minded in not including $0$ in the natural numbers. I always forget the variations of convention in the world. $\endgroup$ – Kevin Long Dec 8 '15 at 20:00
  • 1
    $\begingroup$ @KevinLong I learned them as natural numbers ($1, 2, 3, ...$), whole numbers $(0, 1, 2, 3, ...)$ and integers $(0, \pm 1, \pm 2, ...)$ but I'm sure there are other conventions. $\endgroup$ – John Dec 8 '15 at 20:46

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.