PIE (Principle of Inclusion-Exclusion) A1,A2,:.,AnCU←—universe AinA2∩…An=S0-S1+S2+·+(-1)rSn A=∩A: Ao=U i∈I Sk=∑IA So |Aol Ul 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:[n]onto, m] U=[nl→[ml A,=[m]→([m{) 0- ∑(-1)1A iElm] IE[m] Ar=∩A, Ao=U i∈I
Surjections f : [n] onto ⇥ [m] # of U = [n] [m] Ai = [n] ([m] \ {i}) AI = iI Ai A = U I[m] (1)|I| |AI | i[m] Ai =
Surjections U=[nl→[ml A:=[n]→(ml\{i}) Ag=UAr=∩A:=[m→([m\I) i∈I |Ar=(m-1I)' ∩， ∑(-1)4 i∈[ml IC[m] =∑-0(m-”--()m- IC[m] 三-*()
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 I[m] (1)|I| |AI | i[m] Ai = = m k=0 (1)k m k (m k) n
Surjections m (f-1(0),f-1(1),.,f-1(m-1) ordered partition of [m] 网s例=m{n} {}-点2-1-()
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 les problemes des rencontres ESSAY DANALYSE Two decks,A and B,of cards: SUR 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. What is the probability that no 2 cards are the same in each pair?
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 :