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

A szitaformula három halmazra

Ismert, hogy ha $A$ és $B$ véges halmazok, akkor

$|A\cup B|=|A|+|B|-|A\cap B|$

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

A módszert kétszer alkalmazva

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Általában, $n$ halmaz esetén a képlet

$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.

$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.

$|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.

$|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.

$|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

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

képlet írható úgy is, mint

$|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 $(\Omega ,\Sigma ,P)$ valószínűségi tér, és legyenek $A_{i}$ események benne. Ekkor

$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

${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 $i\in \{1,\dotsc ,n\}$, ahol n a részt vevők száma. A szitaformulával

$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ő:

${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})}$

${+{\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 $k$ adott tag a saját ajándékát kapja:

$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

${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)}}}$

${-{\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)}}}$

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

Egyszerűsítve

${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

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

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

$\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 $0$ körüli Taylor-sorát ismerhetjük fel a $x=-1$ helyen. A határérték $1-{\frac {1}{e}}$, ami azt jelenti, hogy nagy csoportokban körülbelül $63{,}2\,\%$ annak az esélye, hogy legalább egyvalaki a saját ajándékát kapja.

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.