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$ Oct 16, 2015 at 21:58

3 Answers 3

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, 2015 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, 2015 at 18:47
  • $\begingroup$ Also, the opposite of $x_1<6$ should be $x_1\geq 6$, shouldn't it? $\endgroup$
    – String
    Oct 16, 2015 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, 2015 at 19:06
  • $\begingroup$ @BrianTung: That makes sense! $\endgroup$
    – String
    Oct 16, 2015 at 20:47
  • $\begingroup$ Brian Tung is correct. You solved the problem in the nonnegative integers rather than the positive integers. $\endgroup$ Oct 16, 2015 at 22:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .