PIE (Principle of Inclusion-Exclusion) A1,A2,...,An U universe AnAn…An=S0-S1+S2+…+(-1)nSm A1=∩A, Ao=U i∈I Sk=∑|A So=Ao=U I=kPIE (Principle of Inclusion-Exclusion) A1, A2,...,An U universe A1 ⇥ A2 ⇥ ··· An = AI = iI Ai A = U Sk = |I|=k |AI | S0 = |A| = |U| S0 S1 + S2 + ··· + (1)nSn