Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Search this website for "stars and bars" and you will see this question has been asked and answered here many times. –  Gerry Myerson Mar 6 '13 at 4:52

4 Answers 4

up vote 8 down vote accepted

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

share|improve this answer
    
+1 nice illustration! :^) –  B. S. Mar 6 '13 at 5:15
    
I'm a fully grown adult and I really appreciate that illustration. –  papercuts Mar 6 '13 at 5:18
2  
At any age, one solves problems by associating concrete images with the solution process, not "formulas." –  André Nicolas Mar 6 '13 at 5:20
    
+1: Ahh, cool... I'm a pictures guy. (I wish Rudin was too.) –  copper.hat Mar 6 '13 at 5:31
    
Any solution to little drawings the way mathjax is to formulae? –  copper.hat Mar 6 '13 at 5:32

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

share|improve this answer
    
In the Wikipedia link above, see theorem (2). If you want more practice with this type of "stars and bars" problem, search MSE with key words "stars and bars": it's a very common question, and there are lots of wonderful answers. –  amWhy Mar 6 '13 at 5:02

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.