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 \cdots \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 \cdots \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|\ge \sum _{1\le i\le n}|A_i|-\sum _{1\le i<j\le 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|\le \sum _{1\le i\le n}|A_i|-\sum _{1\le i<j\le n}|A_i\cap A_j|+\sum _{1\le i<j<k\le 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|\ge \sum _{1\le i\le n}|A_i|-\sum _{1\le i<j\le n}|A_i\cap A_j|+\sum _{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\sum _{1\le i<j<k<l\le 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 _{\mathrm{\varnothing }=I\subseteq \{1,\dots ,n\}}{(-1)}^{|I|+1}|A_I|$

képlet írható úgy is, mint

$|X|=\sum _{\genfrac{}{}{0ex}{}{I\subseteq \{1,\dots ,n\},}{|I|\text{páratlan}}}|A_I|-\sum _{\genfrac{}{}{0ex}{}{\mathrm{\varnothing }=I\subseteq \{1,\dots ,n\},}{|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 $(\mathrm{\Omega },\mathrm{\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((-1{)}^{k+1}\sum _{\genfrac{}{}{0ex}{}{I\subseteq \{1,\dots ,n\},}{|I|=k}}P\left(\bigcap _{i\in I}{A}_i\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,\dots ,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((-1{)}^{k+1}\sum _{\genfrac{}{}{0ex}{}{I\subseteq \{1,\dots ,n\},}{|I|=k}}P\left(\bigcap _{i\in I}{A}_i\right))$

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

$nP(A_1)-(\genfrac{}{}{0ex}{}{n}{2})P(A_1\cap A_2)+(\genfrac{}{}{0ex}{}{n}{3})P(A_1\cap A_2\cap A_3)-(\genfrac{}{}{0ex}{}{n}{4})P(A_1\cap A_2\cap A_3\cap A_4)$

$+(\genfrac{}{}{0ex}{}{n}{5})P(A_1\cap A_2\cap A_3\cap A_4\cap A_5)-\cdots +\cdots +(-1{)}^{n+1}P(A_1\cap \cdots \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 \cdots \cap A_k)=\frac{1}{n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot (n-k+1)}$.

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

$P(A_1\cup \cdots \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)}$

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

Egyszerűsítve

$P(A_1\cup \cdots \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}-\cdots +\cdots -\cdots +\cdots +(-1{)}^{n+1}\cdot \frac{1}{1\cdot 2\cdot 3\cdot \cdots \cdot n}$.

Rövidebben

$P(A_1\cup \cdots \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 \mathrm{\infty }$ határértéket felhasználni:

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

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\mathrm{\%}$ 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, Sablon:ISBN.
• Stasys Jukna: Extremal Combinatorics. Springer, Mai 2001, Sablon:ISBN.