Kombinációk

Kombinációt akkor használunk, ha egy objektumhalmazból meghatározott számú objektumot választunk ki, és nem számít, milyen sorrendben választjuk ki őket. Tipikus feladat a Hatoslottó: az urnában 45 szám van, ebből húzunk 6-ot, és mindegy, milyen sorrendben húzzuk ki őket.

A képlet levezetése

Szerencsekerék

Legyen adott egy M halmaz, például M = {a, b, c, d, e}. Ekkor a k tagú kombináció olyan K ⊆ M részhalmaz, amelynek pontosan k eleme van. Mivel a K halmaz, a sorrend természetesen nem számít. Az M halmaz háromtagú kombinációja lehet tehát például {a, b, d} vagy {b, c, d}.

A variációkhoz képest a különbség az, hogy ott számított a sorrend, így az (a; b; e) és az (e; b; a) különböző variációk, de ugyanazok a kombinációk, mert az (a; b; e) és az (e; b; a) is ugyanazokat az elemeket tartalmazza; az, hogy más sorrendben vannak, a kombinációknál nem érdekel minket.

A variációkat azonban felhasználhatjuk, hogy megkapjuk a különböző kombinációk számának képletét. Tudjuk, hogy az n elemű halmaz k tagú variációinak száma pontosan

$V_{n}^{k} = \frac{n!}{(n - k)!} .$

Ha tehát megszámolnánk az előbbi M = {a, b, c, d, e} halmaz háromtagú variációit, $V_{5}^{3} = 60$ különböző variációt kapnánk. Csakhogy minden hármasnál ott lenne az összes permutációja is. Vagyis ott lenne az abc hármas, de az acb, bac, bca, cab és cba is. Ez hat különböző variáció, de egyetlen kombináció, mert mindegyikben ugyanazok az elemek vannak.

Ha tehát van egy hármasunk, hány különböző permutációja létezik? Pontosan 3!. Más szóval pontosan 3!-szor több háromtagú variáció van, mint háromtagú kombináció. Ahelyett, hogy egy kombinációval számolnánk, 3!-szor több variációval számolunk, a hármas minden permutációjával. Ha tehát a variációk számát elosztjuk 3!-sal, megkapjuk a kombinációk számát.

Az előző eljárást általánosíthatjuk, és kimondhatjuk, hogy ha az n elemű halmaz összes különböző k tagú kombinációjának számát keressük, akkor ez a szám, jelöljük $C_{n}^{k}$ -val, egyenlő

$C_{n}^{k} = \frac{V_{n}^{k}}{k!},$

vagyis a variációk száma osztva k!-sal, ami minden k-as permutációinak a száma. A képletet átalakíthatjuk a variációk képletének kifejtésével:

