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?
Best Answer
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}$.