Number of integer solutions to a strict inequality

195 Views Asked by At

$$x_1+x_2+x_3+x_4+x_5+x_6<538|x_i>0$$ The inequality is strict. Apparently, there are $\binom{537}{6}$ solutions to this after adding a new variable, $x_7$, that serves as a balance. Could someone walk me through this step-by-step? I realize that, if the inequality is strict, then $x_7 > 0$. I'm confused about the logic of counting the number of integer solutions.

1

There are 1 best solutions below

5
On

Imagine 538 placeholder spaces to put an object. First add a balance variable $x_7$ to make an equality. $$x_1+x_2+x_3+x_4+x_5+x_6+x_7=538|x_7>0$$ The restriction on this variable is that $x_7>0$ for the equality and original strict inequality to hold true. Now distribute 1 object each to variables ${x_1...x_7}$ due to the restriction that $x_i>0$. This leaves 531 objects to distribute among 7 variables. There are 6 dividers to partition the set into 7 parts, which means there are $531+6=537$ placeholders for either a divider or an object. The answer is therefore $537\choose{6}$.