# Finding all non-negative integers solutions to $x_1+x_2+x_3+…+x_6=20$ such that $x_{2n+1} \le x_{2n+2}$ for $0 \le n \le 2$

Solve $x_1+x_2+x_3+x_4+x_5+x_6=20$ such that $x_{2n+1}\leq x_{2n+2}, 0\leq n \leq2$

Edit : I solved it.

Let $0 \le a,b,c \le 20$ such that $0 \le a+b+c \le 20$

$x_1+x_2+x_3+x_4+x_5+x_6=20 \;and\ x_{2n+1}\leq x_{2n+2}\\ \implies x_2=x_1+a,\;x_4=x_3+b,\;x_6=x_5+c\\ \implies 2(x_1+x_2+x_3)+a+b+c=20\\ \implies 2(x_1+x_2+x_3)=20-a-b-c\;\;\;(1)$

So now we need for a fixed values of $a,b,c$ to find the number of non-negative integers solutions to the equation at $(1)$

Now, for all $0 \le i \le 20$

Let $A_i$ be the set of all non negative solutions for $a+b+c=i$

Let $X_i$ be the set of all non negative solutions for $2(x_1+x_2+x_3)=20-i$

Now,

$2(x_1+x_2+x_3)=20-i \implies (x_1+x_2+x_3)= \frac{20-i}{2}$

And since we are interesting in non-negative integers we can say that

$20-i\nmid 2 \implies X_i=\emptyset \implies |X_i|=0\;\;\;(2)$

Otherwise,

If $i$ is even we will want to compute

$\left|A_i\right|\cdot \left|X_i\right|$ because for any solution a+b+c=i in $A_i$ there's the corresponding solution in $X_i$

Therefore we have:

$\sum _{i=0}^{20}\:\left(\left|A_i\right|\cdot \left|X_i\right|\right)=\sum _{i=0}^{20}\:\begin{pmatrix}i+3-1\\ \:i\end{pmatrix}\begin{pmatrix}10-i+3-1\\ \:10-1\end{pmatrix}\\ \text{and from (2)}\\\sum _{i=0}^{20}\:\begin{pmatrix}i+3-1\\ \:i\end{pmatrix}\begin{pmatrix}10-i+3-1\\ \:10-1\end{pmatrix}= \sum \:_{i=0}^{10}\:\begin{pmatrix}2i+3-1\\ \:\:2i\end{pmatrix}\begin{pmatrix}10-i+3-1\\ \:\:10-i\end{pmatrix}=\\ \sum _{i=0}^{10}\:\left(\frac{\left(2i+2\right)\left(2i+1\right)}{2}\right)\left(\frac{\left(12-i\right)\left(11-i\right)}{2}\right)=9009$

And we've got a palindrome.

• The line with a factor of $2$ outside the parentheses is incorrect. You should have $2(x_1 + x_2 + x_3) + a + b + c = 20$. – N. F. Taussig Sep 20 '17 at 12:04
• Are we interested in solving the problem in the positive integers or the nonnegative integers? – N. F. Taussig Sep 20 '17 at 12:11
• Also, your title could be interpreted differently than the statement "Solve $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20$ such that $x_{2n + 1} \leq x_{2n + 2}, 0 \leq n \leq 2$." – N. F. Taussig Sep 20 '17 at 12:14
• Non-negative integers – idan di Sep 20 '17 at 13:26
• @N.F.Taussig thanks I fixed everything – idan di Sep 20 '17 at 14:20

I verified your solution a different way:

Let $N(i)$ denote the number of ways to have $x_{1}+x_{2}=i$ with $x_{1}\leq x_{2}$. It is easy to show that $N(i)=\lfloor\frac{i}{2}\rfloor+1$, for $0\leq i$.

Your problem now reduces to computing the following sum:

$\sum_{(k_{1},k_{2},k_{3})\in K}N(k_{1})\cdot N(k_{2})\cdot N(k_{3})$

where $K=\{(k_{1},k_{2},k_{3}):k_{1}+k_{2}+k_{3}=20,\ k_{i}\geq 0\}$, i.e. the set of ordered pairs of three non-negative integers summing to 20.

After a bit of sum-manipulating we get the equivalent sum:

$\sum_{k_{1}=0}^{20}N(k_{1})\sum_{k_{2}=0}^{20-k_{1}}N(k_{2})\cdot N(20-(k_{1}+k_{2}))$

Now throw elegance to the curb, enter the sum into Mathematica, and get 9009 $\checkmark$.

• You wrote that K_i greater then zero But why not to say that there's at least one K_i greater then zero ? Not All K_i must be greater then zero. If I understood – idan di Sep 20 '17 at 23:09
• @idandi That was my mistake, I meand $k_i \geq 0$. I edited the post to reflect the change. – mm8511 Sep 20 '17 at 23:13