There are \({13 \choose 3}\) ways to distribute 10 cookies to 4 kids (using 10 stars and 3 bars). We will subtract all the outcomes in which a kid gets 3 or more cookies. How many outcomes are there like that? We can force kid A to eat 3 or more cookies by giving him 3 cookies before we start. Doing so reduces the problem to one in which we have 7 cookies to give to 4 kids without any restrictions. In that case, we have 7 stars (the 7 remaining cookies) and 3 bars (one less than the number of kids) so we can distribute the cookies in \({10 \choose 3}\) ways. Of course we could choose any one of the 4 kids to give too many cookies, so it would appear that there are \({4 \choose 1}{10 \choose 3}\) ways to distribute the cookies giving too many to one kid. But in fact, we have over counted.
We must get rid of the outcomes in which two kids have too many cookies. There are \({4 \choose 2}\) ways to select 2 kids to give extra cookies. It takes 6 cookies to do this, leaving only 4 cookies. So we have 4 stars and still 3 bars. The remaining 4 cookies can thus be distributed in \({7 \choose 3}\) ways (for each of the \({4 \choose 2}\) choices of which 2 kids to over-feed).
But now we have removed too much. We must add back in all the ways to give too many cookies to three kids. This uses 9 cookies, leaving only 1 to distribute to the 4 kids using stars and bars, which can be done in \({4 \choose 3}\) ways. We must consider this outcome for every possible choice of which three kids we over-feed, and there are \({4 \choose 3}\) ways of selecting that set of 3 kids.
Next we would subtract all the ways to give four kids too many cookies, but in this case, that number is 0.
All together we get that the number of ways to distribute 10 cookies to 4 kids without giving any kid more than 2 cookies is:
which is
This makes sense: there is NO way to distribute 10 cookies to 4 kids and make sure that nobody gets more than 2. It is slightly surprising that
but since PIE works, this equality must hold.