[Math] Combination with repetition with an upper bound

combinatorics

I am trying to calculate the number of ways to divide $30$ oranges between $10$ kids, with the restriction that each kid will get no more then $5$ oranges. So, as far as I know I need to use the Inclusion–exclusion principle but I'm not sure how exactly.
Here's what I have so far:

Count the number of division with no restrictions so we have $\binom{30+9}{10}$.
Subtract the number of ways with restriction that one kid (or two or three) gets at least $6$ so we have $-\binom{(24+9)}{10}, -\binom{18+9}{10}$ and so on…

How do I continue from here? How do I calculate the intersection of $\binom{24+9}{10}$ and $\binom{18+9}{10}$?

Thanks…

Best Answer

You can use inclusion-exclusion when the problem with a more general but opposite constraint is easier. Here you've already computed the solution without constraints. If the constraint would be that the first kid gets at least $6$ oranges, then start giving those oranges, and find $\binom{30-6+9}{30-6}=\binom{33}9$ solutions. But not only could it be another kid that gets too many oranges, there could be more than one kid at once that gets too much. So the "more general opposite" constraint would be, for any set $S$ of kids, that all kids from $S$ get at least $6$ oranges. For this there are $\binom{30-6s+9}{30-6s}=\binom{39-6s}9$ solutions if $S$ has $s$ kids in it.

By inclusion-exclusion you need to count the solutions for $S=\emptyset$, subtract those for $S$ a singleton, add back for $S$ a doubleton, etc. All in all you get $$ \binom{39}9-\binom{10}1\binom{33}9+\binom{10}2\binom{27}9 -\binom{10}3\binom{21}9+\binom{10}4\binom{15}9 -\binom{10}5\binom99 $$ solutions, which if I calculated well gives $2\,930\,456$ possibilities, less than $1.5$% of the original $211\,915\,132$.

Added (much later). Alternatively, one could compute the coefficient of $X^{30}$ in $(1+X+X^2+X^3+X^4+X^5)^{10}=\frac{(1-X^6)^{10}}{(1-X)^{10}}$. This is quite easy (the numerator has only $6$ terms of degree${}\leq30$) and gives the same result, in fact even via the same formula.