# Count the integer solutions of $x_1+x_2-x_3+x_4-x_5=3$

I am asking for help with solving this exercise:

Find the count of possible integer solutions for equation:

$$x_1+x_2-x_3+x_4-x_5=3$$

There are restrictions for possible values of $x$:

\begin{aligned} &0 < x_1 \le 6\\ -&8 \le x_2 < -2\\ &x_3 \le 1\\ &3 < x_4\\ &2 \le x_5 \le 8 \end{aligned}

Note: We should be able to find the count of solutions by using permutations and Inclusion-Exclusion principle.

• what kind of numbers are you searching for? integers? – Dr. Sonnhard Graubner Jan 6 '18 at 12:37
• Yes, I am looking only for count of integer solutions – zdarsky.peter Jan 6 '18 at 12:38
• there are a lot of solutions – Dr. Sonnhard Graubner Jan 6 '18 at 12:43
• how can i send them to you? – Dr. Sonnhard Graubner Jan 6 '18 at 12:44
• For reference, the answer I found using computer is $2016$ – samjoe Jan 6 '18 at 13:33

As a simplification, transform$^\star$ $x_i$ to $y_i$ so that all variables are atleast positive.

$$y_1 + y_2 + y_3+y_4+y_5 = 15\\ y_1 \in [0,5]\\ y_2 \in [0,5] \\ y_3 \in [0,\infty] \\ y_4 \in [0, \infty] \\ y_5 \in [0,6]$$

Now the bounds in place, it is simple to use inclusion exclusion principle.

\begin{align} N &= N_{y_i \in [0, \infty)} \\ &- (N_{y_1 > 5} + N_{y_2 > 5} +N_{y_5 > 6}) \\ &+(N_{y_1 > 5 \land y_2 > 5} + N_{y_2 > 5 \land y_5 > 6}+N_{y_1 > 5 \land y_5 > 6}) \\ &- (N_{y_1 > 5 \land y_2 > 5 \land y_5 > 6}) \end{align}

Now the rest is pretty straight forward using the classic stars and bars:

$$\binom{19}{4} - \left(\binom{13}{4} +\binom{13}{4} +\binom{12}{4} \right)+\left(\binom{7}{4} +\binom{6}{4} +\binom{6}{4} \right)-0 = \boxed{\color{maroon} {2016}}$$

Edit

$^\star$In this edit I try to explain how we can transform the $x_i$ to $y_i$

1. We start with $x_1 \in [1,6]$, so $x_1 - 1 \in [0,5]$

2. Now $x_2 \in [-8,-2)$ or $x_2+8 \in [0,5]$

3. $x_3 \in (-\infty, 1]$ or $-x_3 \in [-1, \infty)$ and $-x_3+1 \in [0, \infty)$

4. And then $x_4 \in [4, \infty)$ so $x_4-4 \in [0, \infty)$.

5. Lastly $x_5 \in [2,8]$ or $-x_5 \in [-8,-2]$ and $-x_5 + 8 \in [0,6]$

Now sum all the inequalities in the end of each numbered point. Call each expression in variable as new variable $y_i$. Required equation is:

$$(x_1 - 1) + (x_2+8) + (-x_3+1) + (x_4-4) + (-x_5+8 ) = 3 + (-1+8+1-4+8) \\ y_1 + y_2 + y_3 + y_4 + y_5 = 15$$

• @Abcd Thanks mate I was going to link this problem to you! – samjoe Jan 6 '18 at 18:11
• Can you tell me how you got $\dbinom{13}{4}$ for $y_1>5$? – Archer Jan 6 '18 at 18:57
• @Abcd In that case we have $y_1 \in [6, \infty)$ so $y_1 - 6 \in [0,\infty)$, so that $(y_1 - 6) + y_2 + y_3 + y_4 + y_5 = 15-6 = 9$. Answer is from stars and bars, since all terms are non negative $\binom{9+5-1}{5-1}$ – samjoe Jan 6 '18 at 19:02
• @samjoe Your math works, thank you so much! – zdarsky.peter Jan 6 '18 at 21:22

Hint: $-9\le a=x_1+x_2-x_5\le-5$; $b=-x_3+x_4\ge3$. Now you have 5 pairs of solutions $(-9,12),(-8,11),(-7,10),(-6,9),(-5,8)$. Let's start with $(-9,12)$.
$a=-9$ only when $x_1=1, \: x_2=-8, \: x_3=2$. Now $b=12$ when $x_3=-8, x_4=4$; $x_3=-7, x_4=5$; ..., $x_3=1, x_4=11$. That's 10 solutions. Can you finish?

• I think your boundaries are different then from @Manish Kundu – zdarsky.peter Jan 6 '18 at 13:21
• no, since $2+n\le 1$ and $4+n>3$, so $-1 <n\le -1$ – Exodd Jan 6 '18 at 14:28

I need help with solution too. On the picture is my try.