$C_{n}^{k} = \frac{V_{n}^{k}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Példa: az {a, b, c} halmaz kéttagú kombinációinak száma

$C_{3}^{2} = \frac{3!}{1! \cdot 2!} = 3$

és ezek a kombinációk: {a, b}, {a, c} és {b, c}. Az eredeti M = {a, b, c, d, e} halmaz háromtagú kombinációiból

$C_{5}^{3} = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

darab van, és ezek a kombinációk: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Binomiális együttható

A $C_{n}^{k}$ jelölést a gyakorlatban ritkán használják, helyette az úgynevezett binomiális együtthatót. A binomiális együttható alakja

$(\binom{n}{k})$

ez afféle tört törtvonal nélkül (amelyet megszokásból úgyis odaírsz), de zárójelekkel (ezek nem elhagyhatók, ott kell lenniük). A binomiális együtthatót így olvassuk: „n alatt a k”. Az értéke megegyezik a $C_{n}^{k}$ értékével.

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Ha tehát van egy 5 elemű halmazunk, és négyeseket választunk ki belőle, azok száma

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Alapvető összefüggések

A binomiális együtthatóra és az n ∈ ℕ számra érvényes:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Továbbá n, k ∈ ℕ és k ≤ n esetén

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

És n, k ∈ ℕ és k < n esetén

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Számológép

Az alábbi számológép kiszámítja az n alatti k binomiális együtthatót.

Megoldott példák

Kezdjük a már említett Hatoslottóval. Ebben egy 45 golyót tartalmazó urnából összesen 6 golyót húznak ki. Hány különböző kihúzás lehetséges?

Először is, számít-e a számok húzásának sorrendje? Nem számít, csak a számokra tippelünk, a sorrendjükre nem. Kombinációkat fogunk használni. Összesen 45 golyónk van, 6 golyót húzunk, így a következő binomiális együtthatót kapjuk:

$(\binom{45}{6}) = \frac{45!}{(45 - 6)! \cdot 6!} = \frac{45!}{39! \cdot 6!} = 8 145 060$

Összesen 8 145 060 különböző kihúzás lehetséges. Ez egyébként azt jelenti, hogy egyetlen szelvénnyel a főnyeremény valószínűsége 1/8 145 060, vagyis 0,0000122774%.
Pisti, a híres szívtipró, éppen egy falusi bálban van, ahol összesen 13 szép lány van, akik érdeklik. Pisti tudja, hogy egy este alatt 4 különböző lánnyal tud táncolni. Hány különböző négyes közül választhat Pisti?

Ez megint egyszerű kombinációs példa, a sorrend nem számít, Pisti az első lánnyal ugyanolyan jó táncos lesz, mint az utolsóval. Van tehát egy 13 lányból álló halmazunk, amelyből mindig 4 lányt választunk. Ez a következő binomiális együtthatóhoz vezet:

$(\binom{13}{4}) = 715.$
Van egy ötven fős csoport – a fele férfi, a fele nő. Hány különböző hármas létezik, ha a tagjai nem lehetnek mind azonos neműek (vagyis a hármasban nem lehet három férfi vagy három nő)?

Ez már egy kicsit bonyolultabb kombináció. Ha kizárjuk az egynemű hármasokat, csak két lehetőség marad a hármas összetételére – két férfi és egy nő, vagy egy férfi és két nő –, és az első csoport (két férfi és egy nő) kombinációinak száma ugyanannyi, mint a másodiké. Elég tehát az első csoport kombinációinak számát kiszámolni, és megszorozni kettővel. Innen már megint gyerekjáték. Meghatározzuk, hányféleképpen választhatunk ki két férfit, ami huszonöt alatt a kettő, és megszorozzuk az egy nő kiválasztásának lehetőségeivel (ez huszonöt, lásd a fenti alapvető összefüggéseket, konkrétan a második sort). Ezt az eredményt már csak megszorozzuk kettővel, és megvan a végeredmény.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
Egy dobozban 15 termék van, közülük 4 hibás. Hányféleképpen lehet kiválasztani 6 terméket úgy,
- hogy egyik se legyen hibás? Ilyenkor 6 terméket választunk a 15 − 4 = 11 nem hibás termékből. Így a következő binomiális együtthatót kapjuk:
  
  $(\binom{11}{6}) = 462.$
- hogy pontosan egy termék legyen hibás? Olyan halmazt választunk, amely 5 hibátlan és 1 hibás terméket tartalmaz. Hibátlan termékből összesen 11 van, hibásból 4. Alkalmazzuk a kombinatorikai szorzatszabályt, és megkapjuk az eredményt:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- hogy legfeljebb egy legyen hibás? A megoldáshoz felhasználjuk az előző eredményeket. Tudjuk, hogy 462 lehetőségünk van pontosan 6 hibátlan termék kiválasztására, és 1848 lehetőségünk van öt hibátlan és egy hibás termék kiválasztására. Alkalmazzuk tehát a kombinatorikai összegszabályt, ezeket az eredményeket összeadjuk, és megkapjuk a keresett eredményt, vagyis a legfeljebb egy hibás termék esetét (= vagy egyetlen hibás sincs, vagy pontosan egy van). Az eredmény tehát: 462 + 1848 = 2310.

Fejezetek: Kombinatorika, Variációk, Permutációk, Kombinációk, Ismétléses variációk, Ismétléses kombináció, Hányféle PIN-kód létezik?

« Előző: Permutációk

Következő: Ismétléses variációk »