Problem:
$x_1+x_2+x_3+x_4 = 22$. How many solutions are there if the $x_i$s are nonnegative integers and $1<x_1<7$, $3\leq x_2 \leq 5$, $x_3 \leq 7$, $1<x_4\leq 13$?
My work:
$y_1+y_2+y_3+y_4 = 15$
$y_1<5, y_2<3, y_3<8, y_4<12$
$x_1 = y_1+2, x_2=y_2+3, x_3=y_3,x_4=y_4+2$
Ignoring upper-bounds we have $C(15+4-1,15)=816$
Solutions when
$y_1 \geq 5, y_2\geq 0, y_3\geq 0, y_4 \geq 0$
$(y_1-5) + y_2 + y_3 + y_4 = 10$
$C(10+4-1,10) = 286$
Solutions when
$y_1 \geq 0, y_2 \geq 3, y_3 \geq 0, y_4 \geq 0$
$y_1 + y_2-3 + y_3 + y_4 = 12$
$C(12+4-1,12) = 455$
Solutions when $y_1 \geq 0, y_2 \geq 0, y_3 \geq 8,y_4 \geq 0$
$y_1 + y_2 + y_3-8 + y_4 = 7$
$C(7+4-1,7) = 120$
Solutions when $y_1 \geq 0, y_2 \geq 0, y_3 \geq 0, y_4 \geq 12$
$y_1 + y_2 + y_3 + y_4-12 = 3$
$C(3+4-1,3) = 20$
$816-286-455-120-20 = -65$
So I started some of the steps above. I am wondering if I am doing this correctly as well as what the next step is on how to calculate what I am under-counting because $-65$ is obviously not he answer.
Best Answer
You have correctly reduced the problem to finding the number of solutions of the equation $$y_1 + y_2 + y_3 + y_4 = 15 \tag{1}$$ subject to the restrictions $y_1 < 5, y_2 < 3, y_3 < 8, y_4 < 12$.
Let $A_1$ denote the set of outcomes in which $y_1 \geq 5$, $A_2$ denote the set of outcomes in which $y_2 \geq 3$, $A_3$ denote the set of outcomes in which $y_3 \geq 8$, and $A_4$ denote the set of outcomes in which $y_4 \geq 12$. By the Inclusion-Exclusion Principle, the number of outcomes in which none of the restrictions is violated is found by subtracting the number of solutions in which at least one of these restrictions is violated from the number of solutions of equation 1.
You correctly found that the number of solutions of equation 1 is $$\binom{15 + 4 - 1}{4 - 1} = \binom{18}{3} = \binom{18}{15}$$ and that \begin{align*} |A_1| & = \binom{10 + 4 - 1}{4 - 1} = \binom{13}{3} = \binom{13}{10}\\ |A_2| & = \binom{12 + 4 - 1}{4 - 1} = \binom{15}{3} = \binom{15}{12}\\ |A_3| & = \binom{7 + 4 - 1}{4 - 1} = \binom{10}{3} = \binom{10}{7}\\ |A_4| & = \binom{3 + 4 - 1}{4 - 1} = \binom{6}{3} \end{align*} The reason you obtained a negative answer is that you have subtracted each case in which two restrictions are violated twice, once for each way you designated one of the restrictions as the restriction that is being violated. We only want to subtract such cases once, so we must add them to the total. In fact, by the Inclusion-Exclusion Principle, the number of solutions in which at least one condition is violated is \begin{align*} & |A_1 \cup A_2 \cup A_3 \cup A_4|\\ & \quad = |A_1| + |A_2| + |A_3| + |A_4|\\ & \qquad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_1 \cap A_4| - |A_2 \cap A_3| - |A_2 \cap A_4| - |A_3 \cap A_4|\\ & \quad \qquad + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|\\ & \qquad \qquad - |A_1 \cap A_2 \cap A_3 \cap A_4| \end{align*}
Notice that many of these terms are equal to zero. For instance, it is not possible for $y_1 \geq 5$ and $y_2 \geq 12$ since $5 + 12 > 15$.
Let's calculate $|A_1 \cap A_2|$. I will leave the calculations of the remaining terms to you.
$|A_1 \cap A_2|$: Then $y_1 \geq 5$ and $y_2 \geq 3$. Let $y_1' = y_1 - 5$ and $y_2' = y_2 - 3$. Then $y_1'$ and $y_2'$ are nonnegative integers. Substituting $y_1' + 4$ for $y_1$ and $y_2' + 3$ for $y_2$ in equation 1 yields \begin{align*} y_1' + 5 + y_2' + 3 + y_3 + y_4 & = 15\\ y_1' + y_2' + y_3 + y_4 & = 7 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with
$$\binom{7 + 4 - 1}{4 - 1} = \binom{10}{3} = \binom{10}{7}$$
solutions.