# Inclusion Exclusion Principle

In how many ways can you distribute 20 identical objects to 10 distinct recipients such that each recipient receives at most five objects? How many ways if each receives at least one but at most five objects?

I denoted the universe as all 20 multisets of 10. I stated that my property is those recipients that received over 6 objects. Then I attempted to count those multisets without this property (those multisets where a recipient had more than 6 objects). ((10 20)) - (10 1)((10 14)) - (10 1)((10 15)) - ... - (10 1)((10 20)). Is this correct?

-

The total number of ways to distribute 20 identical objects among 10 distinct recipients without any restrictions would be ${29 \choose 9}$. Let this be denoted by N.

Let $A_i$ denote the set of cases in which the ith recipient gets 6 or more objects.

Then we have to calculate $n(A_1\bigcup A_2 \bigcup A_3 \bigcup ....\bigcup A_{10})$, i.e. those cases in which atleast one of the recipients gets more than 6 objects, and subtract it from N to get the required answer.

Now, $n(A_i)={23 \choose 9}, 1\le i\le10$

$n(A_i \bigcap A_j)={17 \choose 9}, 1\le i<j\le10$

and $n(A_i \bigcap A_j \bigcap A_k)={11 \choose 9}, 1\le i<j<k\le10$

All further intersections (of four or more sets) will have 0 elements, as it cannot be the case that more than 3 people get more than 5 elements each.

Therefore the required number of ways is ${29 \choose 9} - {10 \choose 1}{23 \choose 9} + {10 \choose 2}{17 \choose 9} - {10 \choose 3}{11 \choose 9}$

Hope I make sense.

-