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.

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

share|improve this question
    
Your formula for the unconstrained case is wrong: you should have $\binom{30+10-1}{30}=\binom{39}9$ possibilities. It's the oranges that get chosen by the kids, not the kids that get chosen by the oranges. –  Marc van Leeuwen Dec 11 '11 at 14:15

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
That's what I finally did, thanks! –  yotamoo Dec 12 '11 at 9:22

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.