Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2009/ia/paper-4/6e/b/solution

Use the universe and define the exact-occupancy events . The desired collection is , so apply inclusion-exclusion to these events.
Fix distinct block indices. For to belong to the intersection of their events, it must contain exactly three elements in each selected block. There are ways to make those choices. None of the other elements in these selected blocks may be included; the remaining elements must come from the elements outside the selected blocks. Thus
There are choices of block indices, and the intersection is empty when . Substitution into inclusion-exclusion gives
Here binomial coefficients with a lower argument exceeding a nonnegative upper argument are zero. In particular, when every event is empty, and when the sum is empty; both give the correct answer zero. The subtraction of entire selected blocks, not merely the chosen elements, is what enforces exact rather than at-least-three occupancy. This is inclusion-exclusion for exact block occupancy with the number of blocks and subset size both equal to .

New to topics? Read the docs here!