How many solutions does the equation have? (Inclusion-exclusion principle)

Question

How many solutions does the equation $x_1+x_2+x_3+x_4=1$ have? $x_i$ are integers between $-3$ and $3$.

Hints please!

Answer 1

This answer will be easier to understand if you first read this.

First, you biject the problem to:

$x_1 + x_2 + x_3 + x_4 = 13$, where each $x_i \in \{0,1,2,3,4,5,6\}.$

Then, you use inclusion exclusion.

$T_k$ will represent the following computation:

• each of the $\binom{4}{k}$ possible combinations of $k$ of the variables will be examined.

• for each such combination, it will be assumed that the minimum value of the pertinent variables is $7$ rather than 0. That is, the $k$ variables will all be presumed to be out of bounds.

• the $4 - k$ remaining variables will be left unconstrained (i.e. minimum value = 0, they may or may not be out of bounds).

• the number of solutions possible for each such combination will be computed by bijecting the existing equation to one that adjusts for the pertinent variables being forced to be out of bounds.

• $T_k$ will represent the sum of the number of solutions possible for each of the $\binom{4}{k}$ combinations.

Consistent with Inclusion-Exclusion the answer will be
$T_0 - T_1 + T_2 - T_3 + \cdots - \cdots$

$T_0 = \binom{16}{3}.$

By symmetry
$T_1 = 4 \times$ the number of solutions where $x_1 \geq 7.$
Using the analysis in the cited article,
$T_1 = 4 \times \binom{9}{3}.$

At this point, the analysis stops, because it is impossible to have 2 or more constraints out of bounds and still have the sum be $\leq 13.$

Final answer:

$$\binom{16}{3} - [4 \times \binom{9}{3}].$$