23. Tétel

Kombinációk. Binomiális tétel, a Pascal-háromszög. A valószínűség kiszámításának kombinatorikus modellje. A hipergeometrikus eloszlás.

Teljes és alapos kidolgozás az emelt szintű matematika érettségi szóbeli vizsgájára. Ez a tétel bemutatja a kiválasztási problémákat, a binomiális együtthatók tulajdonságait, a valószínűségszámítás klasszikus modelljét és a visszatevés nélküli mintavételt modellező hipergeometrikus eloszlást, a szükséges bizonyításokkal együtt.

Kombinációk

A kombinatorika egyik alapvető kérdése: hogyan választhatunk ki egy adott halmazból elemeket úgy, hogy a kiválasztás sorrendjére nem vagyunk tekintettel? Ezt nevezzük kombinációnak.

  • Ismétlés nélküli kombináció: Adott $n$ különböző elemből választunk ki $k$ darabot ($0 \le k \le n$) úgy, hogy egy elemet csak egyszer választhatunk, és a kiválasztás sorrendje nem számít. Az ilyen kiválasztások számát binomiális együtthatónak nevezzük, és $\binom{n}{k}$-val jelöljük (olvasd: "n alatt a k"). $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
  • Ismétléses kombináció (Emelt szint): Ha $n$ féle elemből választunk ki $k$ darabot úgy, hogy a sorrend nem számít, de egy elemet többször is választhatunk (akár $k$-szor is), ismétléses kombinációról beszélünk. Ennek száma megegyezik egy olyan ismétlés nélküli kombinációval, ahol a kiválasztandó elemek számát megnöveljük $n-1$ "elválasztó" elemmel: $$C_n^{k (ism)} = \binom{n+k-1}{k}$$

A Pascal-háromszög és a Binomiális tétel

A Pascal-háromszög a binomiális együtthatók háromszög alakú elrendezése. A nulladik sorban az $n=0$-hoz, az első sorban az $n=1$-hez tartozó együtthatók állnak, és így tovább. Minden sor szélén 1-esek állnak ($\binom{n}{0} = \binom{n}{n} = 1$), a belső elemek pedig a felettük lévő két elem összegeként állnak elő.

Alapvető összefüggések a háromszögben:

  1. Képzési szabály: $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$
  2. Szimmetria: $\binom{n}{k} = \binom{n}{n-k}$
  3. Sorok összege: Az $n$-edik sor elemeinek összege pontosan $2^n$ (ami egy $n$ elemű halmaz összes részhalmazának száma).
Tétel: A binomiális tétel

Minden $a, b \in \mathbb{R}$ és $n \in \mathbb{N}$ esetén érvényes az alábbi azonosság:

$$(a+b)^n = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + ... + \binom{n}{n}b^n$$

Zárt alakban felírva:

$$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k}b^k$$

Bizonyítás (Kombinatorikai okoskodással):

Írjuk fel az $(a+b)^n$ kifejezést $n$ darab azonos tényező szorzataként:

$$(a+b)^n = (a+b)(a+b)...(a+b)$$

A zárójelek felbontásakor (minden tagot szorozva minden taggal) olyan szorzatokat kapunk, amelyek pontosan $n$ tényezőből állnak. Minden egyes zárójelből vagy az $a$-t, vagy a $b$-t kell kiválasztanunk.

Egy adott $a^{n-k}b^k$ alakú tag pontosan akkor keletkezik, ha az $n$ darab zárójel közül pontosan $k$ darabból választjuk a $b$-t, a maradék $n-k$ darabból pedig az $a$-t.

Mivel $n$ zárójelből a $k$ darab $b$-t pontosan $\binom{n}{k}$-féleképpen választhatjuk ki (a sorrend nem számít), az $a^{n-k}b^k$ tag együtthatója a kifejtés után összevonva pontosan $\binom{n}{k}$ lesz. Ezzel a tételt beláttuk. Q.E.D.

A valószínűség kombinatorikus (Klasszikus) modellje

Ha egy véletlen kísérletnek véges számú, egymást páronként kizáró és egyenlően valószínű kimenetele van, akkor a klasszikus valószínűségi modellt (Laplace-modellt) alkalmazzuk.

Definíció: Legyen az elemi események tere $\Omega$, melynek elemszáma véges (jelöljük $n$-nel), és az elemi események egyformán valószínűek. Egy $A$ esemény valószínűsége:

