Recitation 28

In this last recitation, we discussed a useful specialized version of the inclusion-exclusion principle. Suppose $A_1, \ldots, A_n\subset U$ are finite sets. In addition, $\left|\bigcap_{i\in S}A_i\right|$ only depends on $\left|S\right|$. Thus we may assume that if $\left|S\right|=k$, then $\left|\bigcap_{i\in S}A_i\right|=f(k)$. Under this hypothesis, we have $\left|\left(\bigcup_{i=1}^nA_i\right)^c\right|=\sum_{k=1}^n(-1)^k{n\choose k}f(k)$.