PIE (Principle of Inclusion-Exclusion) A1,A2,.,AnCU←—universe Ai∩A2n…An=S0-S+S2+…+(-1)"Sm Ar=∩A Ao=U i∈I Sk=∑IA So =Ao=U I=kPIE (Principle of Inclusion-Exclusion) A1, A2,...,An ￾ U universe ￾ ￾A1 ⇥ A2 ⇥ ··· An ￾ ￾ = AI = ￾ i￾I Ai A￾ = U Sk = ￾ |I|=k |AI | S0 = |A￾| = |U| S0 ￾ S1 + S2 + ··· + (￾1)nSn