南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Principle of Inclusion-Exclusion（PIE）

The Sieve Methods

The Sieve Methods

PIE (Principle of Inclusion-Exclusion) AUB|=A+|B-A∩B AUBUC=A+B+C -A∩B-A∩C1-|BnC1 +|A∩B∩C 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-,之4n+ 三1 1<i<n 1≤i<j≤n …+(-1)n-1|A1∩.∩An ≥-11门4 IC{1,,n} I≠0

PIE (Principle of Inclusion-Exclusion) ￾ ￾ ￾ ￾ ￾ ⇥ n i=1 Ai ￾ ￾ ￾ ￾ ￾ = ￾ 1￾i￾n |Ai| ￾ ￾ 1￾i<j￾n |Ai ⇥ Aj |+ ··· + (￾1)n￾1|A1 ⇤ ··· ⇤ An| = ￾ I￾{1,...,n} I￾=￾ (￾1)|I|￾1 ￾ ￾ ￾ ￾ ￾ ￾ i￾I Ai ￾ ￾ ￾ ￾ ￾

PIE (Principle of Inclusion-Exclusion) A1,A2,.,AnCU<— universe 西nena=-4刘 2=1 --- ic T I≠0 Ar=∩Ai 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} I￾=￾ (￾1)|I|￾1 ￾ ￾ ￾ ￾ ￾ ￾ i￾I Ai ￾ ￾ ￾ ￾ ￾

PIE (Principle of Inclusion-Exclusion) A1,A2,...,An CUuniverse AnAn…An=(-1)川|Ar IC{1,,n} AI=∩Aa 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,...,An U universe AnAn…An=S0-S1+S2+…+(-1)nSm A1=∩A, Ao=U i∈I Sk=∑|A 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→[m A=[m→([m\{}) ∩A=∑(-1)1A iElm] IC[m] AI=∩A: Ao=U i∈I

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

Surjections U=[m]→[m A:=[m→(m\{i) Ao=U Ar=∩Ai=[m→(Im\I) i∈I |Ar=(m-1I)” ∩A, =>(-1)|A iElm] IC[m] ∑(-1(m-1W”=-1()m- = IC[m] =-m-(）

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 ￾ I￾[m] (￾1)|I| |AI | ￾ ￾ ￾ ￾ ￾ ￾ ￾ i￾[m] Ai ￾ ￾ ￾ ￾ ￾ ￾ = = ￾ m k=0 (￾1)k ￾m k ￾ (m ￾ k) n

Surjections 网n四=-*（四） m kn k=1 (f-1(0),f-1(1),.,f-1(m-1) ordered m-partition of [n] 例-m{h} {}=-(） 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 m-partition of [n] ￾ ￾ ￾[n] onto ￾￾￾￾ [m] ￾ ￾ ￾ = m! ￾ n m ￾ ￾ n m ￾ = 1 m! ￾ m k=1 (￾1)m￾k ￾m k ￾ kn

Derangement les problemes des rencontres ESSAY DANALYSE Two decks,A and B,of cards: 5U我 LES JEUX DE HAZARD. The cards of A are laid out in a row, Par M:Remond de Montmort. and those of B are placed at random, one at the top on each card of A. w光a What is the probability that A PARIS, Chez JAcov Qo,Imprimeur-Jure-Libraire de I'Univerlite,rue Galande. no 2 cards are the same in each pair? M D CC V I I L AVEC APPROBATION ET PRINILIGE DU ROY

Derangement Two decks, A and B, of cards: The cards of A are laid out in a row, and those of B are placed at random, one at the top on each card of A. What is the probability that no 2 cards are the same in each pair? les problèmes des rencontrés :