Szitaformula

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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[szerkesztés]

A szitaformula három halmazra

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

Itt már felismerhető az alapelv: felülről becsüli 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 alak[szerkeszté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ása[szerkeszté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élda[szerkeszté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ások[szerkeszté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ás[szerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.