# Slack variable and counting integer solutions

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$

• 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. – user84413 Sep 29 '14 at 23:35
• 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. – B. Lee Sep 29 '14 at 23:42

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.