南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）The Sieve Methods

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 ￾ ￾ ￾ ￾ ￾ ￾ 1￾i￾n |Ai| ￾ ￾ 1￾i<j￾n |Ai ⇥ Aj |+ ··· + (￾1)n￾1|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 = ￾ i￾I 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 = ￾ i￾I Ai A￾ = U ￾ I￾{1,...,n} (￾1)|I| |AI |

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=k

PIE (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

Surjections of f (nl onto,(ml U=[m→[ml A=[ml→([ml\{i}) U-UA,=∑(-1)川1A icml】 E[m] AI=∩A: Ao=U 2∈I

Surjections f : [n] onto ￾￾￾⇥ [m] # of U = [n] ￾ [m] Ai = [n] ￾ ([m] \ {i}) AI = ￾ i￾I Ai A￾ = U ￾ ￾ ￾ ￾ ￾ ￾ U ￾ ⇥ i￾[m] Ai ￾ ￾ ￾ ￾ ￾ ￾ = ￾ I￾[m] (￾1)|I| |AI |

Surjections U=[ml→[m A:=[n→([m]\{i}) Ag=UAr=∩Ai=[m]→(m\I) i∈I |A=(m-|I)” U-UA=∑(-1)川14 IC[m] -0m-0°--1m(） IC(m] k=1

Surjections U = [n] ￾ [m] Ai = [n] ￾ ([m] \ {i}) AI = ￾ i￾I A￾ = U Ai = [n] ￾ ([m] \ I) |AI | = (m ￾ |I|) n = ⇤ m k=1 (￾1)m￾k ￾m k ⇥ kn = ￾ I￾[m] (￾1)|I| (m ￾ |I|) n ￾ ￾ ￾ ￾ ￾ ￾ U ￾ ⇥ i￾[m] Ai ￾ ￾ ￾ ￾ ￾ ￾ = ￾ I￾[m] (￾1)|I| |AI |

Surjections 网mm=-1m(g〉 m k=1 (f-1(0),f-1(1),.,f-1(m-1) ordered partition of [m] n,lonlm {}=-(） m kn

Surjections = ⇤ m k=1 (￾1)m￾k ￾m k ⇥ kn ￾ ￾ ￾[n] onto ￾￾￾⇥ [m] ￾ ￾ ￾ (f ￾1(0), f ￾1(1),...,f ￾1(m ￾ 1)) ordered partition of [m] ￾ ￾ ￾[n] onto ￾￾￾￾ [m] ￾ ￾ ￾ = m! ￾ n m ￾ ￾ n m ￾ = 1 m! ￾ m k=1 (￾1)m￾k ￾m k ￾ kn

Derangement permutation 7 of [n] i∈[m,π()丰i "permutations with no fixed point" U:permutations of[nlA;={π|π(i)=i} 石--君1 ieln] IEIn] A虹={π|i∈I,π(2)= Ar=(n-)川

Derangement ⇤i ￾ [n], ￾(i) ⇥= i permutation ￾ of [n] “permutations with no fixed point” Ai = {￾ | ￾(i) = i} AI = {￾ | ⇥i ￾ I, ￾(i) = i} |AI | = (n ￾ |I|)! ￾ ￾ ￾ ￾ ￾ ￾ U ￾ ⇤ i⇥[n] Ai ￾ ￾ ￾ ￾ ￾ ￾ = ⇥ I￾[n] (￾1)|I| |AI | U : permutations of [n]