Szitaformula

kombinatorikai leszámlálási technika

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ásSzerkesztés

 
A szitaformula három halmazra

Ismert, hogy ha   és   véges halmazok, akkor

 

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

A módszert kétszer alkalmazva

 

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

 
  • Első közelítésként az összes halmaz elemszámát beleszámoltuk. Ez egy felső becslés.
 
  • 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.
 
  • 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.
 
  • 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.
 
  • Így haladunk tovább, amíg el nem fogynak a metszetek.

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

Alternatív alakSzerkesztés

Az

 

képlet írható úgy is, mint

 

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

AlkalmazásaSzerkesztés

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

Legyen   valószínűségi tér, és legyenek   események benne. Ekkor

 

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

 .

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

PéldaSzerkesztés

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 Ai := Az i-edik tagnak saját magát kell megajándékoznia események uniójával, ahol  , ahol n a részt vevők száma. A szitaformulával

 

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

 
 ,

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

 .

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

 
 
 .

Egyszerűsítve

 .

Rövidebben

 

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

 

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

ForrásokSzerkesztés

  1. Norbert Henze: Stochastik für Einsteiger. Eine Einführung in die faszinierende Welt des Zufalls. Springer Spektrum, 1. Auflage, Wiesbaden 1997, 74–77. o.
  2. Stefan Bartz. Selbst-Bewichtelungen in 2 von 3 Spielen (2013) 
  • 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ásSzerkeszté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.