Kombinace

Kombinace využijeme, pokud z nějaké množiny objektů vybíráme určitý počet objektů, přičemž nezáleží na pořadí, v jakém tyto objekty vybíráme. Typickou úlohou je Sportka — v osudí máme 49 čísel a taháme z nich 6 čísel, přičemž je jedno, v jakém pořadí je vytáhneme.

Odvození vzorce

Mějme nějakou množinu M, například M = {a, b, c, d, e}. Potom k-členná kombinace je podmnožina K ⊆ M, která obsahuje právě k prvků. Protože je K množina, tak samozřejmě nezáleží na pořadí. Tedy tříčlenná kombinace z množiny M by mohla být {a, b, d} nebo {b, c, d}.

Rozdíl oproti variacím je, že u variací záleželo na pořadí, takže [a, b, e] a [e, b, a] jsou různé variace, ale jsou to stejné kombinace, protože [a, b, e] i [e, b, a] obsahují stejné prvky; že jsou v jiném pořadí nás u kombinací nezajímá.

Můžeme ale využít variace, abychom získali vzorec pro počet všech různých kombinací. Víme, že k-členných variací z množiny o n prvcích je právě

$$ V(k, n) = \frac{n!}{(n-k)!}. $$

Pokud bychom tak počítali počet všech tříčlenných variací z předchozí množiny M = {a, b, c, d, e}, získali bychom V(3, 5) = 60 různých variací. Nicméně bychom tam pro každou trojici měli i všechny její permutace. Tj. měli bychom tam trojici abc, ale i trojice acb, bac, bca, cab a cba. Toto je šest různých variací, ale je to jedna kombinace, protože mají všechny stejné prvky.

Pokud tak máme nějakou trojici, kolik různých permutací této trojice existuje? Právě 3!. Jinými slovy, existuje právě 3! vícekrát tříčlenných variací než tříčlenných kombinací. Místo toho, abychom počítali s jednou kombinací, tak počítáme s 3! více variacemi, s každou permutací dané trojice. Takže pokud počet permutací vydělíme 3!, získáme počet kombinací.

Předchozí postup můžeme zobecnit a můžeme říci, že pokud hledáme počet všech různých k-členných kombinací z množiny o velikosti n, pak je tento počet, označíme C(k, n) roven,

$$ C(k, n) = \frac{V(k, n)}{k!}, $$

tj. počet variací děleno k!, což je počet permutací každé k-tice. Vzorec můžeme upravit rozepsáním vzorce pro výpočet variací:

$$ C(k, n) = \frac{V(k, n)}{k!} = \frac{n!}{(n-k)!}\cdot\frac{1}{k!} = \frac{n!}{(n-k)!\cdot k!}. $$

Příklad: počet dvoučlenných kombinací z množiny {a, b, c} je

$$ C(2, 3) = \frac{3!}{1!\cdot2!} = 3 $$

a jsou to tyto kombinace: {a, b}, {a, c} a {b, c}. U tříčlenných kombinací z původní množiny M = {a, b, c, d, e} bychom dostali počet

$$ C(3, 5) = \frac{5!}{(5-3)!\cdot3!}=10 $$

a jsou to tyto kombinace: {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}.

Kombinační číslo

Předchozí zápis vzorce pomocí C(k, n) se příliš nepoužívá a místo něj se používá tzv. kombinační číslo. Kombinační číslo má tento tvar

$$ {n \choose k} $$

je to jakýsi zlomek bez zlomkové čáry (kterou tam stejně ze zvyku budete psát), ale se závorkami (ty nejsou volitelné, ty tam musí být). Kombinační číslo čteme jako „en nad ká“. Hodnota kombinačního čísla je pak stejná jako C(k, n).

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

Takže pokud máme množinu o 5 prvcích a vybíráme z ní čtveřice, tak jejich celkový počet bude

$$ {5 \choose 4} = \frac{5!}{1! \cdot 4!} = 5. $$

Základní vztahy

Pro kombinační číslo a n ∈ ℕ platí:

$$\begin{eqnarray} {n \choose 0} = {n \choose n} = {0 \choose 0} &=& 1\\ {n \choose 1} &=& n \end{eqnarray}$$

Dále pro n, k ∈ ℕ₀ a k ≤ n platí

$$\begin{eqnarray} {n \choose n - k} &=& {n \choose k}. \end{eqnarray}$$

