Kombinácia (kombinatorika)

**Kombinácia**, presnejšie **kombinácia ''k - tej'' triedy z ''n'' prvkov [[množina|množiny]] M** je ľubovoľná *k*-prvková podmnožina *n*-prvkovej množiny *M*. Počet všetkých kombinácií *k*-tej triedy sa teda často využíva pri riešení úloh, kde je potrebné zistiť, koľkými spôsobmi možno vybrať spomedzi *n* prvkov skupinu *k* prvkov, pričom nezáleží na poradí výberu.
 
Takto definované kombinácie sa niekedy tiež označujú ako **kombinácie bez opakovania**, keďže koncept množiny a podmnožiny neumožňuje zachytiť fenomén opakovania prvkov. Existujú však aj **kombinácie s opakovaním,** ktorých počet je počet možností, ako vybrať *k* prvkov spomedzi *n* tak, že sa môžu aj opakovať.

## Kombinácie bez opakovania
### Definícia
Kombinácie bez opakovania *k*-tej triedy z *n* prvkov množiny *M* je ľubovoľná *k*-prvková podmnožina množiny *M*. Z toho vyplýva, že množinu všetkých kombinácií *k*-tej triedy z množiny M definujeme ako podmnožinu potenčnej množiny množiny *M* (označujeme *P(M)*) takú, že obsahuje práve všetky *k*-prvkové množiny patriace do tejto potenčnej množiny. Takúto podmnožinu označujeme P_k(M). Platí teda, že množina všetkých kombinácií bez opakovania *k*-tej triedy z množiny *M* je definovaná ako:
:{M \choose k} = P_k(M)

### Počet kombinácií bez opakovania
Aj keď uvedená definícia korektne definuje kombinácie bez opakovania ako kombinatorické štruktúry, nedáva ešte žiadnu informáciu o ich počte. Preto vzorec poskytujúci túto informáciu treba dokázať ako samostatnú vetu.

Ak definujeme symbol
:{n \choose k} =  = {n!\over k!(n-k)!},
(tento symbol nazývame kombinačné číslo, alebo, pre súvis s binomickou vetou aj binomický koeficient) tak potom pre počet všetkých kombinácií *k*-tej triedy z *n* prvkov množiny *M* platí:
:C_k(n) = \left|{M \choose k}\right| = {|M| \choose k} = {n \choose k}. 

Táto veta sa dokazuje s pomocou vety o počte variácií bez opakovania *k*-tej triedy z *n* prvkov množiny *M*. Pri dôkaze sa využíva fakt, že počet kombinácií bez opakovania je rovnaký ako počet tried ekvivalencie na množine všetkých variácií, kde dve variácie sú spolu v jednej triede práve vtedy, keď je obraz obi dvoch (variácia je špeciálny druh zobrazenia) rovnaká množina a fakt, že počet variácií v jednej takejto triede ekvivalencie je *k!*.

### Príklad
V spoločnosti 5 osôb (a, b, c, d, e) každá osoba podá každej osobe ruku. Koľko bude podaní rúk?
Riešenie: C_2(5) = \frac{5!}{(5 - 2)! \cdot 2!} = 10
* dvojice, ktoré si podajú ruky: ab, ac, ad, ae, bc, bd, be, cd, ce, de

## Kombinácie s opakovaním
### Definícia
Kombinácie s opakovaním *k*-tej triedy z *n* prvkov množiny *M* definujeme ako triedy ekvivalencie na množine všetkých variácií s opakovaním, kde dve variácie s opakovaním sú v relácii ekvivalencie práve vtedy, ak sa na každý prvok množiny *M* zobrazí v oboch variáciách rovnaký počet prvkov, t. j. ak pre variácie *f*, *g* platí:
: \forall x \in M: |f^{-1}(x)| = |g^{-1}(x)|.

Alternatívne definície využívajú napr. pojem multimnožiny.

### Počet kombinácií s opakovaním
Počet všetkých kombinácií s opakovaním *k*-tej triedy z *n* prvkov množiny *M* je:
: C_k^{\prime}(n) = {{(n + k - 1)} \choose k}
alebo
: C_k^{\prime}(n) = \frac{(n + k - 1)!}{(n - 1)! \cdot k!}

### Príklad
Koľko rôznych súčinov dvoch činiteľov možno utvoriť z čísel 2, 3, 5, 7, 11?
Riešenie: C_2^{\prime}(5) = \frac{(5 + 2 - 1)!}{(5 - 1)! \cdot 2!} = 15
* hľadané dvojice: 15

## Pozri aj
* Kombinatorika
* Binomická veta
* Permutácia (kombinatorika)
* Variácia (kombinatorika)
* Faktoriál

## Použitá literatúra
* Jiří Matoušek, Jaroslav Nešetřil: *Kapitoly z diskrétní matematiky*, Karolinum, 2007
* Martin Knor: *Kombinatorika a teória grafov I*, Univerzita Komenského v Bratislave, 2000
* Marián Olejár a kol.: *Zbierka vzorcov z matematiky*, Vydavateľstvo Young Scientist

Kombinácia