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 +A∩B∩C BnC AnC AnBnC A 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) a-∑A-,∑An+ 三1 1<i<m 1≤i<j≤n …+(-1)n-|A1∩…∩An Σ-04 IC{1,…,n}
PIE (Principle of Inclusion-Exclusion) ⇥ n i=1 Ai = = ⇥ I⇥{1,...,n} (1)|I|1 ⇤ i⇤I Ai 1in |Ai| 1i<jn |Ai ⇥ Aj |+ ··· + (1)n1|A1 ⇤ ··· ⇤ An|
PIE (Principle of Inclusion-Exclusion) A1,A2,...,An CU<universe rena。女-4 i=1 -叫￡H门 IC{1,,n} AI=∩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} (1)|I|1 ⇤ i⇤I Ai
PIE (Principle of Inclusion-Exclusion) A1,A2,...,An CU<universe AnA2n…An=∑(-1)I|A IC{1,,n} A1=∩Ai Ao=U i∈I
PIE (Principle of Inclusion-Exclusion) A1, A2,...,An U universe A1 ⇥ A2 ⇥ ··· An = AI = iI Ai A = U I{1,...,n} (1)|I| |AI |