# Linear and Integer Programming

How many different solutions are there to the equation

$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=16$

with the following constraints:

$x_{1}\geq 1$

$x_{2}\geq 2$

$x_{3}\geq 0$

$x_{4}\geq 3$

$x_{5}\geq 2$

$0\leq x_{6}\leq 1$

So far, how I've been approaching the question is: Let $y_{1}=x_{1}-1$, $y_{2}=x_{2}-2$, $y_{3}=x_{3}$, $y_{4}=x_{4}-3$, $y_{5}=x_{5}-2$. And then substitute the equations in for x to express the equation in terms of y. However, I do not how to format $x_{6}$, and I'm not quite sure the logic behind this solution

• What's the constraint on $x_6$?
– lulu
Aug 8, 2018 at 11:39
• Assuming you meant $x_6\in \{0,1\}$ then I'd just solve the two problems separately (that is, fix $x_6=0$ and solve, then fix $x_6=1$ and solve).
– lulu
Aug 8, 2018 at 11:40
• en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) Aug 8, 2018 at 11:43
• Whoops sorry! I changed it and yes you're right! So wait, would you set it as two separate equations? How do you account for that when subbing in the equations? would I go through the process twice? Aug 8, 2018 at 11:49
• Yes, I'd just go through the process twice.
– lulu
Aug 8, 2018 at 11:55

You can use the generating function to solve the problem. First of all we use your transformation of the variables.

$y_1+1+y_2+2+y_3+y_4+3+y_5+2+x_6=16$

I do not replace the $x_6$. We can solve the two cases $x_6=0$ and $x_6=1$ separately as suggested from lulu. If $x_6=0$ we have

$y_1+1+y_2+2+y_3+y_4+3+y_5+2=16$

$y_1+y_2+y_3+y_4+y_5+8=16$

$y_1+y_2+y_3+y_4+y_5=8$

Then we are looking for the coefficient of $y^8$ at $(1+y+y^2+y^3+...)^5=\frac{1}{(1-y)^5}$. This is equal to

$$\sum_{k=0}^{\infty} \binom{k+4}{k} \cdot y^k$$

Therefore in case $x_6=0$ we have $\binom{8+4}{8}=\binom{8+4}{4}=495$ different solutions. Similar procedure for the case $x_6=1.$