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 = iI 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 = iI 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 = iI A = U Ai = [n] ([m] \ I) |AI | = (m |I|) n = ⇤ m k=1 (1)mk 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)mk 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)mk 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]