Kombinácia (kombinatorika)

 
 

Kombinácia, presnejšie kombinácia k - tej triedy z n prvkov 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 spomedzin 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} = {{\prod_{i = n-k+1}^n i}\over{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ácii 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áciach 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