A befogadás-kirekesztés elve
A kombinatorika , a befogadás elve kizárás lehetővé teszi, hogy kifejezze az elemek számát (vagy bíboros ) egy véges uniója véges készletek függvényében az elemek száma ezen készletek és a csomópontok. A valószínűségek szempontjából általánosít .
Abraham de Moivre matematikusnak tulajdonítják , és Poincaré szitaképlet , Poincaré- képlet vagy szitaképlet néven is ismert (ő vagy valószínűségi változata) .
Két halmaz esete
Példa
20 diákból 10 matematikát, 11 fizikát és 4 mindkettőt tanul. Hány olyan diák van, aki nem tanul matematikát vagy fizikát?
A Venn-diagram elkészítése lehetővé teszi a hallgatók általános megoszlásának egyszerű vizualizálását.
Színes terület jelent egy csoportot. E a hallgatók egész csoportját, M azt jelenti, akik rendelkeznek a „matematika tanulmányozásának” tulajdonságával, P a „fizika tanulásának” tulajdonságait.
Ezután minden zónához feljegyzik a hallgatók számát. Mivel négy ember tanul matematikát és fizikát egyaránt, a két kör kereszteződésében 4 tanuló van. Tehát 10 - 4 = 6 ember tanul matematikát, de nem fizikát, és 11 - 4 = 7 ember, aki fizikát tanul, de nem matematikát. Ezért még mindig 20 - (6 + 4 + 7) = 3 ember van, aki nem tanul matematikát vagy fizikát.
Ez az eredmény könnyen megtalálható az inklúzió-kirekesztés elvének alkalmazásával, amely megadja azon hallgatók számát, akik nem rendelkeznek ezzel a két tulajdonsággal: 20 - 10 - 11 + 4 = 3.
N = 2 képlet
Legyen A és B két véges halmaz, a képlet fel van írva
|NÁL NÉL∪B|=|NÁL NÉL|+|B|-|NÁL NÉL∩B|{\ displaystyle | A \ csésze B | = | A | + | B | - | A \ sapka B |}ahol | A | és | B | képviselik A és B megfelelő bíborosát .
Más szavakkal, megszámlálhatjuk két A és B halmaz egyesülésének elemeit, ha összeadjuk ennek a két halmaznak a bíborosait, és kivonjuk a bíborost metszéspontjukból.
Általános eset
Legyen A 1 , ..., A n n véges halmaz. Nekünk van
|⋃én=1nemNÁL NÉLén|=∑én=1nem|NÁL NÉLén|-∑(én,j)/1≤én<j≤nem|NÁL NÉLén∩NÁL NÉLj|+∑(én,j,k)/1≤én<j<k≤nem|NÁL NÉLén∩NÁL NÉLj∩NÁL NÉLk|- ⋯⋯ +(-1)nem+1|NÁL NÉL1∩...∩NÁL NÉLnem|{\ displaystyle \ left | \, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ right | = \ sum _ {i = 1} ^ {n} \ left | A_ {i} \ jobbra | - \ összeg _ {(i, j) \, / \, 1 \ leq i <j \ leq n} \ balra | A_ {i} \ sapka A_ {j} \ jobbra | + \ összeg _ {(i , j, k) \, / \, 1 \ leq i <j <k \ leq n} \ balra | A_ {i} \ cap A_ {j} \ cap A_ {k} \ right | - \ \ cdots \ cdots \ + (- 1) ^ {n + 1} | A_ {1} \ cap \ ldots \ cap A_ {n} |}ahol | A | jelöli a bíboros egy véges halmaz egy .
Ez a képlet tömörebb módon is írható:
Tétel - .
|⋃én=1nemNÁL NÉLén|=∑k=1nem(-1)k-1∑1≤én1<én2<...<énk≤nem|NÁL NÉLén1∩NÁL NÉLén2∩...∩NÁL NÉLénk|{\ displaystyle \ left | \, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ right | = \ sum _ {k = 1} ^ {n} (- 1) ^ {k- 1} \ sum _ {1 \ leq i_ {1} <i_ {2} <\ ldots <i_ {k} \ leq n} \ balra | A_ {i_ {1}} \ cap A_ {i_ {2}} \ cap \ ldots \ cap A_ {i_ {k}} \ right |}
Bizonyítható n-n történő indukcióval , vagy az indikátor függvények használatával .
Legyen E véges halmaz, amely tartalmazza az A i halmazokat . Azon komplexumokba való átadással következtethetünk az E elemek halmazának kardinalitására, amelyek nem tartoznak az A i egyikéhez sem :
|E∖⋃én=1nemNÁL NÉLén|=|E|+∑k=1nem(-1)k∑1≤én1<én2<...<énk≤nem|NÁL NÉLén1∩NÁL NÉLén2∩...∩NÁL NÉLénk|{\ displaystyle \ left | E \ setminus \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ right | = | E | + \ sum _ {k = 1} ^ {n} (- 1 ) ^ {k} \ sum _ {1 \ leq i_ {1} <i_ {2} <\ ldots <i_ {k} \ leq n} \ balra | A_ {i_ {1}} \ cap A_ {i_ {2 }} \ cap \ ldots \ cap A_ {i_ {k}} \ right |}.
A befogadás-kizárás elve a Möbius-inverziós képlet általánosításának speciális eseteként tekinthető .
Valószínűségi változat
Legyen egy valószínűsített tér és a törzs elemei . Nekünk van
(Ω,NÁL NÉL,P){\ displaystyle (\ Omega, {\ mathcal {A}}, \ mathbb {P})}nem{\ displaystyle n}NÁL NÉL1,NÁL NÉL2,...,NÁL NÉLnem{\ displaystyle A_ {1}, A_ {2}, \ pontok, A_ {n}} NÁL NÉL{\ displaystyle {\ mathcal {A}}}
P(⋃én=1nemNÁL NÉLén)=∑k=1nem(-1)k-1∑1≤én1<én2<...<énk≤nemP(NÁL NÉLén1∩NÁL NÉLén2∩...∩NÁL NÉLénk){\ displaystyle \ mathbb {P} \ balra (\, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ jobbra) = \ sum _ {k = 1} ^ {n} (- 1 ) ^ {k-1} \ sum _ {1 \ leq i_ {1} <i_ {2} <\ ldots <i_ {k} \ leq n} \ mathbb {P} \ balra (A_ {i_ {1}} \ cap A_ {i_ {2}} \ cap \ ldots \ cap A_ {i_ {k}} \ right)}.
Ez a képlet az n képleten történő indukcióval vagy az indikátorfüggvények használatával bizonyítható , az előző képlethez hasonlóan. A következőképpen is megfogalmazható:
P(⋃én=1nemNÁL NÉLén)=∑S⊂[[1,nem]],S≠∅(-1)|S|-1 P(⋂én∈SNÁL NÉLén){\ displaystyle \ mathbb {P} \ bal (\, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ right) = \ sum _ {S \ részhalmaz [\! [1, n] \!], \, S \ neq \ varnothing} (- 1) ^ {| S | -1} \ \ mathbb {P} \ left (\ bigcap _ {i \ in S} \, A_ {i} \ right )}.
Alkalmazások
Bonferroni egyenlőtlenségek
A képlet első tagjai részösszegei felváltva adják meg a teljes összeg felső és alsó határát, és ezek közelítéseként használhatók: ezeket a növekedéseket és csökkenéseket Bonferroni egyenlőtlenségeknek nevezzük , szerzőjük nevéből Carlo Emilio Bonferroni .
A permutáció hibái és rögzített pontjainak száma
A kombinatorikában a szita képlete lehetővé teszi egy véges halmaz zavarainak számának meghatározását, és így a találkozások problémájának megoldását . A zavar egy sor X jelentése bijekciót az X önmagára nélkül egy fix pont . Hála a befogadás-kirekesztés elvét, és azáltal, hogy az A i halmaza permutációk X kilépő i invariáns, bizonyítani tudjuk, hogy ha a számosság az X egyenlő n , majd a számot zavarok X egyenlő . Ez az n ! / E-hez legközelebbi egész szám (ahol e a természetes logaritmusok alapját jelöli ). Ebből következik, hogy annak a valószínűsége, hogy a véletlenszerűen vett bijekció zavar, gyorsan az 1 / e felé halad, míg n a végtelenbe.
nem!∑k=0nem(-1)kk!{\ displaystyle n! \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}}}
Tovább tolhatjuk a permutációk rögzített pontjainak statisztikai vizsgálatát . Jelölje N ( ω ) a száma fix pontok permutációs ω . Ez a szám akkor és csak akkor nulla, ha ω hiba. Ebben a következő javaslat határozza meg a zavarokra vonatkozó eredményt (amely nem más, mint a számítás ):
P(NEM=0){\ displaystyle \ mathbb {P} \ bal (N = 0 \ jobb)}
Tétel : Bármely k 0 és n közötti egész szám esetén
P(NEM=k) = 1k!∑ℓ=0nem-k(-1)ℓℓ!{\ displaystyle \ mathbb {P} (N = k) \ = \ {\ frac {1} {k!}} \ quad \ sum _ {\ ell = 0} ^ {nk} {\ frac {(-1) ^ {\ ell}} {\ ell!}}}.
Különösen az N törvénye nagyon közel áll az 1. paraméter Poisson-törvényéhez , nagy n esetén . Ez azt mutatja, a Poisson paradigma , amely szerint egy bizonyos összeget a nagyszámú kis-paraméter, rosszul korrelált Bernoulli változók nagyjából követi a Poisson eloszlás: N látható , mint egy ilyen összeget. Ez a script lehetővé, hogy kiszámítja az átlag és szórás az N gyorsabb, mint a fenti kifejezés a törvény nem .
Az inklúzió-kizárás elve lehetővé teszi azt is megmutatni, hogy A τ-nak megadjuk az X permutációinak halmazát, amely befogadja a 2. rendű τ ciklust , hogy a 2. rendű ciklus nélküli permutációk száma , ahol m az egész szám. része a n / 2. Általánosabban, a száma permutációk nem rendelkező ciklus érdekében p jelentése , ahol m jelentése a egész része az n / p .
nem!∑k=0m(-1)k2kk!{\ displaystyle n! \ sum _ {k = 0} ^ {m} {\ frac {(-1) ^ {k}} {2 ^ {k} k!}}}nem!∑k=0m(-1)kokk!{\ displaystyle n! \ sum _ {k = 0} ^ {m} {\ frac {(-1) ^ {k}} {p ^ {k} k!}}}
A véges halmazból a másikba történő túladások száma
Legyen X és Y két véges halmaz. Fontolja meg a készlet a térképeket X és Y , és bármely elem y az Y , a részhalmaza térképek, amelyek soha nem érték y . A készlet surjections származó X , hogy Y ezután egyenlő és annak számossága tehát:
E: =Yx{\ displaystyle E: = Y ^ {X}}NÁL NÉLy{\ displaystyle A_ {y}}E∖⋃y∈YNÁL NÉLy{\ displaystyle E \ setminus \ bigcup _ {y \ Y} A_ {y}}
So,q=|E|+∑k=1q(-1)k∑Z⊂Y|Z|=k|⋂y∈ZNÁL NÉLy|=∑k=0q(-1)k∑Z⊂Y|Z|=k|(Y∖Z)x|=∑k=0q(-1)k∑Z⊂Y|Z|=k(q-k)o=∑k=0q(-1)k(qk)(q-k)o{\ displaystyle {\ begin {aligned} S_ {p, q} & = | E | + \ sum _ {k = 1} ^ {q} (- 1) ^ {k} \ sum _ {Z \ Y halmaz tetején | Z | = k} \ balra | \ bigcap _ {y \ -ban Z} A_ {y} \ jobbra | \\ & = \ sum _ {k = 0} ^ {q} (- 1) ^ {k} \ sum _ {Z \ Y \ athalmaz | Z | = k} \ bal | (Y \ setminus Z) ^ {X} \ right | \\ & = \ sum _ {k = 0} ^ {q} (- 1) ^ {k} \ sum _ {Z \ Y halmaz | Z | = k} (qk) ^ {p} \\ & = \ sum _ {k = 0} ^ {q} (- 1) ^ {k} {\ binom {q} {k}} (qk) ^ {p} \ end {igazítva}}}vagy újra, az index változásával:
Javaslat - Legyen . Az elemkészletből az elemkészletbe történő túlélések számát az alábbiak adják meg:
o,q∈NEM{\ displaystyle p, q \ in \ mathbb {N}}So,q{\ displaystyle S_ {p, q}}o{\ displaystyle p}q{\ displaystyle q}
So,q=∑j=0q(-1)q-j(qj)jo{\ displaystyle S_ {p, q} = \ sum _ {j = 0} ^ {q} (- 1) ^ {qj} {\ binom {q} {j}} j ^ {p}}.
Worpitzky számok
Legyen m és n két szigorúan pozitív egész szám. A Wortpitzky-szám az m négyzetek n színnel egy vonalba rendezett színezésének számos módja , mindegyik szín legalább egyszer megjelenik, és minden négyzet színtelen is maradhat. Találhatunk kifejezést a befogadás-kizárás elvének valószínűségi változatának használatára. Minden négyzethez véletlenszerűen rajzolunk egy színt {1, ..., n +1} közé, egyenletes eloszlással. Ha a rajzolt szín n +1, az azt jelenti, hogy a négyzet színtelen. Minden 1-től n- ig változó i szín esetén az eseményt jelöljük : az i színt egyetlen négyzetben sem használjuk. Ezután:
Wmnem{\ displaystyle W_ {mn}}Wmnem{\ displaystyle W_ {mn}}NÁL NÉLén{\ displaystyle A_ {i}}
P(NÁL NÉLén)=nemm(nem+1)m{\ displaystyle \ mathbb {P} (A_ {i}) = {\ frac {n ^ {m}} {(n + 1) ^ {m}}}}
P(NÁL NÉLén∪NÁL NÉLj)=(nem-1)m(nem+1)m{\ displaystyle \ mathbb {P} (A_ {i} \ pohár A_ {j}) = {\ frac {(n-1) ^ {m}} {(n + 1) ^ {m}}}}mindenre i < j .
P(NÁL NÉLén∪NÁL NÉLj∪NÁL NÉLk)=(nem-2)m(nem+1)m{\ displaystyle \ mathbb {P} (A_ {i} \ csésze A_ {j} \ csésze A_ {k}) = {\ frac {(n-2) ^ {m}} {(n + 1) ^ {m }}}}minden i < j < k
stb. Az inklúzió-kizárási képlet a következőket nyújtja:
P(⋃én=1nemNÁL NÉLén)=∑k=1nem(-1)k-1(nemk)(nem+1-k)m(nem+1)m{\ displaystyle \ mathbb {P} \ balra (\, \ bigcup _ {i = 1} ^ {n} A_ {i} \, \ jobbra) = \ sum _ {k = 1} ^ {n} (- 1 ) ^ {k-1} {n \ select k} {\ frac {(n + 1-k) ^ {m}} {(n + 1) ^ {m}}}}Az ellenkező esemény valószínűsége nem más, mint végül:
Wmnem(nem+1)m{\ displaystyle {\ frac {W_ {mn}} {(n + 1) ^ {m}}}}
Wmnem=∑k=0nem(-1)k(nemk)(nem+1-k)m{\ displaystyle W_ {mn} = \ sum _ {k = 0} ^ {n} (- 1) ^ {k} {n \ select k} (n + 1-k) ^ {m}}
Megjegyzések és hivatkozások
-
Lásd az alábbi linket a Wikegyetemhez .
-
A valószínûsített tér itt a véges permutációk halmazaSnem{\ displaystyle {\ mathfrak {S}} _ {n}}[[1,nem]]{\ displaystyle [\! [1, n] \!]} , amelyet a triviális törzs és az egységes törvény biztosít .
-
(a) AD Barbour , L. Holst , és S. Janson , Poisson-közelítés , Oxford, Clarendon Press, Oxford University Press ,1992, 277 o. ( ISBN 0-19-852235-5 ).
-
(in) Larry Carter és Stan Wagon, " A Mensa correctionnal Institute " , Amer. Math. Havi , vol. 125, n o 4,2018. április, P. 306-319.
-
Sam Vandervelde, „ A Worpitzky-számok áttekintésre kerültek ”, Amer. Math. Havi , vol. 125, n o 3,2018. március
Lásd is
Az összeg szabálya
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">