Solution: 2015 Winter Final - 11
Author: Michiel SmidQuestion
How many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 99$, where $x_1 \geq 0$,
$x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$ are integers?
(a)
${102 \choose 4}$
(b)
${103 \choose 4}$
(c)
${102 \choose 3}$
(d)
${103 \choose 3}$
Solution
We can use the stars and bars method to solve this problem.
We have 3 dividers and 99 stars.
- $x_1$ is the number of stars to the left of the first divider
- $x_2$ is the number of stars between the first and second dividers
- $x_3$ is the number of stars between the second and third dividers
- $x_4$ is the number of stars to the right of the third divider
The number of solutions to the equation is $ \binom{99+3}{3} $