How many solutions does $x_1+x_2+x_3 = 11$ have if $0\le x_1 \le 3$, $0\le x_2 \le 4$, and $0\le x_3 \le 6$

combinatoricsdiscrete mathematicsinclusion-exclusion

How many solutions does $x_1+x_2+x_3 = 11$ have if $0\le x_1 \le 3$, $0\le x_2 \le 4$, and $0\le x_3 \le 6$?

I tried to do it with method 2 but there is a problem;

\begin{align*}
x_1+x_2+x_3 = 11\tag{1}\\ x_1\ge4, x_2\ge5, x_3\ge7
\end{align*}

then combining equation 1 and 2;
\begin{align*}
y_1 = x_1-4, y_2=x_2-5,y_3=x_3-7\tag{2}\\y_1+4+y_2+5+y_3+7 = 11\\y_1+y_2+y_3=-4\tag{3}
\end{align*}
how can I manage this problem in equation 3?

Best Answer

I'll edit these equations tomorrow if needed. I need to study a bit more to exam lol..

$S_0 = N = \binom{11+3-1}{3-1} = \binom{13}{2}=78\tag{0}$

Equation (0) is Total Number of Solutions

$N(C_1) = y_1+4+y_2+y_3 = 11 => y_1+y_2+y_3 = 7 => \binom{7 + 3 -1}{3-1} = \binom{9}{2} = 36 \tag{1}$

$N(C_2) = y_1+y_2+5+y_3 = 11 => y_1+y_2+y_3 = 6 => \binom{6 + 3 -1}{3-1} = \binom{8}{2} = 28 \tag{2}$

$N(C_3) = y_1+y_2+y_3+7 = 11 => y_1+y_2+y_3 = 4 => \binom{4 + 3 -1}{3-1} = \binom{6}{2} = 15 \tag{3}$

$S_1 = Equation(1)+Equation(2)+Equation(3) = 79$

Equation(1) is Total Number of Solutions with restriction $x_1\ge4$

$N(C_1C_2) = y_1+4+y_2+5+y_3 = 11 => y_1+y_2+y_3 = 2 => \binom{2 + 3 -1}{3-1} = \binom{4}{2} = 6 \tag{4}$

$N(C_1C_3) = y_1+4+y_2+y_3+7 = 11 => y_1+y_2+y_3 = 0 => \binom{0 + 3 -1}{3-1} = \binom{2}{2} = 1 \tag{5}$

$N(C_2C_3) = y_1+y_2+5+y_3+7 = 11 => y_1+y_2+y_3 = -1\tag{6}$

$S_2 = Equation(4)+Equation(5)+Equation(6) = 7$

Equation(4) is Total Number of Solutions with restriction $x_1\ge4 \cup x_2 \ge5$

At Equation(6) $y_1+y_2+y_3=-1$ means there is no solution for this spesific case.

So finally; $N(\overline C_1\overline C_2\overline C_3) = S_0-S_1+S_2 => 78-79+7 = 6$ total solutions with these restrictions.

I believe that is correct.

Related Solutions

[Math] How many nonnegative integer solutions are there to the pair of equations $x_1+x_2+…+x_6=20$ and $x_1+x_2+x_3=7$

You are correct. You can also think of it in terms of permutations.

The number of non-negative integer solutions of $x_1+x_2+x_3=7$ is the number of permutations of a multiset with seven $1$'s, and two $+$'s. This is $$\frac{9!}{7!\ 2!}.$$ Similarly, the number of non-negative integer solutions of $x_4+x_5+x_6=13$ is the number of permutations of thirteen $1$'s, and two $+$'s. This is $$\frac{15!}{13!\ 2!}.$$

This is why the first number in your combination is what the variables equal, and the second is "one less" the amount of variables, since you're permuting the $+$'s.

[Math] Find the number of integer solutions for $x_1+x_2+x_3 = 15$ under some constraints by IEP.

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?

Best Answer

Related Solutions

[Math] How many nonnegative integer solutions are there to the pair of equations $x_1+x_2+…+x_6=20$ and $x_1+x_2+x_3=7$

[Math] Find the number of integer solutions for $x_1+x_2+x_3 = 15$ under some constraints by IEP.

Related Question