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

Question

Help me understand problems of this type a bit more intuitively.

The solution $C(3+11−1,11)$ seems simple enough, but I got stuck thinking about how many integers you are choosing from within $x_1$, $x_2$, and $x_3$ and I was trying to get an $n$ - as in $C(n+r-1,r)$ - this way. Also, I though the $r$ was 3 since you have $x_1$, $x_2$, $x_3$ choices. Basically, I went wrong at every step. Help!

Answer 1

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}$.

Answer 2

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".

Answer 3

Note that $C(3 + 11 - 1, 11) = C(3 + 11 - 1, 2)$, then figure that once you choose two parts, the third is already decided.

For a full answer, picture 13 dots in a row. If you choose two of them, you've cut up the space into 3 parts. The ugly part is when two are next two each other, but you can think of that as: if two choices are adjacent, they are the same choice. So if you choose the first dot, that's really choosing 0 for $x_1$. You should be able to fill in the details from there.

Answer 4

You are thinking of the problem the wrong way. Draw $11$ dots. Now you want to separate these $11$ dots into three separate collections (one for each variable). One way is to draw two lines that separates the $11$ dots into three piles (left, middle, center). Instead of drawing two lines, add two more dots (the number of piles, or variables, less one), and now pick any two dots (or alternatively, pick any $11$ dots, which must leave two behind).

So, you have $11+3-1$ dots, and you are selecting any $2$, which gives $\binom{11+3-1}{2} = \binom{11+3-1}{11}$ possibilities.

This generalizes easily. If you are looking for non-negative solutions to $x_1+\dots + x_n = r$, then there are $\binom{n+r-1}{r}=\binom{n+r-1}{n-1}$ solutions.