0

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

starsaber99
  • 17
  • 7
  • What's the constraint on $x_6$? – lulu Aug 08 '18 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 08 '18 at 11:40
  • https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) – Matti P. Aug 08 '18 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? – starsaber99 Aug 08 '18 at 11:49
  • Yes, I'd just go through the process twice. – lulu Aug 08 '18 at 11:55
  • I tried to go through it but am unfortunately still a little confused, do you mind just writing out part of the solution for me so I know if I'm going in the right direction? – starsaber99 Aug 08 '18 at 12:37
  • You are probably looking only for basic solutions. Otherwise the answer is: ∞. – Erwin Kalvelagen Aug 08 '18 at 14:23
  • @starsaber99 Usually integer programming requires that $x_i\in \mathbb N_0$. But this constraint is missing in your model. – callculus42 Aug 08 '18 at 14:58

1 Answers1

0

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.$

callculus42
  • 30,550