The Sieve Methods
The Sieve Methods
PIE (Principle of Inclusion-Exclusion) |AUB=A+|B|-A∩B AUBUC=A+B+C -A∩B-A∩C-B∩C +AnBnC C BnC AnC AnBnC B AnB
PIE (Principle of Inclusion-Exclusion) |A B| = |A| + |B| |A ⇥ B| |A B C| = |A| + |B| + |C| |A ⇥ B| |A ⇥ C| |B ⇥ C| +|A B C|
PIE (Principle of Inclusion-Exclusion) n= ∑|A-∑IA,nA+ 二1 1≤i≤m 1≤i<j≤n …+(-1)n-1|A1∩…nAnl =∑(--1∩A: IC{1,…,n} I≠0
PIE (Principle of Inclusion-Exclusion) ⇥ n i=1 Ai = 1in |Ai| 1i<jn |Ai ⇥ Aj |+ ··· + (1)n1|A1 ⇤ ··· ⇤ An| = I{1,...,n} I= (1)|I|1 iI Ai
PIE (Principle of Inclusion-Exclusion) A1,A2,...,An CU universe 元nn周-U4 -2,-y-1QA I{1，，n} I≠0 A虹=∩A, Ao=U i∈I
PIE (Principle of Inclusion-Exclusion) A1, A2,...,An U universe A1 ⇥ A2 ⇥ ··· An = U ⇥ n i=1 Ai AI = iI Ai A = U = |U| I{1,...,n} I= (1)|I|1 iI Ai
PIE (Principle of Inclusion-Exclusion) A1,A2,...,An U universe AinA2n…An=(-1)川|Al IC{1,.,n} Ar=∩A, Ao=U i∈1
PIE (Principle of Inclusion-Exclusion) A1, A2,...,An U universe A1 ⇥ A2 ⇥ ··· An = AI = iI Ai A = U I{1,...,n} (1)|I| |AI |