0
$\begingroup$

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?

1 Answers 1

2

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

  • 0
    This was a great explanation! Thanks, I have been trying to get this question clearly answered for a couple weeks.2012-12-14
  • 0
    I have to say again thank you! This was on my final! :)2012-12-16
  • 0
    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?2012-12-27
  • 0
    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.)2012-12-27
  • 0
    Yes, for the exam I just wanted to check, but2012-12-28