• Welcome to MSE. Please type your questions (using MathJax) instead of posting links to pictures. – José Carlos Santos Jan 6 '18 at 13:27
• It is kinda the way how I wanted to be solved, but I think that answer is not correct. – zdarsky.peter Jan 6 '18 at 13:41

By translations $x\to x+c$ and symmetries $x\to-x$ you can reformulate your problem as

Find all $x_1,x_2,x_3,x_4,x_5$ integers that satisfy $$1+x_3+x_4 = x_1+x_2+x_5$$ with bounds $$0\le x_1\le 5\qquad 0\le x_2\le 5\qquad 0\le x_5\le 6$$ $$0\le x_3\qquad 0\le x_4$$

Now, call $p(n)$ the number of triples $(x_1,x_2,x_5)$ such that $x_1+x_2+x_5=n$ and such that $$0\le x_1\le 5\qquad 0\le x_2\le 5\qquad 0\le x_5\le 6$$ hold. In the same way, let $q(n)$ the number of couples $(x_3,x_4)$ such that $x_3+x_4=n$ and such that $$0\le x_3\qquad 0\le x_4$$ hold. Your solution is $$p(1)q(0) + p(2)q(1) + p(3)q(2) + \dots + p(16)q(15).$$ We know that $q(n)=n+1$, but $p(n)$ is much harder to compute, and I think must be done by a computer.

Let's do it with permutations/inclusion-exclusion.

First of all, a Toy Problem

Find all $x_1,x_2,x_3,x_4,x_5$ positive integers that satisfy $$c+x_3+x_4 = x_1+x_2+x_5$$ where $c$ is an integer (may be negative) and with bound $$c + x_3+x_4\le n$$ where $n$ is a positive integer.

Like before, let $p(m)$ the number of triples $(x_1,x_2,x_5)$ such that $x_1+x_2+x_5=m$ and let $q(m)$ the number of couples $(x_3,x_4)$ such that $x_3+x_4=m$. We know that $$p(m) = \frac{(m+2)(m+1)}2 = \binom{m+2}2 \qquad q(m) = m+1 = \binom{m+1}1$$ The solution is $$TP(c,n) = q(-c)p(0) + q(1-c)p(1) + \dots +q(n-c)p(n)$$ $$= \binom {1-c}1\binom 22 + \binom {2-c}1\binom 32 + \dots + \binom {n-c+1}1\binom {n+2}2$$

If we return to our first problem, we can operate an inclusion-exclusion method.

• First of all, we notice that $x_1+x_2+x_5\le 16$, so we can consider the Toy Problem with $c=1$ and $n=16$, so we get $TP(1,16)$.
• We have to respect the bounds, though, so we have to subtract the wrong solutions. How many solution are there with $x_5>6$? If we substitute $x_5 = 7 +z_5$ we get again the Toy Problem with $$-6+x_3 + x_4 = x_1+x_2+z_5$$ so $c=-6$ and $n=16 -7=9$, so $TP(-6,9)$. If we do the same for $x_1,x_2$ we get $TP(-5,10)$ twice.
• Now we subtracted too much. For example we subtracted twice the (wrong) solutions with $x_1>5,x_2>5$ and we have to add them again. With the same substitutions as before, we get $TP(-11,4)$. Doing the same for the other couples, we get $TP(-12,3)$ twice.

The final answer is thus $$TP(1,16) - TP(-6,9) - 2\cdot TP(-5,10) + TP(-11,4) + 2\cdot TP(-12,3)$$

• We should be able to find the count of solutions by using permutations and Inclusion–exclusion principle – zdarsky.peter Jan 6 '18 at 13:33
• Ok, now I'll write it. Warning: it'll be long – Exodd Jan 6 '18 at 13:49

Note that the problem reduces to counting the solutions of $x_4-x_3=\alpha=3+a$, where $a=-x_1-x_2+x_5$. Now note that $a$ ranges between $-1$ and $15$, so that $\alpha$ takes on values between $2$ and $18$ respectively, which gives us $17$ different values for $\alpha$. With the constraints $x_4\ge4$ and $x_3\le1$ and the equation $x_4-x_3=\alpha$, it is possible to note that the number of solutions is finite.

• False: $x_4 = 3+ x_5+x_3 -x_1-x_2 \le 3+8+1-0+8=20$ – Exodd Jan 6 '18 at 12:59
• Oh, yes. One has to consider $x_3$ too. – Allawonder Jan 6 '18 at 13:00
• There is no infinite solutions, $x_4$ is bounded below but $x_3$ is positive at some point. – Abr001am Jan 6 '18 at 13:10
• Still false: $x+y=\alpha$ has finite solutions when, for example, $x\ge 0$ and $y\ge 0$. – Exodd Jan 6 '18 at 13:11
• There are actually infinitely many solutions. See new edition. – Allawonder Jan 6 '18 at 14:02