Dahil etme-dışlama ilkesi
Gelen kombinatorik , içerme-dışlama prensibi sayesinde elemanların (veya sayısını ifade etmek kılan kardinal a) sonlu birliği sonlu kümeler bu setleri ve bunların kavşak elemanlarının sayısının bir fonksiyonu olarak. Olasılıklar açısından geneller .
Matematikçi Abraham de Moivre'ye atfedilir ve aynı zamanda Poincaré elek formülü , Poincaré formülü veya elek formülü adı altında da bilinir (olasılıklı versiyonu) .
İki setin durumu
Misal
20 öğrenciden 10'u matematik, 11'i fizik ve 4'ü her ikisini de okuyor. Matematik veya fizik okumayan kaç öğrenci var?
Bir Venn diyagramının oluşturulması, öğrencilerin genel dağılımını kolayca görselleştirmeyi mümkün kılar.
Renkli bir alan bir grubu temsil eder. E tüm öğrenci grubunu, M “matematik çalışma” özelliğine sahip olanları , P “fizik çalışma” özelliğine sahip olanları temsil eder.
Daha sonra her bölge için öğrenci sayısı not edilir. Dört kişi hem matematik hem de fizik okuduğundan, iki dairenin kesişme noktasında 4 öğrenci var. Yani matematik okuyan ama fizik çalışmayan 10 - 4 = 6 kişi ve fizik okuyan ama matematik çalışmayan 11 - 4 = 7 kişi var. Bu nedenle, matematik veya fizik okumayan hala 20 - (6 + 4 + 7) = 3 kişi var.
Bu iki özelliğe sahip olmayan öğrencilerin sayısını veren dahil etme-dışlama ilkesi kullanılarak bu sonuç kolayca bulunur: 20 - 10 - 11 + 4 = 3.
N = 2 için formül
Let A ve B olmak iki sonlu setleri, formül yazılır
|AT∪B|=|AT|+|B|-|AT∩B|{\ displaystyle | A \ fincan B | = | A | + | B | - | A \ cap B |}nerede | A | ve | B | A ve B'nin ilgili kardinalini temsil eder .
Başka bir deyişle, bu iki kümenin kardinallerini ekleyerek ve kardinali kesişiminden çıkararak iki A ve B kümesinin birleşiminin elemanlarını sayabiliriz .
Genel dava
Let A 1 , ..., A n n sonlu setleri. Sahibiz
|⋃ben=1değilATben|=∑ben=1değil|ATben|-∑(ben,j)/1≤ben<j≤değil|ATben∩ATj|+∑(ben,j,k)/1≤ben<j<k≤değil|ATben∩ATj∩ATk|- ⋯⋯ +(-1)değil+1|AT1∩...∩ATdeğil|{\ displaystyle \ sol | \, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ sağ | = \ toplamı _ {i = 1} ^ {n} \ sol | A_ {i} \ right | - \ sum _ {(i, j) \, / \, 1 \ leq i <j \ leq n} \ left | A_ {i} \ cap A_ {j} \ right | + \ sum _ {(i , j, k) \, / \, 1 \ leq i <j <k \ leq n} \ left | A_ {i} \ cap A_ {j} \ cap A_ {k} \ right | - \ \ cdots \ cdots \ + (- 1) ^ {n + 1} | A_ {1} \ cap \ ldots \ cap A_ {n} |}nerede | A | sonlu bir A kümesinin kardinalini gösterir .
Bu formül ayrıca daha yoğun bir şekilde de yazılabilir:
Teorem - .
|⋃ben=1değilATben|=∑k=1değil(-1)k-1∑1≤ben1<ben2<...<benk≤değil|ATben1∩ATben2∩...∩ATbenk|{\ displaystyle \ sol | \, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ sağ | = \ toplamı _ {k = 1} ^ {n} (- 1) ^ {k- 1} \ sum _ {1 \ leq i_ {1} <i_ {2} <\ ldots <i_ {k} \ leq n} \ left | A_ {i_ {1}} \ cap A_ {i_ {2}} \ cap \ ldots \ cap A_ {i_ {k}} \ sağ |}
N üzerinde tümevarım ile veya gösterge fonksiyonları kullanılarak ispatlanabilir .
E , A i kümelerini içeren sonlu bir küme olsun . Tamamlayıcıya geçerek, herhangi bir A i'ye ait olmayan E elementlerinin önemini anlıyoruz :
|E∖⋃ben=1değilATben|=|E|+∑k=1değil(-1)k∑1≤ben1<ben2<...<benk≤değil|ATben1∩ATben2∩...∩ATbenk|{\ displaystyle \ sol | E \ setminus \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ sağ | = | E | + \ toplamı _ {k = 1} ^ {n} (- 1 ) ^ {k} \ sum _ {1 \ leq i_ {1} <i_ {2} <\ ldots <i_ {k} \ leq n} \ left | A_ {i_ {1}} \ cap A_ {i_ {2 }} \ cap \ ldots \ cap A_ {i_ {k}} \ sağ |}.
Dahil etme-dışlama ilkesi , Möbius ters çevirme formülünün özel bir genellemesi olarak görülebilir .
Olasılıklı versiyon
Bir olalım probabilized alanı ve elemanları arasında kabilesi . Sahibiz
(Ω,AT,P){\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P})}değil{\ displaystyle n}AT1,AT2,...,ATdeğil{\ displaystyle A_ {1}, A_ {2}, \ noktalar, A_ {n}} AT{\ displaystyle {\ mathcal {A}}}
P(⋃ben=1değilATben)=∑k=1değil(-1)k-1∑1≤ben1<ben2<...<benk≤değilP(ATben1∩ATben2∩...∩ATbenk){\ displaystyle \ mathbb {P} \ sol (\, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ sağ) = \ toplamı _ {k = 1} ^ {n} (- 1 ) ^ {k-1} \ sum _ {1 \ leq i_ {1} <i_ {2} <\ ldots <i_ {k} \ leq n} \ mathbb {P} \ left (A_ {i_ {1}} \ cap A_ {i_ {2}} \ cap \ ldots \ cap A_ {i_ {k}} \ sağ)}.
Bu formül n üzerinde tümevarımla veya önceki formülle aynı şekilde gösterge fonksiyonları kullanılarak gösterilebilir. Aşağıdaki gibi de formüle edilebilir:
P(⋃ben=1değilATben)=∑S⊂[[1,değil]],S≠∅(-1)|S|-1 P(⋂ben∈SATben){\ displaystyle \ mathbb {P} \ sol (\, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ sağ) = \ toplamı _ {S \ altküme [\! [1, n] \!], \, S \ neq \ varnothing} (- 1) ^ {| S | -1} \ \ mathbb {P} \ left (\ bigcap _ {i \ in S} \, A_ {i} \ sağ )}.
Başvurular
Bonferroni eşitsizlikleri
Formülün ilk terimlerinin kısmi toplamları, dönüşümlü olarak tam toplamın bir üst ve alt sınırını sağlar ve ikincisinin yaklaşımı olarak kullanılabilir: bu artışlar ve azalmalar, yazarlarının Carlo adından Bonferroni eşitsizlikleri olarak adlandırılır. Emilio Bonferroni .
Bir permütasyonun hataları ve sabit noktalarının sayısı
Kombinasyonlarda, elek formülü, sonlu bir kümenin bozulma sayısını belirlemeyi ve dolayısıyla karşılaşma problemini çözmeyi mümkün kılar . Bir dizi bir düzensizliği X a, bijection arasında X olmadan kendi üzerine sabit bir noktaya . İçerme-dışlama ilkesine ve için alarak teşekkürler A i permütasyon kümesi X bırakarak ı değişmez, biz eğer kanıtlayabilirim kardinalitesi ait X eşittir n , daha sonra bozuklukları sayısı X eşittir . Bu, n ! / E'ye en yakın tam sayıdır (burada e , doğal logaritmaların tabanını gösterir ). Bijection gelişigüzel alınan olasılık bir rahatsızlık doğru hızla eğilimi olduğu sonucu 1 / e kadar , n sonsuza doğru gitmektedir.
değil!∑k=0değil(-1)kk!{\ displaystyle n! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}}}
Sabit permütasyon noktalarının istatistiksel çalışmasını daha ileriye taşıyabiliriz . Bir permütasyonun ω sabit noktalarının sayısını N ( ω ) ile gösterelim . Bu sayı, ancak ve ancak ω bir hata ise sıfırdır . Bunda, aşağıdaki önerme, rahatsızlıklarla ilgili sonucu belirtir (bu, hesaplanmasından başka bir şey değildir ):
P(DEĞİL=0){\ displaystyle \ mathbb {P} \ sol (N = 0 \ sağ)}
Önerme - 0 ile n arasında herhangi bir k tamsayısı için ,
P(DEĞİL=k) = 1k!∑ℓ=0değil-k(-1)ℓℓ!{\ displaystyle \ mathbb {P} (N = k) \ = \ {\ frac {1} {k!}} \ quad \ sum _ {\ ell = 0} ^ {nk} {\ frac {(-1) ^ {\ ell}} {\ ell!}}}.
Özellikle, N yasası , büyük n için 1. parametrenin Poisson yasasına çok yakındır . Bu , çok sayıda küçük parametreli, zayıf korelasyonlu Bernoulli değişkenlerinin toplamının yaklaşık olarak Poisson dağılımını takip ettiği Poisson paradigmasını gösterir: N , böyle bir toplam olarak görülebilir . Bu komut dosyası sağlar ortalamasını ve varyansını hesaplamak N hızlı Kanunu yukarıdaki ifadeyi kullanmaktan daha No .
Dahil dışlama ilkesi ayrıca için alarak göstermek mümkün kılar A τ permütasyon grubu X bir döngü kabul t alınmak , 2 seviyesinde bu sırayla 2 arasında bir döngüsü olan permütasyon sayısı , m olan tam sayı kısmı ve n / 2. Daha genel olarak, sırası herhangi bir döngüsü olan permütasyon sayısı p olduğu burada, m, bir tam sayı parçası arasında n / p .
değil!∑k=0m(-1)k2kk!{\ displaystyle n! \ sum _ {k = 0} ^ {m} {\ frac {(-1) ^ {k}} {2 ^ {k} k!}}}değil!∑k=0m(-1)kpkk!{\ displaystyle n! \ sum _ {k = 0} ^ {m} {\ frac {(-1) ^ {k}} {p ^ {k} k!}}}
Sonlu bir kümeden başka bir kümeye yapılan surjections sayısı
Let X ve Y olmak iki sonlu kümeler. Set düşünün gelen haritaların X için Y herhangi bir öğe için, ve y arasında Y , alt kümesi değeri asla haritaların y . Grubu surjections gelen X ile Y sonra eşittir ve önem düzeyi bu nedenle:
E: =YX{\ displaystyle E: = Y ^ {X}}ATy{\ displaystyle A_ {y}}E∖⋃y∈YATy{\ displaystyle E \ setminus \ bigcup _ {y \, Y} A_ {y}}
Sp,q=|E|+∑k=1q(-1)k∑Z⊂Y|Z|=k|⋂y∈ZATy|=∑k=0q(-1)k∑Z⊂Y|Z|=k|(Y∖Z)X|=∑k=0q(-1)k∑Z⊂Y|Z|=k(q-k)p=∑k=0q(-1)k(qk)(q-k)p{\ displaystyle {\ begin {align} S_ {p, q} & = | E | + \ sum _ {k = 1} ^ {q} (- 1) ^ {k} \ sum _ {Z \ altküme Y \ atop | Z | = k} \ left | \ bigcap _ {y \ in Z} A_ {y} \ right | \\ & = \ sum _ {k = 0} ^ {q} (- 1) ^ {k} \ sum _ {Z \ subset Y \ atop | Z | = k} \ left | (Y \ setminus Z) ^ {X} \ right | \\ & = \ sum _ {k = 0} ^ {q} (- 1) ^ {k} \ sum _ {Z \ subset Y \ atop | Z | = k} (qk) ^ {p} \\ & = \ sum _ {k = 0} ^ {q} (- 1) ^ {k} {\ binom {q} {k}} (qk) ^ {p} \ end {hizalı}}}veya yine, indeks değişikliği ile:
Önerme - Let . Bir eleman kümesinden bir eleman kümesine yapılan eklerin sayısı şu şekilde verilir:
p,q∈DEĞİL{\ displaystyle p, q \ in \ mathbb {N}}Sp,q{\ displaystyle S_ {p, q}}p{\ displaystyle p}q{\ displaystyle q}
Sp,q=∑j=0q(-1)q-j(qj)jp{\ displaystyle S_ {p, q} = \ toplam _ {j = 0} ^ {q} (- 1) ^ {qj} {\ binom {q} {j}} j ^ {p}}.
Worpitzky sayıları
Let m ve n olmak iki katı pozitif tamsayılar. Wortpitzky sayısı , n renkli bir çizgi halinde düzenlenmiş m kareleri renklendirme yöntemlerinin sayısıdır , her renk en az bir kez görünür ve her kare de renksiz kalabilir. Dahil etme-dışlama ilkesinin olasılıkçı versiyonunu kullanmak için bir ifade bulabiliriz . Her kare için, tekdüze dağılımlı {1, ..., n +1} arasından rastgele bir renk çizeriz . Çizilen renk n +1 ise karenin renksiz olduğu anlamına gelir. 1'den n'ye değişen her renk i için olayı ifade ediyoruz : renk i herhangi bir karede kullanılmaz. Daha sonra elimizde:
Wmdeğil{\ displaystyle W_ {mn}}Wmdeğil{\ displaystyle W_ {mn}}ATben{\ displaystyle A_ {i}}
P(ATben)=değilm(değil+1)m{\ displaystyle \ mathbb {P} (A_ {i}) = {\ frac {n ^ {m}} {(n + 1) ^ {m}}}}
P(ATben∪ATj)=(değil-1)m(değil+1)m{\ displaystyle \ mathbb {P} (A_ {i} \ cup A_ {j}) = {\ frac {(n-1) ^ {m}} {(n + 1) ^ {m}}}}tüm i < j .
P(ATben∪ATj∪ATk)=(değil-2)m(değil+1)m{\ displaystyle \ mathbb {P} (A_ {i} \ cup A_ {j} \ cup A_ {k}) = {\ frac {(n-2) ^ {m}} {(n + 1) ^ {m }}}}tüm i < j < k için
vb. Dahil etme-hariç tutma formülü şunları verir:
P(⋃ben=1değilATben)=∑k=1değil(-1)k-1(değilk)(değil+1-k)m(değil+1)m{\ displaystyle \ mathbb {P} \ sol (\, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ sağ) = \ toplamı _ {k = 1} ^ {n} (- 1 ) ^ {k-1} {n \ seçin k} {\ frac {(n + 1-k) ^ {m}} {(n + 1) ^ {m}}}}Karşıt olayın olasılığı, sonuç olarak , sonuçtan başka bir şey değildir :
Wmdeğil(değil+1)m{\ displaystyle {\ frac {W_ {mn}} {(n + 1) ^ {m}}}}
Wmdeğil=∑k=0değil(-1)k(değilk)(değil+1-k)m{\ displaystyle W_ {mn} = \ toplam _ {k = 0} ^ {n} (- 1) ^ {k} {n \ k seçin} (n + 1-k) ^ {m}}
Notlar ve referanslar
-
bağlantısına bakın aşağıda etmek Vikiversite .
-
Olasılıklı uzay burada , önemsiz kabile ve tekdüze yasa ile sağlanan sonlu permütasyon kümesidirSdeğil{\ displaystyle {\ mathfrak {S}} _ {n}}[[1,değil]]{\ displaystyle [\! [1, n] \!]} .
-
(inç) AD Barbour , L. Holst ve S. Janson , Poisson yaklaşımı , Oxford, Clarendon Press, Oxford University Press ,1992, 277 p. ( ISBN 0-19-852235-5 ).
-
(in) Larry Carter ve Stan Wagon, " Erkek ıslah enstitüsü " , Amer. Matematik. Aylık , cilt. 125, n, o , 4,Nisan 2018, s. 306-319.
-
Sam Vandervelde, " Worpitzky sayıları yeniden ziyaret edildi, " Amer. Matematik. Aylık , cilt. 125, n o 3,Mart 2018
Ayrıca görün
Toplam kuralı
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">