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