Szitaformula

A matematikában a halmazelméletben a szitaformula egy halmazok elemszámának meghatározását segítő módszer. Főként a kombinatorikában, a számelméletben és a valószínűségszámításban alkalmazzák.

A képlet az alaphalmaz méretét nem feltétlenül diszjunkt részhalmazainak méretével fejezi ki. A nem diszjunkt halmazok méretének összege a méretet felülről becsli, melyet a metszetek méretének kivonásával korrigál.

Bővebb leírás

Ismert, hogy ha ${\displaystyle A}$ és ${\displaystyle B}$ véges halmazok, akkor

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$

Itt már felismerhető az alapelv: ${\displaystyle |A|+|B|}$ felülről becsüli az ${\displaystyle |A\cup B|}$ unió elemszámát. Ennek korrigálására egyszer ki kell vonni a ${\displaystyle |A\cap B|}$ metszet elemszámát, mivel ezeket az elemeket mind az ${\displaystyle A}$, mind a ${\displaystyle B}$ halmazhoz hozzászámoltuk, így kétszer lettek beszámolva.

A módszert kétszer alkalmazva

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}$

Általában, ${\displaystyle n}$ halmaz esetén a képlet

${\displaystyle X=A_{1}\cup A_{2}\cup \dotsb \cup A_{n}}$

• Első közelítésként az összes halmaz elemszámát beleszámoltuk. Ez egy felső becslés.

${\displaystyle X=A_{1}\cup A_{2}\cup \dotsb \cup A_{n}}$

• Második közelítésként kivonjuk a páronként képzett metszetek elemszámát, mivel ezeket kétszer számoltuk. Ezzel egy alsó becslést kapunk.

${\displaystyle |X|\geq \sum _{1\leq i\leq n}|A_{i}|~-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|}$

• Az előző művelettel töröltük a hármas metszetek elemszámát az összegből, így azt újra hozzá kell adnunk. Ez egy felső becslés.

${\displaystyle |X|\leq \sum _{1\leq i\leq n}|A_{i}|~-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|~+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|}$

• Az előző művelettel kétszer hozzáadtuk a négyes metszetek elemszámát, így azt újra le kell vonnunk. Ez egy alsó becslés.

${\displaystyle |X|\geq \sum _{1\leq i\leq n}|A_{i}|~-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|~+\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|~-\sum _{1\leq i<j<k<l\leq n}|A_{i}\cap A_{j}\cap A_{k}\cap A_{l}|}$

• Így haladunk tovább, amíg el nem fogynak a metszetek.

A kételemű esetről általánosítható teljes indukcióval.

Alternatív alak

Az

${\displaystyle |X|=\sum _{\emptyset \not =I\subseteq \{1,\dotsc ,n\}}\left(-1\right)^{|I|+1}|A_{I}|}$

képlet írható úgy is, mint

${\displaystyle |X|=\sum _{{I\subseteq \{1,\dotsc ,n\},} \atop {|I|~{\text{páratlan}}}}|A_{I}|-\sum _{{\emptyset \not =I\subseteq \{1,\dotsc ,n\},} \atop {|I|~{\text{páros}}}}|A_{I}|}$

hiszen a páratlan elemszámú metszeteket hozzáadjuk, a páros számúakat kivonjuk.

Alkalmazása

Poincaré és Sylvester szitaformulája a valószínűségekre alkalmazza a képletet:

Legyen ${\displaystyle (\Omega ,\Sigma ,P)}$ valószínűségi tér, és legyenek ${\displaystyle A_{i}}$ események benne. Ekkor

${\displaystyle P\left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k+1}\!\!\sum _{I\subseteq \{1,\dotsc ,n\}, \atop |I|=k}\!\!\!\!P\left(\bigcap _{i\in I}A_{i}\right)\right)}$

A mértékek additivitása miatt a bizonyítás egy az egyben átvihető a valószínűségszámításba. Például három eseményre

${\displaystyle {P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)}}$.

Általában is igaz véges mértékű halmazalgebrákra.

Példa

Szokás, hogy karácsony előtt egy-egy közösség úgy dönt, hogy véletlenszerűen döntik el, ki kit ajándékoz meg. Hogyha valakinek saját magát kellene megajándékoznia, akkor az elveszi az ő meglepetését. Kérdés, mekkora ennek a valószínűsége?

Matematikailag kifejezve a keresett esemény A := Legalább egy tagnak saját magát kell megajándékoznia. Ez ekvivalens az A_i := Az i-edik tagnak saját magát kell megajándékoznia események uniójával, ahol ${\displaystyle i\in \{1,\dotsc ,n\}}$, ahol n a részt vevők száma. A szitaformulával

