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.

You have 20 identical cookies that you want to distribute amoung 7 children, without breaking the cookies, how many ways can this be done... a) if every child gets at least one cookie? b) if not every child gets a cookie?

This was explained to me through stars and bars, the answer to a being 19 choose 6 and b 26 choose 6. How could I understand/justify this answer?

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

First, for b), think of it like having 20 cookies and 6 "partitions". If you arrange the 20 cookies and the 6 "partitions", this corresponds to a unique cookie distribution (every cookie before the partition goes to the first child, everything between the first two partitions goes to the second child, etc.). Also, for all ways to distribute the cookies there is a unique way to arrange the 20 cookies and 6 partitions. So, this amounts to the number of ways to choose 6 of the 26 spots for the partitions (and filling in the remaining spots with cookies): $\binom{26}{6}$.

For a), simply assign one cookie to each child first. You now have 13 cookies to distribute however you like, so by the same logic as was used in b), there are $\binom{13 + 6}{6} = \binom{19}{6}$ ways.

In general, if you have $m$ cookies and $n$ children there are $\binom{n + m - 1}{n-1}$ ways to do the assignment, and if child each has some minimum number of cookies $c_i$, then let $k = \sum_{i} c_i$ (the sum of the minimum number of cookies). We now have $\binom{n + (m - k) - 1}{n - 1}$.

share|improve this answer
    
This was a great explanation! Thanks, I have been trying to get this question clearly answered for a couple weeks. –  Olivia Irving Dec 14 '12 at 5:26
    
I have to say again thank you! This was on my final! :) –  Olivia Irving Dec 16 '12 at 1:42
    
Just to be sure, I know this was posted a while ago, but the first formula, m+n-1 and n-1 ( sorry about the formatting). That would be valid when applied in problems such as the following: how to distribute m balls among 4 urns it would be m+3 choose 3? –  Olivia Irving Dec 27 '12 at 5:21
    
Yes, that's right. If you're just trying to memorize the formula it will be very easy to mix up $n$ and $m$. You can try small cases to see which is which (1 ball, 2 urns; 2 balls 1 urn). However, you will learn far more if you remember how the expression arose and derive it when you need it. (This, of course, is true across almost all mathematics.) –  William Macrae Dec 27 '12 at 11:34
    
Yes, for the exam I just wanted to check, but –  Olivia Irving Dec 28 '12 at 19:40
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.