1
$\begingroup$

For equation $$ x_1+x_2+x_3 = 15 $$ Find number of positive integer solutions on conditions: $$ x_1<6, x_2 > 6 $$ Let: $y_1 = x_1, y_2 = x_2 - 6, y_3 = x_3$ than, to solve the problem, equation $y_1+y_2 +y_3 = 9$ where $y_1 < 6,0<y_2, 0<y_3 $ has to be solved. Is this correct?

To solve this equation by inclusion-exclusion, number of solution without restriction have to be found $C_1 (3+9-1,9)$ and this value should be subtracted by $C_2 (3+9-7-1,2)$ , (as the negation of $y_1 < 6$ is $y_1 \geq 7$). Thus: $$ 55-6=49 $$ Is this the correct answer ?
Problem must be solved using inclusion-exclusion...

$\endgroup$
1
  • $\begingroup$ You solved the problem in the nonnegative integers rather than the positive integers. $\endgroup$ – N. F. Taussig Oct 16 '15 at 21:58
2
$\begingroup$

Here is a different way to break it down $$ x_1\in\{1,2,3,4,5\} $$ and given $x_1$ we then have $x_1+x_2<15$ and $x_2>6$ combined as $$ 6<x_2<15-x_1 $$ And whenever $x_1$ and $x_2$ are given, the value of $x_3$ follows from them.

For $x_1=5$ we then have $x_2\in\{7,8,9\}$ so three choices for $x_2$. Each time $x_1$ is decreased by $1$ we gain one option for $x_2$. Thus we have a total of $$ 3+4+5+6+7 = 25 $$ sets of integer solutions under the given constraints.


I ran the following code snippet in Python which confirmed the figure of 25:

n = 0
for x1 in range(1,16):
    for x2 in range(1,16):
        for x3 in range(1,16):
            if x1 < 6 and x2 > 6 and x1+x2+x3 == 15:
                n += 1
                print n, ":", x1, x2, x3

I understand that I did not answer the question using the method required, but I wonder why I find the number of solutions to be $25$ whereas the OP and the other answer find it to be $49$. Did I misunderstand the question in the first place?

$\endgroup$
1
  • $\begingroup$ No, I think you are correct on the answer. See my comment below. $\endgroup$ – Brian Tung Oct 16 '15 at 19:06
2
$\begingroup$

You solved the problem in the nonnegative integers rather than the positive integers.

You wish to determine the number of solutions of the equation $$x_1 + x_2 + x_3 = 15 \tag{1}$$ in the positive integers subject to the constraints $x_1 < 6$ and $x_2 > 6$.

Let's deal with the constraint $x_2 > 6$ first. Let $y_2 = x_2 - 6$. Then $y_2$ is a positive integer. Substituting $y_2 + 6$ for $x_2$ in equation 1 yields \begin{align*} x_1 + y_2 + 6 + x_3 & = 15\\ x_1 + y_2 + x_3 & = 9 \tag{2} \end{align*} Equation 2 is an equation in the positive integers. A particular solution of equation 2 in the positive integers corresponds to a placement of addition signs in two of the eight spaces between successive ones in a row of nine ones. For instance, $$1 1 + 1 1 1 1 1 + 11$$ corresponds to the solution $x_1 = 2$, $y_2 = 5$, and $x_3 = 2$ (or $x_1 = 2$, $x_2 = 11$ and $x_3 = 2$ in equation 1), while $$1 1 1 1 + 1 1 + 1 1 1$$ corresponds to the solution $x_1 = 4$, $y_2 = 2$, and $x_3 = 3$ (or $x_1 = 4$, $x_2 = 8$, and $x_3 = 3$ in equation 1). Therefore, the number of solutions of equation 2 is $$\binom{8}{2}$$ From these, we must exclude those solutions in which $x_1 \geq 6$. Assume $x_2 \geq 6$. Let $y_1 = x_1 - 5$. Then $y_1$ is a positive integer. Substituting $y_1 + 5$ for $x_1$ in equation 2 yields \begin{align*} y_1 + 5 + y_2 + x_3 & = 9\\ y_1 + y_2 + y_3 & = 4 \tag{3} \end{align*} Equation 3 is an equation in the positive integers. The number of solutions of equation 3 is the number of ways we can place two addition signs in the three spaces between successive ones in a row of four ones, which is $$\binom{3}{2}$$
Hence, the number of solutions of equation 1 subject to the constraints $x_1 < 6$ and $x_2 > 6$ is $$\binom{8}{2} - \binom{3}{2}$$

$\endgroup$
2
$\begingroup$

(This corrects for the restriction that the integers are positive and not non-negative. Thanks for those who have commented to point this out.)

As the restrictions specify $x_1>0, x_2>6, x_3>0$ and $x\in\mathbb Z$, this is the same as $x_1\geq1, x_2\geq7, x_3\geq 1$.

First we "reserve" $1$ for $x_1$, $7$ for $x_2$ and $1$ for $x_3$ and apply stars-and-bars on the remaining. $$x_1+x_2+x_3=15\\ (\overbrace{y_1+1}^{x_1})+(\overbrace{y_2+7}^{x_2})+(\overbrace{y_3+1}^{x_3})=15\\ y_1+y_2+y_3=6 $$

$$\large\overbrace{*\;*}^{y_1}\;\bigl|\;\overbrace{*\;*}^{y_2}\;\bigl|\;\overbrace{*\;*}^{y_3}$$ Using stars-and-bars, without applying the upper constraint $x_1<6$, number of combinations is $$\binom {6+2}2$$ With the restriction $x_1<6$ which is the same as $y_1<5$ impossible combinations are for $y_1\geq 5$. From the $6$ elements, remove $5$, and use stars-and-bars. Number of impossible combinations is $$\binom {1+2}2$$ Hence total number of combinations is $$\binom {8}2-\binom 32 =28-3=25\qquad\blacksquare$$

$\endgroup$
6
  • $\begingroup$ Could you, perhaps, consider the code snippet I just gave in addition to my answer, and clarify why that does not produce the same figure as your answer? $\endgroup$ – String Oct 16 '15 at 18:47
  • $\begingroup$ Also, the opposite of $x_1<6$ should be $x_1\geq 6$, shouldn't it? $\endgroup$ – String Oct 16 '15 at 18:52
  • 2
    $\begingroup$ @hypergeometric: No, this is not right. Stars and bars the way you've done it permit the bars to be next to each other, or at the ends, in either case permitting one of the variables to be zero. At least the way the problem is stated, this is not permitted. You should have $(x_1-1)+(x_2-7)+(x_3-1) = 6$, and then the number of combinations, not restricting on $x_1$, is $\binom{6+2}{2} = 28$. Then, to identify the exclusion on $x_1$, eliminate the count from $(x_1-6)+(x_2-7)+(x_3-1) = 1$; this is $\binom{1+2}{1} = 3$. Therefore, the answer is $28-3 = 25$, as String (and I) obtained. $\endgroup$ – Brian Tung Oct 16 '15 at 19:06
  • $\begingroup$ @BrianTung: That makes sense! $\endgroup$ – String Oct 16 '15 at 20:47
  • $\begingroup$ Brian Tung is correct. You solved the problem in the nonnegative integers rather than the positive integers. $\endgroup$ – N. F. Taussig Oct 16 '15 at 22:00

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.