A pro n, k ∈ ℕ₀ a k < n platí

$$\begin{eqnarray} {n \choose k} + {n \choose k+1} &=& {n+1 \choose k+1}. \end{eqnarray}$$

Počítačka

Následující počítačka vám vypočítá kombinační číslo n nad k, včetně postupu.

Řešené příklady

1. Začneme již zmíněnou Sportkou. V ní se tahá z osudí, ve kterém je 49 míčků, celkem 6 míčků. Kolik různých možností můžeme vylosovat?

   V prvé řadě — záleží na pořadí tažení čísel? Nezáleží, tipujeme pouze čísla, ne jejich pořadí. Budeme používat kombinace. Máme celkem 49 míčků, taháme 6 míčků, dostáváme kombinační číslo

   $$ {49 \choose 6} = \frac{49!}{(49-6)!\cdot6!}=\frac{49!}{43!\cdot6!} = 13{,}983,816 $$

   Existuje celkem 13 983 816 možností, které může být vylosováno. Což nám, mimochodem, dává pravděpodobnost výhry při jedné sázce 1/13 983 816, což je 0,00000715112 %.

2. Sagvan, známý balič holek, je zrovna na vesnické tancovačce, kde se nachází celkem 13 krásných dívek, o které by měl zájem. Sagvan ví, že je schopen za večer obšťastnit 4 různé dívky. Z kolika různých čtveřic si může Sagvan vybírat?

   To je opět jednoduchý příklad na kombinace, na pořadí nezáleží, Sagvan bude stejně dobrý s první dívkou jako s poslední. Dostáváme tak množinu 13 dívek, z nichž vybíráme vždy 4 dívky. To vede na kombinační číslo

   $$ {13 \choose 4} = 715. $$

3. Máte skupinu padesáti lidí - polovina muži a polovina ženy. Kolik existuje různých trojic lidí, pokud nesmí být složeny pouze z jednoho pohlaví (tj. v trojici se nesmí vyskytnout tři muži nebo tři ženy).

   To už je trošičku složitější kombinace. Pokud vyloučíme jednopohlavní trojici lidí, zbudou nám pouze dvě možnosti, jak může být trojice složena - dva muži a jedna žena nebo jeden muž a dvě ženy, přičemž počet kombinací první skupiny (dva muži a jedna žena) bude stejný, jako počet kombinací druhé skupiny. Stačí nám tedy vypočítat počet kombinací první skupiny a ten následně vynásobit dvěma. Teď už je to opět hračka. Určíme počet kombinací různých dvojic mužů, což je dvacet pět nad dvěma a vynásobíme to počtem kombinací jedné ženy (to dělá dvacet pět, viz předchozí seznam kombinačních čísel, konkrétně hned to první). Tento výsledek již jen vynásobíme dvěma a máme konečný výsledek.

   $$ 2 \cdot {25 \choose 2} \cdot {25 \choose 1} = 15000. $$

4. V krabici je 15 výrobků, z nichž jsou 4 vadné. Kolika způsoby lze vybrat 6 výrobků tak,

   • aby žádný nebyl vadný? V tuto chvílí vybíráme 6 výrobků z 15 − 4 = 11 výrobků, které nejsou vadné. Dostáváme tak kombinační číslo

     $$ {11 \choose 6} = 462. $$

   • aby byl vadný právě jeden výrobek? Vybíráme tak množinu, která obsahuje 5 funkčních výrobků a 1 vadný. Funkčních výrobků máme celkem 11, vadných máme 4. Použijeme kombinatorické pravidlo součinu a získáváme výsledek:

     $$ {11 \choose 5} \cdot {4 \choose 1} = 1848 $$

   • aby nejvýše jeden byl vadný? K řešení využijeme předchozí výsledky. Víme, že máme celkem 462 možností, jak vybrat právě 6 funkčních výrobků a máme 1848 možností jak vybrat pět funkčních a jeden vadný výrobek. Použijeme tak kombinatorické pravidlo součtu, tyto výsledky sečteme a máme výsledek, který chceme, tj. nejvýše jeden vadný výrobek (= buď žádný vadný výrobek, nebo právě jeden). Výsledek tak je: 462 + 1848 = 2310.

Zdroje a další čtení

• Kombinatorika na cuni.cz
• Bělohlávek, Vychodil: Diskrétní matematika [PDF]