0
$\begingroup$

So, I'm now familiar with the stars and bars method, but something struck my mind.

To calculate non-negative integer solutions to $x_1+x_2+x_3+\cdots+x_n = k$ we use the Stars and Bars method. However, what if we have an inequality: $\boxed{x_1+x_2+x_3+\cdots+x_n < k}$.

I searched for information and found that you could use a new slack variable $$x_{n+1} = k-(x_1+x_2+x_3+\cdots+x_n)$$ And therefore you would have the equivalent equation: $$x_1+x_2+x_3+\cdots+x_n+x_{n+1} = k$$

This would then be solved by the usual Stars and Bars method. But I'm puzzled by the slack variables effect in the Stars and Bars method.

If one introduces a new variable, and initializes its value to be reliant on the other $x$'s, won't that destroy the whole concept in Stars and Bars method where you can freely choose where each bar & star gets placed? And what about the solution $x_1+x_2+x_3+\cdots+x_n = 39, 38, 37$ etc...

And as a bonus question, if anyone care enough to add on what happens when you have an expression $$x_1+x_2+x_3+\cdots+x_n > k, \quad (\text{greater than }k)$$

Edit 1:

Example

Given $x_1+x_2+x_3 < 10$, I would add the slack variable $x_4 = 10-(x_1+x_2+x_3)$

This gives the equation $x_1+x_2+x_3+x_4 = 10$

And the non-negative integer solutions are solved as: $\binom{10+4-1}{4-1} = \binom{14}{3} = 364$

Edit 2:

I need to make sure $x_{n+1} \ge 0$

Given $x_1+x_2+x_3 < 10$, I would first rewrite it as $x_1+x_2+x_3 \le 9$

I would add the slack variable $x_4 = 9-(x_1+x_2+x_3)$

This gives the equation $x_1+x_2+x_3+x_4 = 9$

And the non-negative integer solutions are solved as: $\binom{9+4-1}{4-1} = \binom{12}{3} = 220$

$\endgroup$
  • $\begingroup$ Adding the slack variable just gives you an extra bar, so S&B will still work fine (but you first need to make an adjustment to take care of the fact that $x_{n+1}\ge1$). The last inequality will have infinitely many solutions. $\endgroup$ – user84413 Sep 29 '14 at 23:35
  • $\begingroup$ Hmm, care to elaborate on the adjustment part? If I give you an example in the bodytext (edit 1). Did I do that the right way? Edit: I see why I need to make the adjustment. The expression is $expr < k$ not $expr \le k$. Sorry about that, no need to explain, I guess. $\endgroup$ – B. Lee Sep 29 '14 at 23:42
1
$\begingroup$

Even when you freely choose the $\star$'s and $|$'s for choosing a solution to $x_1+\dots +x_n=k$, one of the variable choices is still forced. For example, when finding a $\star$'s and $|$'s string to represent a solution to $x_1+x_2+x_3=5$, I start out with $5+3-1=7$ empty spaces, to be filled with $5 \star$'s and $3-1=2$ bars. $$ \_\,\_\,\_\,\_\,\_\,\_\,\_\, $$ If I wanted to make $x_1=3$, I could start with three $\star$'s, followed by a bar: $$ \star\star\star|\,\_\,\_\,\_\, $$ And to make $x_2=1$, I could follow this by one $\star$ and a bar: $$ \star\star\star|\,\star |\,\_\, $$ But now, there is only one valid way to finish the string, since you only are allowed to distribute $3-1=2$ bars. So even though you can freely place the bars, you can't freely choose the variables.

For the bonus, there are infinitely many solutions to that inequality, so it falls outside the realm of combinatorics.

$\endgroup$

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.