Kombináció

A permutáció és a variáció mellett a kombinatorika harmadik fontos fogalma a kombináció. Az alábbiakban megnézzük, hogy mi az az ismétléses kombináció, mi az az ismétlés nélküli kombináció és mi a kettő között a különbség. A definíciók mellett pedig mindegyikre hoztunk több példát is.

Ismétlés nélküli kombináció

Legyen n egymástól különböző elemünk. Ha ezekből k (k \leq n) elemet kiválasztunk minden lehetséges módon úgy, hogy a kiválasztott elemek sorrendjére nem vagyunk tekintettel, akkor az n elem k-ad osztályú ismétlés nélküli kombinációját kapjuk. Jelölése: C_{n}^{k}.

Most már tudjuk, hogy pontosan mit is értünk ismétlés nélküli kombináción, azonban azt még nem láttuk, hogy hogyan lehet ezt kiszámolni. Ebben a következő tétel lesz segítségünkre:

Az n elem k-ad osztályú összes ismétlés nélküli kombinációjának száma n alatt a k:

C_{n}^{k} = \frac{n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)}{k \cdot (k-1) \cdot \ldots \cdot 2 \cdot 1} = \frac{n!}{k! \cdot (n-k)!} = \binom{n}{k}.

Most pedig nézzük meg néhány példán keresztül, hogyan tudjuk felhasználni a fent leírtakat.

Ismétlés nélküli kombináció segítségével megoldható feladatok

Feladat: Határozzuk meg, hogy hányféleképpen lehet kitölteni egy ötöslottó szelvényt!

Segítség: Az ötöslottó számok kiválasztásánál 90 számból kell kiválasztanunk 5 számot. A kiválasztás során a sorrend nem számít, de egy számot csak egyszer választhatunk, így ismétlés nélküli kombinációról beszélünk.

Megoldás: Esetünkben 90 szám közül kell kiválasztanunk 5 számot, vagyis n = 90 és k = 5. Tehát a C_{90}^{5}-t keressük. A képletbe behelyettesítve a megoldás:

C_{90}^{5} = \frac{90 \cdot 89 \cdot 88 \cdot \ldots \cdot 86}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{90!}{5! \cdot 85!} = \binom{90}{5}=43949268.

Nézzük most meg a következő feladatot.

Feladat: Egy ötfős társaságban mindenki kezet fog mindenkivel. Hány kézfogás történik összesen?

Segítség: A kézfogások száma megegyezik azzal, ahányféleképpen kiválaszthatunk 5 ember közül 2-t. Azaz 5 elem másodosztájú ismétlés nélküli kombinációjáról beszélünk.

Megoldás: n=5 és k=2. A képletbe behelyettesítve a megoldás:

C_{5}^{2} = \binom{5}{2} = \frac{5!}{2! \cdot 3!} = 10.

Ismétléses kombináció

Legyen n egymástól különböző elemünk. Ha ezekből k elemet kiválasztunk minden lehetséges módon úgy, hogy a kiválasztott elemek sorrendjére nem vagyunk tekintettel és ugyanazt az elemet többször is kiválaszthatjuk, akkor az n elem k-ad osztályú ismétléses kombinációját kapjuk. Jelölése: C_{n}^{k,i}.

Az ismétlés nélküli kombinációhoz hasonlóan ebben az esetben is a kiszámításra vonatkozó tétellel folytatjuk, majd pedig megnézünk egy feladatot.

Az n elem k-ad osztályú összes ismétléses kombinációjának száma n+k-1 alatt a k:

C_{n}^{k,i} = \frac{(n+k-1)!}{k! \cdot [(n+k-1)-k)]! } = \frac{(n+k-1)!}{k! \cdot (n-1)! } = \binom{n+k-1}{k}.

Ismétléses kombináció segítségével megoldható feladatok

Feladat: Egy 24 fős osztályban kisorsolunk 5 könyvet. Minden könyv egyforma és egy ember több könyvet is kaphat. Hányféleképpen tehetjük ezt meg?

Segítség: A feladatban 24 ember közül akarunk kiválasztani 5 embert úgy, hogy egy embert többször is választhatunk. A könyvek mind egyformák, vagyis ismétléses kombinációról van szó.

Megoldás: n= 24 és k=5. A megoldás így:

C_{24}^{5,i} = \frac{(24+5-1)!}{5! \cdot [(24+5-1)-5)]! } = \frac{(24+5-1)!}{5! \cdot (24-1)! } = \frac{28!}{5! \cdot 23!} = \binom{24+5-1}{5} = \binom{28}{5}=98280.