$$P(A) = \frac{\text{kedvező esetek száma ($k$)}}{\text{összes eset száma ($n$)}}$$

Ennek a modellnek az alkalmazásakor a kombinatorika eszköztárát (permutációk, variációk, kombinációk) használjuk a "kedvező" és az "összes" eset számának meghatározására.

A hipergeometrikus eloszlás

A hipergeometrikus eloszlás a visszatevés nélküli mintavétel matematikai modellje. Tipikus példája a lottóhúzás vagy a minőségellenőrzés, ahol az alapsokaságból egy elemet csak egyszer választhatunk ki, és nem tesszük vissza.

A modell felépítése:

  • Van egy $N$ elemű halmazunk (az összes golyó).
  • Ebből $K$ darab elem rendelkezik egy adott tulajdonsággal (pl. piros golyók), $N-K$ pedig nem (pl. fehér golyók).
  • Visszatevés nélkül kihúzunk $n$ darab elemet ($n \le N$).
  • A valószínűségi változó, $X$, jelentse a kihúzott piros golyók számát.

Annak a valószínűsége, hogy pontosan $k$ darab piros golyót húzunk ($k \le K$ és $n-k \le N-K$):

$$P(X=k) = \frac{\binom{K}{k} \cdot \binom{N-K}{n-k}}{\binom{N}{n}}$$

A képlet magyarázata: Az összes esetek száma $\binom{N}{n}$, hiszen $N$ elemből $n$-et választunk kiválasztási sorrend nélkül. A kedvező esetek számát úgy kapjuk, hogy a $K$ darab pirosból kiválasztjuk a szükséges $k$ darabot ($\binom{K}{k}$ féleképpen), a maradék $N-K$ fehérből pedig a hiányzó $n-k$ darabot ($\binom{N-K}{n-k}$ féleképpen). A független választások miatt ezeket szorozzuk.

A hipergeometrikus eloszlás várható értéke:

$$E(X) = n \cdot \frac{K}{N}$$

Megjegyzés: Ha a húzások száma ($n$) eltörpül az alapsokaság méretéhez ($N$) képest, a hipergeometrikus eloszlás jól közelíthető a binomiális eloszlással ($p = \frac{K}{N}$ paraméterrel), mivel a visszatevés hiánya minimálisan módosítja csak az arányokat.

Alkalmazások és Matematikatörténet

Matematikatörténet:

  • A Pascal-háromszög: Bár Európában Blaise Pascal francia matematikus (1623-1662) tanulmányozta behatóan a Traité du triangle arithmétique című művében, az elrendezés sokkal régebbi. Indiában (Pingala, i.e. 2. század) és Kínában (Jia Xian, 11. század, illetve Yang Hui, 13. század) már évszázadokkal korábban ismerték. Perzsiában Omar Khajjám költő-matematikus is használta a binomiális együtthatók számítására.
  • Valószínűségszámítás kezdetei: A klasszikus valószínűségelmélet alapjait Pascal és Pierre de Fermat levélváltása fektette le 1654-ben, amikor egy félbeszakadt szerencsejáték tétjének igazságos elosztásán (a pont-problémán) vitatkoztak.

Gyakorlati alkalmazások:

  • Minőségellenőrzés (Hipergeometrikus eloszlás): A gyárakban a legyártott termékek (pl. chipek, csavarok) egy nagy $N$ elemszámú tételéből $n$ elemű mintát vesznek. Ha a mintában a hibás termékek száma meghalad egy kritikus $k$ értéket, az egész szállítmányt visszautasítják. Ennek valószínűségét hipergeometrikus eloszlással számítják ki.
  • Lottójátékok: Az ötöslottón a főnyeremény valószínűsége tipikus kombinatorikus probléma ($1 / \binom{90}{5}$), de a 2-es, 3-as vagy 4-es találat valószínűségét pontosan a hipergeometrikus eloszlás adja meg (pl. 3 találat: $P(X=3) = \frac{\binom{5}{3}\binom{85}{2}}{\binom{90}{5}}$).
  • Genetika: A populációgenetikában az allélok öröklődésének és a genotípusok gyakoriságának meghatározásánál (Hardy-Weinberg törvény) a binomiális tétel kap kulcsszerepet.