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.

In how many ways can you distribute 9 marbles in 3 piles?

The marbles are all identical. I know its not a very deep question but I don't know how to solve it. There is a difference between (pile a getting 4 pile b getting 4 and pile c getting 1) and (pile a getting 1 pile b getting 4 and pile c getting 4). I first thought it was 9^3 but then i realized you needed to eliminate various combinations that gave the same result.

Is there a special name for the combination I'm asking for?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

You are asking for "combinations with repetitions" (you want to choose the 3 piles, 9 times, allowing the same pile to be chosen more than once, but you don't care the order in which you select the piles); it is sometimes also called (because of a particular method of proving the formulas) stars and bars:

Imagine all $9$ marbles on a line, indicated by stars: $$\star\quad\star\quad\star\quad\star\quad \star\quad\star\quad\star\quad \star\quad\star$$ Now, insert two vertical bar to indicate where you will finish the piles. For example, $$\star\quad\star\quad\star\quad\star\quad\Bigm|\quad \star\quad\star\quad\Bigm|\quad\star\quad \star\quad\star$$ means that you have 4 marbles in the first pile, two on the second pile, and three in the last pile; or $$\Bigm|\quad\star\quad\star\quad\star\quad\star\quad\Bigm|\quad\star\quad\star\quad\star\quad \star\quad\star$$ means no marbles in the first pile, four on the second pile, and five in the third pile; and $$\star\quad\star\quad\star\quad\star\quad\Bigm|\quad\Bigm|\quad \star\quad\star\quad\star\quad \star\quad\star$$ means four marbles in the first pile, no marbles on the second pile, and five on the third pile.

So you need to choose where to put two vertical bars. How many ways are there to do so?

share|improve this answer
add comment

Assuming marbles are the same, try to form a sequence of 9 M's and 2 |'s that break into 3 piles, e.g. MM|MMMMM|MM -> 2,5,2. Such a sequence representation captures exactly all possible pile distributions. Numbe rof such sequences is equivalent to picking 2 places in a sequence of length 9+2 = 11, so a total $\frac{11!}{2!9!} = 55$ ways.

share|improve this answer
2  
I think it's worth noting that a common name for this method is "stars and bars". en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) –  David Spencer Jul 12 '12 at 18:56
    
@David Spencer, +1, never heard of the name. I was taught this in combinatorics as a way to model the number of integer solutions to a set of equations, akin to what is trying to do in her answer below... –  gt6989b Jul 12 '12 at 18:57
    
I see, thanks a lot, I think thats correct. –  Bananarama Jul 12 '12 at 18:59
add comment

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.