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).

Leave a Reply

Your email address will not be published. Required fields are marked *