Question:
Compute how many different integer solutions the following inequality has:
$$ x_1 + x_2 + x_3 + x_4 < 50 $$
when we require that $-1 \leq x_1, -2 \leq x_2 \leq 2, -3 < x_3, -4 < x_4 < 4.$
My approach:
So I will start by making the inequality to equality.
$$ x_1 + x_2 + x_3 + x_4 < 50 $$
$$ x_0 + x_1 + x_2 + x_3 + x_4 = 49 $$
$$x_0 \geq 0 $$
Then I would change $x_i$ for $y_i$:
$$y_1 – 1 = x_1$$
$$y_2 – 2 = x_2$$
$$y_3 – 2 = x_3$$
$$y_4 – 3 = x_4$$
So that would be:
$$y_0 + y_1 – 1 + y_2 – 2 + y_3 – 2 + y_4 – 3 = 49 $$
$$y_0 + y_1 + y_2 + y_3 + y_4 = 57 $$
Since I have bounds on $x_2$ and $x_4$, I need to make condition for them:
$$-2 \leq x_2 \leq 2$$
$$0 \leq x_2 \leq 4$$
$$x_2 \geq 5$$
$$and$$
$$-4 < x_4 < 4$$
$$0 < x_4 < 8$$
$$x_4 > 8$$
And finally to count it:
$$\binom{57+5-1}{5-1}…$$
But I don't know how to get the final number (including those conditions). Is it possible to do it with inclusion–exclusion principle ?
Any help on what to do would be appreciated.
Best Answer
You're on the right track.
Hint We're aiming to solve the inequality $$\phantom{(\ast)} \qquad y_1 + y_2 + y_3 + y_4 \leq N,$$ or just as well the equality $$\phantom{(\ast)} \qquad y_0 + y_1 + y_2 + y_3 + y_4 = N , \qquad (\ast)$$ in nonnegative integers.
As you suggest, we can use the Inclusion-Exclusion Principle: Let $S$ denote the set of solutions $(y_0, \ldots, y_4)$ of $(\ast)$, $S_2 \subset S$ the set of solutions satisfying $y_2 \geq a$, and $S_4 \subset S$ the set of solutions satisfying $y_4 \geq b$, so that our aim is to compute $|S| - |S_2 \cup S_4| = |S| - |S_2| - |S_4| + |S_2 \cap S_4|$.
The number of solutions of $(\ast)$ is $$|S| = {{N + 4} \choose 4}$$ (see this question for a derivation and OEIS 000332 for the sequence).
We now consider the number of solutions of $(\ast)$ in $S_2$, that is, that satisfy $y_2 \geq a$ (in particular not imposing the condition on $y_4$). If we set $\color{#ff0000}{z_2} := y_2 - a$, then we are just as well looking for the number of solutions in nonnegative integers to $$y_0 + y_1 + \color{#ff0000}{z_2} + y_3 + y_4 = N - a ,$$ which we know from the computation of $|S|$ is $$|S_2| = {{N - a + 4} \choose 4} .$$