1
$\begingroup$

I am trying to solve the following question. I have worked through a similar question but the question I have worked through the range was all positive, however this one has a negative side of the range so I am not quite sure how to solve it. I will include the question I have worked through as reference below. Here is the question I need help solving, thanks! I need to solve it through the principle of inclusion exclusion

How many integer solutions of $x_1+x_2+x_3+x_4=28$ are there with $-10 \leq x_i \leq 20$

Here is the similar problem I mentioned above,

How many integer solutions for the equation $x_1+x_2+x_3+x_4=28$ are there with $0 \leq x_i \leq 10$

For this solution I used the negation $N(a_1',a_2'a_3'a_4') = N -N(a_i)+N(a_i,a_j)-...$

I let $N=$ all possible solutions. I said it was like distrubting 28 balls in 4 bins so, $\binom{28+4=1}{28}$

the next would term would happen after I use $11$ balls, one more than the range of the question as listed above which is $10$, so we have $\binom{17+4-1}{17}$ and there are $\binom{4}{1}$ also, so $\binom{17+4-1}{17} \binom{4}{1}$

next after using 11 more balls we would have $\binom{6+4-1}{6}$ with $\binom{4}{2}$ so putting together we have $\binom{6+4-1}{6} \binom{4}{2}$

the term in the sequence is not possible since $6-11$ makes us run out of balls

so then the solution is, $\binom{28+4=1}{28} - \binom{17+4-1}{17} \binom{4}{1} + \binom{6+4-1}{6} \binom{4}{2}$

So then how can I use that similar process to solve my question

$\endgroup$
  • 1
    $\begingroup$ Perhaps it helps to add $10$ to each $x_i$ and then to require the sum to be $68$? This is a partitioning question. $\endgroup$ – user334732 Mar 23 '18 at 10:51
  • $\begingroup$ how would I do that? $\endgroup$ – jh123 Mar 23 '18 at 10:52
  • $\begingroup$ Well just change the rules. $0\leq x_i\leq 30$ and $x_1+x_2+x_3+x_4=68$. The problem remains unchanged but is perhaps a little simpler to think about. $\endgroup$ – user334732 Mar 23 '18 at 10:53
  • $\begingroup$ okay and that would the correct answer then using my steps I have shown above? $\endgroup$ – jh123 Mar 23 '18 at 10:54
  • $\begingroup$ tricky to answer that because I think about it differently. I see this as: How many ways are there to partition the number $68$ into four different parts all between $0$ and $30$ inclusive? The theory is here: restricted partitions. en.wikipedia.org/wiki/… $\endgroup$ – user334732 Mar 23 '18 at 11:02
1
$\begingroup$

How many integers solutions of $$x_1 + x_2 + x_3 + x_4 = 28$$ are there that satisfy $-10 \leq x_k \leq 20$ for $1 \leq k \leq 4$?

We can convert this to an equivalent problem in the nonnegative integers.
$$x_1 + x_2 + x_3 + x_4 = 28 \tag{1}$$ Let $y_k = x_k + 10$, where $1 \leq k \leq 4$. Then each $y_k$ is a nonnegative integer satisfying $0 \leq k \leq 30$. Substituting $y_k - 10$ for $x_k$, $1 \leq k \leq 4$, in equation 1 yields \begin{align*} y_1 - 10 + y_2 - 10 + y_3 - 10 + y_4 - 10 & = 28\\ y_1 + y_2 + y_3 + y_4 & = 68 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers. A particular solution of equation 2 corresponds to the placement of $3$ addition signs in a row of $68$ ones. The number of solutions of equation 1 is $$\binom{68 + 3}{3} = \binom{71}{3}$$ since we must choose which $3$ of the $71$ positions required for $68$ ones and $3$ addition signs will be filled with addition signs.

From these, we must subtract those cases that violate one or more of the restrictions that $y_k \leq 30$, $1 \leq k \leq 4$. Notice that at most two of these restrictions can be violated simultaneously since $3 \cdot 31 = 93 > 68$.

Suppose $y_1 > 30$. Then $y_1' = y_1 - 31$ is a nonnegative integer. Substituting $y_1' + 31$ for $y_1$ in equation 2 yields \begin{align*} y_1' + 31 + y_2 + y_3 + y_4 & = 68\\ y_1' + y_2 + y_3 + y_4 & = 37 \tag{3} \end{align*} Equation 3 is an equation in the nonnegative integers with $$\binom{37 + 3}{3} = \binom{40}{3}$$ solutions. By symmetry, there are an equal number of solutions for each of the four variables that could violate the restriction $y_k \leq 30$. Hence, there are $$\binom{4}{1}\binom{40}{3}$$ cases in which one of the restrictions is violated.

However, if we subtract this number from the total, we will have subtracted too much since we will have subtracted each case in which two of the variables violate the restrictions twice, once for each variable we designated as the variable that violated the restriction. We only want to subtract those cases once, so we must add them back.

Suppose $y_1, y_2 > 30$. Let $y_1' = y_1 - 31$; let $y_2 = y_2 - 31$. Then $y_1'$ and $y_2'$ are nonnegative integers. Substituting $y_1' + 31$ for $y_1$ and $y_2' + 31$ for $y_2$ in equation 2 yields \begin{align*} y_1' + 31 + y_2' + 32 + y_3 + y_4 & = 68\\ y_1' + y_2' + y_3 + y_4 & = 6 \tag{4} \end{align*}
Equation 4 is an equation in the nonnegative integers with $$\binom{6 + 3}{3} = \binom{9}{3}$$ solutions. By symmetry, there are an equal number of solutions for each of the $\binom{4}{2}$ pairs of variables that could violate the restrictions. Hence, there are $$\binom{4}{2}\binom{9}{3}$$ cases in which two of the variables violate the restrictions.

Thus, by the Inclusion-Exclusion Principle, the number of solutions that satisfy the restrictions is $$\binom{71}{3} - \binom{4}{1}\binom{40}{3} + \binom{4}{2}\binom{9}{3}$$

$\endgroup$
  • $\begingroup$ this seems to be different from the solution you said was correct yesterday? $\endgroup$ – jh123 Mar 24 '18 at 13:51
  • $\begingroup$ Keep in mind that $\binom{n}{k} = \binom{n}{n - k}$. Hence, we could also express the answer in the form $\binom{71}{68} - \binom{4}{1}\binom{40}{37} + \binom{4}{2}\binom{9}{6}$, as you did yesterday. $\endgroup$ – N. F. Taussig Mar 24 '18 at 13:54
  • $\begingroup$ yes i plugged them into wolfram and that was true, so both solutions are correct $\endgroup$ – jh123 Mar 24 '18 at 13:58
  • 1
    $\begingroup$ your answer is very detailed, thanks! $\endgroup$ – jh123 Mar 24 '18 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.