Past exam of the mathematics course of the University of Cambridge / 2009 / ia / Paper 4 / 6E (Numbers and Sets)

For finite sets $X_1,\dots ,X_N$, the inclusion-exclusion principle statesTo prove it, fix an element belonging to exactly $s\ge 1$ of these sets. At level $r$ it is counted in precisely $\left(\genfrac{}{}{0ex}{}{s}{r}\right)$ intersections, so its total multiplicity on the right isby the binomial theorem. An element in no set contributes zero. Summing these equal multiplicities over the finite union proves inclusion-exclusion. This also explains why pairwise subtraction alone is insufficient: elements in triple and higher intersections must receive the alternating corrections.

Use the universe $\Omega =\{B\subseteq A:|B|=k\}$ and define the exact-occupancy events $E_i=\{B\in \Omega :|B\cap A_i|=3\}$. The desired collection is ${\bigcup }_{i=1}^k{E}_i$, so apply inclusion-exclusion to these events.

Fix $r$ distinct block indices. For $B$ to belong to the intersection of their events, it must contain exactly three elements in each selected block. There are ${\left(\genfrac{}{}{0ex}{}{m}{3}\right)}^r$ ways to make those choices. None of the other elements in these selected blocks may be included; the remaining $k-3r$ elements must come from the $n-rm$ elements outside the selected blocks. ThusThere are $\left(\genfrac{}{}{0ex}{}{k}{r}\right)$ choices of block indices, and the intersection is empty when $3r>k$. Substitution into inclusion-exclusion givesHere binomial coefficients with a lower argument exceeding a nonnegative upper argument are zero. In particular, when $m<3$ every event is empty, and when $k<3$ the sum is empty; both give the correct answer zero. The subtraction of entire selected blocks, not merely the $3r$ 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 $k$.