# Counting marbles

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?

-

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?

-

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.

-
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. – Carry on Smiling Jul 12 '12 at 18:59