24. Tétel

A kombinatorika ezen ága a véges halmazok elemeinek sorbarendezésével és kiválasztásával foglalkozik. A két legfontosabb fogalom a permutáció (összes elem sorbarendezése) és a variáció (adott számú elem kiválasztása és sorbarendezése).

• Ismétlés nélküli permutáció: $n$ darab különböző elem egy lehetséges sorrendje. Az összes lehetséges sorrend számát $P_n$-nel jelöljük. Képlete: $$P_n = n! = n \cdot (n-1) \cdot ... \cdot 2 \cdot 1$$
• Ismétléses permutáció: Ha az $n$ elem között vannak egyformák (pl. $k_1$ db egyforma, $k_2$ db egyforma, ..., $k_r$ db egyforma, ahol $\sum k_i = n$), akkor a lehetséges különböző sorrendek száma: $$P_{n}^{k_1, k_2, ..., k_r} = \frac{n!}{k_1! \cdot k_2! \cdot ... \cdot k_r!}$$
• Ismétlés nélküli variáció: $n$ darab különböző elemből kiválasztunk $k$ darabot ($k \le n$), és ezeket sorba rendezzük. Ennek lehetséges száma: $$V_{n}^{k} = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)$$
• Ismétléses variáció: $n$ darab különböző elemből kiválasztunk $k$ darabot úgy, hogy egy elemet többször is választhatunk, és a sorrend számít. Ekkor a lehetőségek száma: $$V_{n}^{k, ism} = n^k$$

A binomiális eloszlás a valószínűségszámítás egyik legfontosabb diszkrét eloszlása. Olyan eseteket ír le, ahol egy kísérletet (ún. Bernoulli-kísérletet) egymástól függetlenül $n$-szer megismételünk, és mindegyik kísérletnek pontosan két kimenetele lehet: "siker" (valószínűsége $p$) vagy "kudarc" (valószínűsége $q = 1-p$). Ez a modell megfelel a visszatevéses mintavételnek.

Definíció: Legyen $X$ az a valószínűségi változó, amely megadja, hogy az $n$ független kísérlet során hányszor következik be a "siker". Ekkor az annak valószínűsége, hogy pontosan $k$-szor lesz sikeres a kísérlet ($0 \le k \le n$):

$$P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}$$

A képlet levezetése (gondolatmenet):

• Egy konkrét sorozat, amelyben pontosan $k$ siker és $(n-k)$ kudarc van, valószínűsége az események függetlensége miatt: $p \cdot p \cdot ... \cdot p \cdot q \cdot q \cdot ... \cdot q = p^k \cdot q^{n-k}$.
• Azonban a $k$ siker az $n$ kísérlet során bárhol bekövetkezhet. Annak a száma, hogy az $n$ helyből kiválasztjuk azt a $k$-t, ahol a siker bekövetkezik, éppen az ismétlés nélküli kombináció: $\binom{n}{k}$.
• Mivel ezek a különböző sorrendű kimenetelek egymást kizáró események, valószínűségeiket összeadjuk, így kapjuk a fenti szorzatot.

A binomiális eloszlás jellemzői: A binomiális eloszlású $X$ valószínűségi változó várható értéke $E(X) = n \cdot p$, szórása pedig $D(X) = \sqrt{n \cdot p \cdot (1-p)}$. Ezt az eloszlást gyakran a binomiális tétellel hozzák kapcsolatba, mivel az eloszlás tagjainak összege pontosan $(p + (1-p))^n = 1^n = 1$.

A klasszikus valószínűségi modell (Laplace-modell) csak véges sok, egyenlő valószínűségű elemi esemény esetén használható ($P = \frac{\text{kedvező}}{\text{összes}}$). Ha azonban a lehetséges kimenetelek száma végtelen (kontinuum), de a kimenetelek továbbra is "egyenletesen" oszlanak el egy adott tartományban, a geometriai valószínűségi modellt alkalmazzuk.

Definíció: Tegyük fel, hogy egy kísérlet minden lehetséges kimenetelének halmaza (az eseménytér) reprezentálható egy $\Omega$ geometriai alakzattal (egyenes szakasz, síkidom vagy térbeli test), amelynek mértéke (hossza, területe, vagy térfogata) $m(\Omega) < \infty$. Ha a kimenetelek egyenletesen oszlanak el $\Omega$-ban, akkor egy $A \subseteq \Omega$ esemény valószínűsége arányos az $A$-t reprezentáló alakzat mértékével:

$$P(A) = \frac{m(A)}{m(\Omega)}$$

ahol $m(A)$ az $A$ eseménynek megfelelő tartomány mértéke, $m(\Omega)$ pedig az eseménytér teljes mértéke.

A geometriai modell tulajdonságai:

• A valószínűség értéke itt is mindig $0 \le P(A) \le 1$.
• Bármely egyetlen, konkrét pont kiválasztásának valószínűsége pontosan $0$, hiszen egy pont kiterjedése (mértéke) nulla. (Ennek ellenére a kísérlet kimenetele mindig valamilyen konkrét pont lesz. Ez rámutat a "lehetetlen esemény" és a "nulla valószínűségű esemény" közti különbségre végtelen halmazok esetén).

A tétel maximális pontszámának eléréséhez az emelt szintű szóbeli vizsgán szükséges a témakör gyakorlati és történelmi vonatkozásainak ismerete is.

Matematikatörténeti vonatkozások:

• Jakob Bernoulli (1654–1705): A posztumusz megjelent Ars Conjectandi (A feltételezés művészete) című művében alapozta meg a valószínűségszámítást. Ő formalizálta a független kísérleteket (Bernoulli-kísérlet) és bizonyította be a nagyok törvényének egy korai formáját.
• Georges-Louis Leclerc, Comte de Buffon (1707–1788): A geometriai valószínűség leghíresebb korai példája a Buffon-féle tűprobléma (1777). Ha egy $l$ hosszúságú tűt leejtünk egy vonalazott papírra (ahol a párhuzamos vonalak távolsága $d \ge l$), annak valószínűsége, hogy a tű metsz egy vonalat: $P = \frac{2l}{\pi d}$. Ezzel a kísérlettel statisztikai úton közelíthető a $\pi$ értéke.

Gyakorlati alkalmazások:

• Binomiális eloszlás a minőség-ellenőrzésben: Gyárakban a termékek selejtarányának vizsgálatakor. Ha egy gépsor ismert $p$ valószínűséggel gyárt hibás terméket, a binomiális eloszlás segítségével meghatározható, mennyi az esélye annak, hogy egy $n$ darabos véletlenszerű mintában egy bizonyos számnál több hibás termék található.
• Geometriai valószínűség - Találkozási problémák: Két ember megbeszéli, hogy 12:00 és 13:00 között találkoznak. Mindketten véletlenszerűen érkeznek a megadott órán belül, és legfeljebb 15 percet várnak a másikra. Annak az esélyét, hogy találkoznak, egy $60 \times 60$-as négyzetben (koordináta-rendszerben) felrajzolt sáv területének és a teljes négyzet területének aránya adja meg. Ez az operációkutatás és a hálózati csomagütközések elemzésének alapja.
• Variációk az informatikában: Jelszavak, PIN-kódok és hálózati IP-címek számának meghatározása. Egy 4 jegyű PIN-kód ismétléses variációk számítása ($10^4 = 10000$ lehetőség), ami megadja a rendszer biztonsági fokát a "brute force" (nyers erő) támadásokkal szemben.