${\displaystyle P\left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k+1}\!\!\sum _{I\subseteq \{1,\dotsc ,n\}, \atop |I|=k}\!\!\!\!P\left(\bigcap _{i\in I}A_{i}\right)\right)}$

Mivel az azonos méretű metszethalmazok valószínűsége egyenlő, ez a következő alakra egyszerűsíthető:

${\displaystyle {nP(A_{1})-{\binom {n}{2}}P(A_{1}\cap A_{2})+{\binom {n}{3}}P(A_{1}\cap A_{2}\cap A_{3})-{\binom {n}{4}}P(A_{1}\cap A_{2}\cap A_{3}\cap A_{4})}}$

${\displaystyle {+{\binom {n}{5}}P(A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\cap A_{5})-\dotsb +\dotsb +(-1)^{n+1}P(A_{1}\cap \dotsb \cap A_{n})}}$,

Annak a valószínűsége, hogy ${\displaystyle k}$ adott tag a saját ajándékát kapja:

${\displaystyle P(A_{1}\cap A_{2}\cap A_{3}\cap \dotsb \cap A_{k})={\frac {1}{n\cdot (n-1)\cdot (n-2)\cdot \dotsm \cdot (n-k+1)}}}$.

A binomiális együtthatók definíciója alapján

${\displaystyle {P(A_{1}\cup \dotsb \cup A_{n})=n\cdot {\frac {1}{n}}-{\frac {n(n-1)}{1\cdot 2}}\cdot {\frac {1}{n(n-1)}}+{\frac {n(n-1)(n-2)}{1\cdot 2\cdot 3}}\cdot {\frac {1}{n(n-1)(n-2)}}}}$

${\displaystyle {-{\frac {n(n-1)(n-2)(n-3)}{1\cdot 2\cdot 3\cdot 4}}\cdot {\frac {1}{n(n-1)(n-2)(n-3)}}+{\frac {n(n-1)(n-2)(n-3)(n-4)}{1\cdot 2\cdot 3\cdot 4\cdot 5}}\cdot {\frac {1}{n(n-1)(n-2)(n-3)(n-4)}}}}$

${\displaystyle {-\dotsb +\dotsb -\dotsb +\dotsb +(-1)^{n+1}\cdot {\frac {1}{1\cdot 2\cdot 3\cdot \dotsm \cdot n}}}}$.

Egyszerűsítve

${\displaystyle {P(A_{1}\cup \dotsb \cup A_{n})=1-{\frac {1}{1\cdot 2}}+{\frac {1}{1\cdot 2\cdot 3}}-{\frac {1}{1\cdot 2\cdot 3\cdot 4}}+{\frac {1}{1\cdot 2\cdot 3\cdot 4\cdot 5}}-\dotsb +\dotsb -\dotsb +\dotsb +(-1)^{n+1}\cdot {\frac {1}{1\cdot 2\cdot 3\cdot \dotsm \cdot n}}}}$.

Rövidebben

${\displaystyle P(A_{1}\cup \dotsb \cup A_{n})=1-\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$

Nagy csoportok esetén az ${\displaystyle k!}$ faktoriális nagyonm nagy, és a tagok száma is nagyon megnő. Ekkor célravezető az ${\displaystyle n\to \infty }$ határértéket felhasználni:

${\displaystyle \lim _{n\to \infty }\left(1-\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\right)=1-\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}=1-e^{-1}=1-{\frac {1}{e}}\approx 63{,}2\,\%}$

A sorfejtésben a természetes exponenciális függvény ${\displaystyle 0}$ körüli Taylor-sorát ismerhetjük fel a ${\displaystyle x=-1}$ helyen. A határérték ${\displaystyle 1-{\frac {1}{e}}}$, ami azt jelenti, hogy nagy csoportokban körülbelül ${\displaystyle 63{,}2\,\%}$ annak az esélye, hogy legalább egyvalaki a saját ajándékát kapja.^[1][2]

Források

• Norbert Henze: Stochastik für Einsteiger. Eine Einführung in die faszinierende Welt des Zufalls. Springer Spektrum, 10. Auflage, Wiesbaden 2016, S. 70–76.
• Klaus Dohmen: Improved Bonferroni Inequalities via Abstract Tubes – Inequalities and Identities of Inclusion-Exclusion Type. Springer-Verlag, 2003, ISBN 3-540-20025-8.
• Stasys Jukna: Extremal Combinatorics. Springer, Mai 2001, ISBN 3-540-66313-4.

Fordítás

Ez a szócikk részben vagy egészben a Prinzip von Inklusion und Exklusion című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.