How many solutions does the equation $x_1 + x_2 + x_3 = 11$ have, where $x_1, x_2, x_3$ are nonnegative integers?

Perhaps this will help. We have $11$ identical candies, that we wish to distribute between $3$ children $C_1$. $C_2$, and $C_3$. (Possibly one or more of the children will get no candies.) For every solution of $x_1+x_2+x_3=11$, we have a way of distributing the candies, $x_1$ to $C_1$, $x_2$ to $C_2$, and $X_3$ to $C_3$. conversely, every distribution of candies gives us a solution of $x_1+x_2+x_3=11$.

It is a little easier to do count a closely related problem: we will distribute $11+3=14$ candies to the children, at least one candy to each. Then we will take away a candy from each child. Line up the candies like this: $$\times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times.$$ There are $13$ inter-candy gaps. Choose $2$ of these gaps to put a separator into, maybe like this. $$\times\quad \times\quad \times\quad \times\quad |\times\quad \times\quad| \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times\quad \times.$$ Give all the candies up to the first separator to $C_1$, the candies between the two separators to $C_2$, and the rest to $C_3$. So the pattern above has $C_1$ getting $4$, $C_2$ getting $2$, and $C_3$ getting $8$. when the one candy is taken away, this corresponds to the solution $x_1=3$, $x_2=1$, $x_3=7$.

There are just as many ways to insert the two separators as there are solutions of our equation. Thus the number of solutions is $\binom{13}{2}$.

Since $\binom{n}{r}=\binom{n}{n-r}$, the answer can be alternately be rewritten as $\binom{13}{11}$.


This is the classic stars-and-bars problem, and in this case, it appears in the guise of finding non-negative integer solutions to the equation $$x_1 + x_2 + x_3 = 11$$

There are $$\binom{n + r - 1}{n} = \binom{n + r - 1}{r-1}$$ solutions.

If we put $n = 11$, and $r = 3$ (where $r$ is the number of $x_i$ terms in the sum), then in this case, that, we compute either $$\binom{11 + 3 - 1}{11} =\;\;\text{or}\;\;= \binom{11 + 3 - 1}{2}$$

For more practice with problems such as this, and some variations: see the search results at Math.SE for "stars-and-bars".