24. tétel

Kombinatorika. A valószínűség kiszámításának kombinatorikus modellje.

Kombintorika

Def.: n különböző elem egy lehetséges sorrendjét permutációnak nevezzük.

n különböző elem permutációinak száma: P_n = n!

pl.: Hányféle sorrendben léphet be az ajtón 5 ember? (Válasz: 5! = 120)

Def.: n elem lehetséges sorrendjét, amikor vannak egyforma elemek is, ismétléses permutációnak nevezzük.                                                

 (k, l, m: az egyforma elemek száma)

pl.: Hányféleképpen állítható sorba 4 db piros, 3 db kék és 2 db zöld golyó? (Válasz: )

Def.: Variációnak nevezzük, amikor n különböző elemből kiválasztunk k darabot úgy, hogy számít a sorrend.

pl.: Egy fagyizóban 12-féle fagyit árulnak. Hányféle 5 gombócos tölcséres fagyi van? (Egyféléből csak egy gombócot veszünk.) (Válasz: )

Def.: Ismétléses variációnak nevezzük, amikor n különböző elemből kiválasztunk k darabot úgy, hogy 1-1 elem többször is szerepelhet és számít a sorrend.

V_n^k (ism.) = n^k

pl.: Hányféle 5 hosszúságú „fej vagy írás” sorozat van? (Válasz: 2⁵ = 32)

pl.: Egy fagyizóban 12-féle fagyit árulnak. Hányféle 5 gombócos tölcséres fagyi van? (Egyféléből többet is vehetünk.) (Válasz: )

Def.: Kombinációnak nevezzük, amkor n különböző elemből kiválasztunk k darabot úgy, hogy a sorrend nem számít.

pl: Hányféle lottóötös van (5 a 90-ből)? (Válasz: )

pl.: Egy fagyizóban 12-féle fagyit árulnak. Hányféle 5 gombócos kelyhes fagyi van? (Egyféléből csak egy gombócot veszünk.) (Válasz: )

Def.: Ismétléses kombinációnak nevezzük, amikor n különböző elemből kiválasztunk k darabot úgy, hogy a sorrend nem számít és 1 elemet többször is kiválaszthatunk

pl: Egy fagyizóban 12-féle fagyit árulnak. Hányféle 5 gombócos kelyhes fagyi van? (Egyféléből többet is vehetünk.) (Válasz: )

A binomiális tétel:

Pascal-háromszög: A Pascal-háromszög egy kiválasztási táblázat, a segítségével megmondhatjuk, hogy például hányféleképpen lehet n darab elemből k darabot kiválasztani: n-dik sor k-adik eleme.  

0.                                      1

1.                          1    1

2.                       1    2    1

3.                    1    3    3    1

.

.

n.   …… 

1. Tétel:

Bizonyítás:

- bal oldal:

-jobb oldal:  

2. Tétel: A Pascal háromszög n-edik sorában lévő számok összege 2ⁿ. (Azaz: )

1. Bizonyítás:

Binomiális tétellel:

2. Bizonyítás:

Mindkét oldalon az n elemű halmaz részhalmazainak száma van feltüntetve.

- bal oldal: 0-elemű részhalmazok száma + 1-elemű részhalmazok száma + ... + n-elemű részhalmazok száma = összes részhalmaz száma

- jobb oldal: részhalmazok száma az ismert tétel szerint

(Segédtétel: n elemű halmaz részhalmazainak száma:2ⁿ.

Megjegyzés: a segédtétel bizonyítását az 1. tételben találod meg.)

A valószínűség kiszámításának kombinatorikus modellje

- az W eseménytér elemei egyformán valószínű elemi események

- klasszikus valószínűségszámítási modell: Az A esemény valószínűsége:
 
 

Megjegyzés: A tört számlálója és nevezője egyaránt kiszámítható a kombinatorika segítségével.

pl.: Mekkora a valószínűsége annak, hogy 3 fejet és 7 írást dobunk 10 dobásból?

(Válasz:            jó esetek:  à kombináció, ismétléses permutáció
  

összes eset: 2¹⁰ à ismétléses variáció

)
 

Visszatevéses mintavétel (binomiális eloszlás)

Egy kísérletben a „siker” valószínűsége p, a „kudarc” valószínűsége (1 - p). Annak a valószínűsége, hogy n-szer elvégezve a kísérletet k db siker következik be: .

Visszatevés nélküli mintavétel (hipergeometrikus eloszlás)

N golyóból M fekete N - M fehér, n-et kihúzunk. Annak a valószínűsége, hogy m fekete lesz: .

Ha N nagyon nagy és n hozzá képest elhanyagolható nagyságú, akkor a hipergeometrikus eloszlás nagy pontosággal közelíthető a binomiális eloszlással is (pl magyar lakosságból kiválasztok 10 embert és őket vizsgálom)

Alkalmazások

·         szerencsejátékok (rulett, kártyajátékok, póker, stb), nyereményjátékok (totó, lottó, stb.) esetén használható a kombinatorika, illetve a valószínűségszámítás (Ezt részletesen kifejtve, példát mutatva nem kell további alkalmazást említeni!)

·         időjárás jelentésben, természeti katasztrófák előrejelzésében is nagyon jelentős szerepet játszik a valószínűségszámítás (pl: földrengések prognózisában - a föld mozgásait a korábbi tapasztalatok alapján következtetik ki)

·         természettudományokban (statisztikus fizika)

·         közgazdaságtan (operációkutatás)

·         kísérlettervezés, -optimalizálás

·         programozásban, számítógépek fejlesztésében - követelménye: a program minden lehetséges esetben működjön

·         kódmegfejtéskor is használják a kombinatorikát; az összes variáció segítségével található meg a helyes kombináció - számítástudomány

·         a kombinatorika igen fontos lehet egy sakkozó számára, hogy  felmérje az összes kombinációs lehetőséget és így ezek közül kiválasztva mindig a legjobb lépést lépje meg

·         sportversenyek, sportrendezvények megszervezése esetén is hasznunkra válhat a kombinatorika (pl: bajnokság, csapatok kialakításakor)