Combinatorics: How many non-negative integer solutions are there to each of the following equations: 
*

*$x_1 + x_2 + x_3 + x_4 + x_5 = 100$

*$x_1 + x_2 + x_3 + x_4 + x_5 \leq 100$

*$x_1 + x_2 + x_3 + x_4 + x_5 < 100$ with all $x_i > 0$


For the first one I said that the answer was $104C4$ and for the second one I said the answer was $105C5$. Are these two correct? If not, how do I do it? As for question 3, I have no idea how to do it. Any help would be appreciated. 
 A: The first two are correct, assuming you are counting things like $x_1 = 60, x_2 = 40$ as distinct from $x_1 = 40, x_2 = 60$.  The idea here is that you're spreading a certain number of balls into a certain number of bins.  The equation you used is usually derived via a stars and bars argument.
For part (a), you're basically distributing 100 balls into 5 bins, so the solution would be $104 \choose 4$.  For part (b), you can imagine having 6 bins instead;  the 100 balls are distributed between them, and the number of balls in the first five is then less than or equal to 100.  The answer is therefore $105 \choose 5$.
Since this looks like a homework problem, I won't give you the straight answer to part (c), but think of it this way:  if I handed you 100 balls and told you to put them into 5 bins such that there's at least one ball in each bin, what's the first thing you would do?  What would you do after that?
A: Your answers to the first two questions are correct.
For the third question, we reduce it to a problem you know how to solve.  Since each $x_k$, $1 \leq k \leq 5$, is a positive integer, the strict inequality
$$x_1 + x_2 + x_3 + x_4 + x_5 < 100$$ 
is equivalent to the weak inequality
$$x_1 + x_2 + x_3 + x_4 + x_5 \leq 99$$
If we make the substitution $y_k = x_k - 1$ for $1 \leq k \leq 5$, then each $y_k$ is a non-negative integer.  Substituting $y_k + 1$ for $x_k$, $1 \leq k \leq 5$, in the weak inequality yields
\begin{align*}
y_1 + 1 + y_2 + 1 + y_3 + 1 + y_4 + 1 + y_5 + 1 & \leq 99\\
y_1 + y_2 + y_3 + y_4 + y_5 & \leq 94
\end{align*}
which is an inequality in the non-negative integers, which you evidently know how to solve.
