Past exam of the mathematics course of the University of Cambridge / 2010 / ia / Paper 4 / 7E / b / Solution

For finite sets $C_1,\dots ,C_k$, the inclusion-exclusion principle statesIn a finite ambient set $\Omega$, its equivalent complement form iswhere the intersection for $J=\varnothing$ means $\Omega$. To see the counting mechanism, an element in exactly $r\ge 1$ of the sets has coefficient ${\sum }_{i=1}^r(-1{)}^{i+1}(\genfrac{}{}{0ex}{}{r}{i})=1$, by the binomial theorem; an element in none has coefficient zero in the union formula.