## Tuesday, December 23, 2008

### Vacation From School

In how many ways can you arrange 100 identical stones into 3 piles so that each pile has at least 1 stone in it.

Labels:
Math

Subscribe to:
Post Comments (Atom)

In how many ways can you arrange 100 identical stones into 3 piles so that each pile has at least 1 stone in it.

Labels:
Math

Subscribe to:
Post Comments (Atom)

I'll take a crack at it; Let me see:

ReplyDeleteIf the piles are non-identical (indexed with 1,2,3), then the first pile may have n = between 1 and 98 stones. In each of these cases, the number of stones in the second pile can range from 1 to (100 - (n + 1)), and after that the distribution is uniquely identified. So the total number of combinations is SUM(n=1 to 98)[99-n], or SUM(1,2,3,...,98), which is equal to 4,581.

If the piles are identical (so that, for instance, {1,1,98} is the same distribution as {1,98,1}), we can group the combinations above and count the number of such groups, leaving out the "repeated" combinations. There is no {n,n,n} combination, since 100 % 3 <> 0. There are 49 {n,n,m} combinations (one for each number such that m = 100 - 2*n > 0), and each occurs 3 times ([n,n,m],[n,m,n],[m,n,n]). The remaining 4,434 (4,581 - 49*3) combinations are [n,m,l] combinations with no repeated entries, and they occur 6 times each ([n,m,l],[n,l,m],[m,n,l],[m,l,n],[l,m,n],[l,n,m]), for a total of 739 unique combinations. Now, 49 + 739 = 788; so I believe that is our answer?

98+97+96+95+......+3+2+1 = 4851

ReplyDeleteNice work, both of you. Here's another way to explain it, although oudeis did a great job above.

ReplyDeleteBy removing one stone from each pile, this is the number of ways you can arrange m-k identical stones into k (possibly empty) piles.

Now, view the k piles as a numbered set .

Write on each stone the number of a chosen pile and order the stones accordingly.

The numbered stones constitute a combination with repetition of k elements (the numbers) choose m-k (the stones). This can be done in

C'(k,m-k) = C(m-1,m-k) =

(m - 1)!

----------------- ways.

(m - k)!(k - 1)!