Nastavení

12.2 Základní počítací principy

12.2.1 Variace, permutace, kombinace

Sepišme nyní principy prezentované v Příkladě 12.1 do obecných tvrzení, kterými zavedeme pojmy variace, permutace a kombinace. Dokazují se stejnými argumenty jako v Příkladě 12.1, jenom nahradíme číslo $6$ parametrem $n\in \N$ vyjadřujícím počet různých kategorií, a číslo $4$ parametrem $k\in \N$ vyjadřujícím počet prvků, které za daných podmínek z  $n$ možných kategorií vybíráme. Důkazy ponecháme na čtenáři.

Jako první zobecníme případy b. a c. Příkladu 12.1, ve kterých děláme výběry prvků z různých kategorií, přičemž záleží na pořadí vybraných prvků.

Mějme $n\in\N$ různých kategorií objektů. Pro $k\in\N$ se každá uspořádaná $k$-tice sestavená z prvků z daných kategorií, přičemž se ve vybrané $k$-tici může vyskytovat libovolný počet prvků z každé kategorie, nazývá variace $k$ prvků z  $n$ s opakováním. Pokud je $k\leq n$ a z každé kategorie se ve vybrané $k$-tici vyskytuje nejvýše jeden prvek, jedná se o  variace $k$ prvků z  $n$.

Následující pojmy a tvrzení odpovídají případům a. a f. v Příkladě 12.1 a jedná se o různá uspořádání pevně zvoleného počtu prvků.

Mějme $n\in\N$ různých prvků. Každá uspořádaná $n$-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje právě jednou, se nazývá permutace $n$ prvků. Nyní mějme $\ell\in\mathbb{N}$ a $n_1$ stejných prvků kategorie 1, $n_2$ stejných prvků kategorie 2 (odlišné od kategorie 1), atd. až $n_{\ell}$ stejných prvků kategorie $\ell$ (odlišné od předchozích). Označme $n=n_1+n_2+\cdots +n_{\ell}$. Libovolná uspořádaná $n$-tice těchto prvků se nazývá permutace s opakováním.

Všimněme si, že permutace $n$ prvků jsou vlastně variace $n$ prvků z  $n$. (Zde připomínáme, že z definice je $0!=1$.)

Konečně, Příklad 12.1 části d. a e. odpovídají výběrům prvků z různých kategorií, přičemž nezáleží na pořadí vybraných prvků.

Mějme $n\in\N$ a $k\in\N$ takové, že $k\leq n$. Libovolnému výběru $k$ prvků z  $n$ různých kategorií (bez jakéhokoli uspořádání), přičemž z každé kategorie můžeme vybrat nejvýše jeden prvek, se říká kombinace $k$ prvků z  $n$. Jedná se vlastně o výběry $k$-prvkových podmnožin z  $n$-prvkové množiny. Pokud $k\in\mathbb{N}$ je libovolné, potom se každému výběru $k$ prvků z  $n$ různých kategorií (bez jakéhokoli uspořádání), ve kterém může být i více prvků z jedné kategorie, říká kombinace $k$ prvků z  $n$ s opakováním

12.2.2 Kombinační číslo

Na chvíli se zastavíme u výrazu vyjadřujícího počet různých kombinací, kterému se říká kombinační číslo. Ukážeme si, jak ho efektivně vyčíslit a pár jeho základních vlastností.

Začneme připomenutím funkce faktoriál, která je pro $n\in\N_0$ definována následovně:

Z Tvrzení 12.3 plyne, že kombinační číslo $n\choose k$ vyjadřuje počet všech možných kombinací $k$ prvků z  $n$.

K výpočtu kombinačního čísla není potřeba počítat všechny tři faktoriály. Stačí si všimnout, že (podle definice funkce faktoriál) platí následující vztah

K vyčíslení kombinačního čísla tedy zvolíme ten z výrazů na pravé straně, který vede na jednodušší výpočet.

Někdy se nám při výpočtech budou hodit i následující vztahy mezi kombinačními čísly, které lze odvodit jednoduše přímým výpočtem z definice.

12.2.3 Násobící, sčítací a doplňkový princip

Nyní si představíme tři základní počítací principy (vyplývající z teorie mohutnosti množin), pomocí kterých lze kombinatorické úlohy rozdělit na menší podúlohy.

To, že jsou fáze nezávislé znamená, že probíhají postupně a že výsledek v jedné fázi neovlivní průběh další fáze. Tedy libovolný způsob provedení jedné fáze může být následován kteroukoliv z možností v další fázi – proto se počty možností v jednotlivých fázích navzájem násobí. Tvrzení nebudeme dále formálně dokazovat, ale demonstrujeme si ho na jednoduchém příkladě.

Hierarchicky lze takovýto proces reprezentovat stromem s výškou odpovídající počtu fází procesu, ve kterém větvení v úrovni $i-1$ odpovídá fázi $i$ procesu. Počet všech různých způsobů, jak lze proces vykonat, potom odpovídá počtu listů tohoto stromu. V našem příkladě bychom tak dostali strom výšky 3, jehož kořen má $26^2$ potomků, každý uzel v úrovni $1$ má $10^2$ potomků, každý uzel v úrovni $2$ má $4$ potomky. Počet listů tohoto stromu je skutečně $26^2\cdot 10^2\cdot 4=270\,400$.

Násobící princip jsme vlastně již využili při odvození počtu variací a permutací.

Tvrzení 12.4 jsme formulovali popisem průběhů nějakých procesů. Matematicky přesnější přístup je přes mohutnosti množin. Násobící princip totiž odpovídá tvrzení, že počet prvků v kartézském součinu konečně mnoha konečných množin je roven součinu počtu prvků v jednotlivých množinách.

Dále si uvedeme princip, který se aplikuje, když proces připouští různé alternativy.

Ani toto tvrzení nebudeme dokazovat, ale objasníme si ho na příkladě.

Podobně jako násobící princip, i sčítací princip má svou formulaci pomocí mohutnosti množin. Odpovídá tvrzení, že počet prvků v sjednocení konečně mnoha konečných množin, které jsou po dvou disjunktní, je roven součtu prvků v jednotlivých množinách. Princip inkluze a exkluze je obdobou pro sjednocení množin, které nejsou po dvou disjunktní.

Následující princip se typicky uvádí jako samostatné tvrzení. Z jeho formulace by však mělo být ihned zřejmé, že se vlastně jedná pouze o specifické použití sčítacího principu pro $N=2$.

Pokud chceme například spočítat, kolik lze z písmen abecedy vytvořit různých hesel délky právě 4, která obsahují písmeno A, můžeme spočítat počet všech hesel délky 4 a od tohoto počtu odečíst počet hesel délky 4, která neobsahují písmeno A. (Je to jednodušší než počítat to přímo, museli bychom rozlišit kolikrát se písmeno A vyskytuje, na jakých pozicích, atd.) Počet všech různých hesel délky právě 4, která obsahují písmeno A, je tedy $26^4 - 25^4$ podle 12.1.