Let's say I'm using stars-and-bars to count the number of nonnegative integer solutions to$$x_1 + x_2 + x_3 = 3n.$$Clearly, it's going to be $\binom{3n + 2}{2}$. And now let's say we want to count the number of positive integer solutions to the same equation. I'm able to calculate without stars and bars by subtracting from $\binom{3n + 2}{2}$ (1) the number of solutions where one $x_i$ is zero, and (2) the number of solutions where two $x_i$ are zero. We have$$\binom{3n+2}{2} – 3(3n-1) – 3 = \binom{3n-1}{2},$$which is the correct answer. However, when I try to apply stars-and-bars to the solving for the number of positive integer solutions of the equation$$x_1 + x_2 + x_3 = 3n,$$I add $3$ to both sides to account for the fact that each of the three $x_i$ has to now be greater than or equal to $1$ and not $0$, and so I end up getting $\binom{3n + 5}{2}$, which is clearly wrong.
I don't understand why I would have to subtract $3$ from both sides of$$x_1 + x_2 + x_3 = 3n$$to perform stars-and-bars for the positive integer solutions case instead of adding $3$, in order to get the correct answer of $\binom{3n-1}{2}$. Any help would be well-appreciated.
Best Answer
If you want to find the number of positive solutions to $$x_1 + x_2 + x_3 = 3n$$ then you could restate this by letting $y_i=x_i-1$ and finding the number of non-negative solutions to $$(y_1+1) + (y_2+1) + (y_3+1) = 3n$$
But, subtracting $3$ from each side, this is the number of non-negative solutions to $$y_1 + y_2 + y_3 = 3n-3$$ which you already know is $${3n-3+2 \choose 2} = {3n-1 \choose 2}$$