12.1 Základní počítací principy

1 Úvod 2 Číselné množiny 3 Logika: důkaz 4 Algebraické výrazy 5 Funkce 6 Rovnice a nerovnice 7 Lineární a lomené funkce 8 Trigonometrické funkce 9 Exponenciála a logaritmus 10 Posloupnosti a sumy 11 Analytická geometrie 12 Kombinatorika 12.1 Základní počítací principy 12.2 Další příklady 12.3 Pravděpodobnost 13 Logika – formalizace Index Literatura

12.1.1 Násobící princip

Základní kombinatorické principy vychází z následujícího tvrzení z oblasti teorie mohutnosti množin:

Tvrzení 12.1 (Násobící princip)

Jestliže nějaký proces probíhá v $N$ nezávislých fázích (kde $N\in\N$) a v $i$-té fází existuje $n_i$ různých způsobů jejího provedení (kde $n_i\in\N$), potom možno daný proces provést celkem $n_1\cdot n_2\cdot n_3\cdots\cdot n_N$ různými způsoby.

Tvrzení nebudeme dokazovat, ale demonstrujeme si ho na jednoduchém příkladě.

Příklad 12.1

Kolik různých hesel délky 5 znaků můžeme vytvořit z písmen anglické abecedy (která má 26 znaků)?

Zobrazit řešení

Tento proces probíhá v pěti fázích – v první vybereme písmeno na první pozici v hesle, ve druhé vybereme písmeno na druhou pozici v hesle, atd. Pro výběr prvního písmene máme 26 možností, a pro každou z těchto možností pak máme opět na výběr z 26 písmen na druhou pozici, se kterými to můžeme zkombinovat. Pro obsazení prvních dvou pozic je tedy celkem $26\cdot 26=676$ možností. No a pro každou z těchto 676 možností je na výběr z 26 písmen na třetí pozici, a tak dále. Proto se počty různých způsobů v jednotlivých fázích procesu navzájem násobí. Výsledek je tedy $26^5=11\, 881\, 376$. Hierarchicky lze tuto úlohu reprezentovat stromem výšky 5, ve kterém má každý uzel 26 potomků. Větvení v úrovni $i$ odpovídá možným výběrům písmene na pozici $i+1$. Odpověď na zadanou otázku je potom počet listů tohoto stromu.

Násobící princip 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.

12.1.2 Motivační příklad

Nyní z násobícího principu odvodíme základní kombinatorické principy – variace, permutace a kombinace. Jde vlastně o nejčastější aplikace násobícího principu s jasnou interpretací, které je proto výhodné formulovat do samostatných tvrzení, na které se můžeme jednoduše odkazovat. Ukážeme si je na jednom společném příkladě.

Příklad 12.2

Čtyři kamarádi se zastavili u stánku se zmrzlinou, ve kterém nabízejí zmrzlinu šesti příchutí: kakaovou, vanilkovou, oříškovou, pistáciovou, jahodovou a citrónovou. Zamyslíme se nad různými kombinatorickými otázkami souvisejícími s touto situací:

Kolika různými způsoby se můžou kamarádi u stánku postavit do řady?
Kolika různými způsoby si můžou každý vybrat jeden kopeček zmrzliny?
Kolika různými způsoby si můžou každý vybrat jeden kopeček zmrzliny tak, aby se žádná příchuť neopakovala?
Kolik můžeme vytvořit různých zmrzlinových pohárů se čtyřmi kopečky zmrzliny různých příchutí?
Kolik můžeme vytvořit různých zmrzlinových pohárů se čtyřmi kopečky zmrzliny, přičemž se příchutě můžou vyskytovat i vícekrát?
Nyní předpokládejme, že je kamarádů devět a každý z nich si objedná jeden kopeček zmrzliny. Kolika různými způsoby může vypadat jejich objednávka, když víme, že tři z nich si objednali kakaovou, tři vanilkovou, dva pistáciovou a jeden jahodovou?

Jde o proces probíhající ve čtyřech nezávislých fázích: v první fázi vybereme ze čtyř lidí, kdo se postaví první, ve druhé fázi vybere ze zbývajících tří lidí, kdo bude druhý, ve třetí fázi vybere ze dvou, kdo bude třetí, a na čtvrtou pozici zůstane jedna osoba. Aplikujeme tedy násobící princip a dostaneme, že počet všech možných seřazení je

\begin{equation*} 4\cdot3\cdot2\cdot1=4!=24. \end{equation*}

Proces má čtyři nezávislé fáze, kde každý z kamarádů vybírá ze všech šesti dostupných příchutí nezávisle na volbě ostatních. Podle násobícího principu je tedy počet možných výběrů

\begin{equation*} 6\cdot 6\cdot 6\cdot 6=6^4=1296. \end{equation*}

Opět je možné výběr rozdělit do čtyř nezávislých fází, ovšem tentokrát se možnosti postupně zužují. První kamarád vybírá ze všech šesti příchutí, druhý už jenom ze zbývajících pěti, třetí ze čtyř, a poslední ze tří. Z násobícího principu tedy plyne že, počet všech výběrů za těchto podmínek je

\begin{equation*} 6 \cdot 5 \cdot 4 \cdot 3 = \frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} = \frac{6!}{2!} = \frac{6!}{(6-4)!} = 360. \end{equation*}

Otázku můžeme ekvivalentně přeformulovat následovně: Kolika různými způsoby si můžou kamarádi vybrat každý jeden kopeček zmrzliny tak, aby se žádná příchuť neopakovala, přičemž nás nezajímá, kdo si kterou příchuť vybral? Můžeme tedy použít řešení c., ale tentokrát při výběru nezáleží na pořadí, tj. všechna přeuspořádání jednoho výběru jsou považována za stejná. V případě c. se každý výběr objevuje ve $4! = 24$ uspořádáních (podle bodu a.), takže musíme výsledek c. vydělit $4!$ a dostaneme

\begin{equation*} \frac{6!}{2!\cdot 4!}=\frac{360}{24}=15 \end{equation*}

možností.

Budeme tedy vybírat čtyři příchutě ze šesti bez jakéhokoli pořadí a bez omezení na opakování. Ukážeme si, že tuto úlohu můžeme převést na úlohu typu d. správnou interpretací.

Výběry lze „kódovat“ jako řetězce obsahující pět symbolů $|$ a čtyři symboly $\bullet$ následovně: Symboly $|$ budou oddělovače vytvářející přihrádky pro jednotlivé příchutě³⁶ a symboly $\bullet$ budou reprezentovat kopečky zmrzliny.

\begin{equation*} \underbrace{ \bullet \, \bullet \, \bullet \, \bullet }_{\text{kopečky}} \,\longrightarrow \underbrace{}_{\text{kakao}}|\underbrace{}_{\text{vanilka}}|\underbrace{}_{\text{ořech}}|\underbrace{}_{\text{pistácie}}|\underbrace{}_{\text{jahoda}}|\underbrace{}_{\text{citrón}}. \end{equation*}

Například, výběru dvou kopečků kakaové, jednoho kopečku pistáciové a jednoho kopečku jahodové bude odpovídat řetězec

\begin{equation*} \bullet \bullet | \, | \, | \bullet | \bullet |. \end{equation*}

Naopak, libovolný řetězec sestavený z pěti symbolů $|$ a čtyř symbolů $\bullet$ reprezentuje nějaký výběr. Například řetězec

\begin{equation*} |\bullet\bullet\bullet | \, | \, | \, |\bullet \end{equation*}

odpovídá výběru tří kopečků vanilkové a jednoho kopečku citrónové.

Takovýmto způsobem můžeme jednoznačně znázornit všechny možné výběry. Počet možných výběrů tedy bude odpovídat počtu všech možných řetězců $|$ a $\bullet$, ve kterých se vyskytuje právě pět symbolů $|$ a čtyři symboly $\bullet$.

Kolik tedy existuje řetězců $|$ a $\bullet$ (binárních řetězců), ve kterých se vyskytuje právě pět symbolů $|$ a čtyři symboly $\bullet$? V řetězci o celkové délce $9$ znaků stačí vybrat $4$ pozice pro $\bullet$ (což je stejné jako vybrat $5$ pozic pro $|$). Na každé pozici může být pouze jeden symbol, tedy se výběru nemůžou opakovat, a nezáleží na tom, v jakém pořadí pozice vybereme. Dostali jsme se tedy do stejné úlohy jako v bodě d., ale nyní vybíráme čtyři (pozice) z devíti možností:

\begin{equation*} \frac{9!}{5!\cdot 4!}=\frac{9\cdot 8\cdot 7\cdot 6}{4\cdot 3\cdot 2}=126. \end{equation*}

Na tuto úlohu budeme taky moci aplikovat model z případu d. Tentokrát nebudeme pro osoby vybírat zmrzlinu, ale pro zrmzlinu vybírat její konzumenty. Je to proces, který proběhne ve čtyřech nezávislých fázích. Nejdřív z devítí kamarádů vybereme tři, kteří dostanou kakaovou zmrzlinu. To odpovídá výběrům $3$ prvků z $9$, ve kterých se vybrané prvky neopakují a nezáleží na pořadí jejich výběru. Podle bodu d. tedy pro tento krok máme $\frac{9!}{6!\cdot 3!}$ možností. V dalším kroku ze zbylých šesti kamarádů vybereme další tři, kteří dostanou vanilkovou zmrzlinu. Pro to máme $\frac{6!}{3!\cdot 3!}$ možností. Dále ze tří vybereme dva kamarády, kteří dostanou pistáciovou zmrzlinu – analogicky, máme $\frac{3!}{1!\cdot 2!}$ možností. No a na závěr zůstane jedna osoba, která bude mít jahodovou zmrzlinu – pouze 1 možnost. Podle násobícího principu počty možností v jednotlivých fázích spolu vynásobíme, čímž dostaneme konečný výsledek

\begin{equation*} \frac{9!}{6!\cdot 3!}\cdot \frac{6!}{3!\cdot 3!}\cdot \frac{3!}{1!\cdot 2!}\cdot 1=\frac{9!}{3!\cdot 3! \cdot 2!}=5040. \end{equation*}

12.1.3 Variace, permutace, kombinace

Sepišme nyní principy prezentované v Příkladě 12.2 do obecných tvrzení, kterými zavedeme pojmy variace,permutace a kombinace. Dokazují se stejnými argumenty jako v Příkladě 12.2, 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.2, 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$.

Tvrzení 12.2

Počet všech různých variací $k\in\N$ prvků z $n\in\N$ s opakováním je

\begin{equation*} n^k=\underbrace{n\cdot n\cdots n}_{k\times} \end{equation*}

a počet všech různých variací $k\in\N$ prvků z $n\in\N$, kde $k\leq n$, (tedy bez opakování) je

\begin{equation*} \frac{n!}{(n-k)!}. \end{equation*}

Následující pojmy a tvrzení odpovídají případům a. a f. v Příkladě 12.2 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.

Tvrzení 12.3

Počet všech různých permutací $n\in\N$ prvků je

\begin{equation*} n!=n\cdot(n-1)\cdot(n-2)\cdots 2\cdot 1. \end{equation*}

Počet všech různých permutací s opakováním uvedených v předchozím odstavci je

\begin{equation*} \frac{n!}{n_1!\cdot n_2!\cdot \cdots \cdot n_{\ell}!}. \end{equation*}

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.2 čá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

Tvrzení 12.4

Počet všech různých kombinací $k\in\N$ prvků z $n\in\N$, kde $k\leq n$, je

\begin{equation*} \frac{n!}{(n-k)!\cdot k!}. \end{equation*}

Počet všech různých kombinací $k\in\N$ prvků z $n\in\N$ s opakováním je

\begin{equation*} \frac{(k+n-1)!}{(n-1)!\cdot k!}. \end{equation*}

12.1.4 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$ definována následovně:

\begin{equation*} n!=\begin{cases} 1,&\quad n=0,\\ n\cdot(n-1)\cdot(n-2)\cdots 2\cdot 1,&\quad n\geq 1. \end{cases} \end{equation*}

Definice 12.1 (Kombinační číslo)

Pro $k,n\in\N_0$, kde $k\leq n$, definujeme kombinační číslo $n\choose k$ (čteme „$n$ nad $k$“) jako

\begin{equation*} {n\choose k}=\frac{n!}{(n-k)!\cdot k!}. \end{equation*}

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

Poznámka 12.1

Kombinačnímu číslu se říká také binomický koeficient jelikož se vyskytuje jako koeficient v mnohočlenu, který vznikne rozvojem $n$-té mocniny libovolného dvojčlenu. Toto tvrzení je obsahem binomické věty (Věta 3.3), podle které pro každé $a,b\in\R$ a $n\in\N$ platí rovnost

\begin{equation*} (a+b)^n=\sum_{k=0}^n{n\choose k}a^{n-k}b^k. \end{equation*}

Binomický koeficient $n\choose k$ tady odpovídá počtu všech různých výběrů $k$ závorek z $n$, u kterých při roznásobení výrazu $(a+b)^n$ volíme člen $b$.

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

\begin{align*} {n\choose k}&=\frac{n!}{(n-k)!\cdot k!}=\frac{n\cdot(n-1)\cdots(n-k+1)}{k!}\\ &=\frac{n\cdot(n-1)\cdots(k+1)}{(n-k)!}.\end{align*}

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.

Pozorování 12.1

Pro libovolné $k,n\in\N_0$ takové, že $k\leq n$, platí

\begin{equation*} {n\choose k}={n\choose n-k}\quad\quad\textup{a}\quad\quad{n\choose k}+{n\choose k+1}={n+1\choose k+1}. \end{equation*}

12.1.5 Sčítací princip

Na závěr této sekce si uvedeme ještě jeden základní kombinatorický princip vycházející z teorie mohutnosti množin.

Tvrzení 12.5 (Sčítací princip)

Jestliže je nějaký proces možno rozdělit na $N$ navzájem různých případů (kde $N\in\N$) a $i$-tý případ lze provést $n_i$ různými způsoby (kde $n_i\in\N$), potom možno daný proces provést celkem $n_1+n_2+\cdots+n_N$ různými způsoby.

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

Příklad 12.3

Kolik lze vytvořit různých hesel z písmen anglické abecedy, které budou mít délku nejvýše 4 znaky?

Zobrazit řešení

Tento proces je možno rozdělit do čtyř navzájem různých případů podle délky hesla. Můžeme tedy zvlášť spočítat počet všech možných hesel délky 1, délky 2, délky 3 a délky 4, a výsledky pak sečíst. Podle výpočtu v Příkladě 12.1 existuje 26 různých hesel délky 1, $26^2$ hesel délky 2, atd. Počet všech hesel délky nejvýše 4 je tedy $26+26^2+26^3+26^4=475\,254$.

Poznámka 12.2

Někdy se jako samostatné tvrzení formuluje i takzvaný doplňkový princip. Jedná se však pouze o specifickou aplikaci sčítacího principu. Doplňkový princip říká, že pokud je nějaký proces možno rozdělit do dvou různých případů, a my známe počet všech způsobů, jak proces vykonat, a také počet způsobů v jednom z případů, pak můžeme počet způsobů v druhém případě spočítat jako rozdíl počtu všech způsobů a způsobů ve známém případě. Vraťme se opět k příkladu s hesly. 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.) Mělo by být tedy zřejmé, že se vlastně jedná o sčítací princip, kde $N=2$.

Poznámka 12.3

Zobecněním sčítacího principu je takzvaný princip inkluze a exkluze (IN-EX). Lze jej požít i v situaci, kdy jednotlivé případy, na které možno nějaký proces rozdělit, nejsou nutně navzájem různé. Uvažujme opět úlohu vytváření hesel, a v rámci ní tři kategorie zvláštních znaků: velká písmena, číslice, a speciální znaky. Zajímá nás, kolik lze vytvořit hesel délky 4 tak, aby obsahovala alespoň jeden zvláštní znak. Mohli bychom zvlášť spočítat počet všech hesel, které obsahují alespoň jedno velké písmeno, pak těch, které obsahují alespoň jednu číslici, a nakonec těch, které obsahují alespoň jeden speciální znak. Tyto případy ovšem nejsou navzájem různé; existují hesla, která obsahují například velká písmena i číslice zároveň (a jsou tedy započtena v prvních dvou případech), nebo dokonce znaky ze všech tří speciálních kategorií (která jsou započtena ve všech třech případech). Proto, na rozdíl od sčítacího principu, pouhým sečtením možností v jednotlivých případech získáme číslo, které je příliš velké, a neodpovídá správnému výsledku. Od tohoto součtu je potřeba odečíst možnosti, které byly započteny ve dvou případech (tedy hesla, která obsahují speciální znaky ze dvou kategorií), čímž ovšem úplně odstraníme ty, které se vyskytují ve všech případech³⁷ (hesla obsahující speciální znaky ze všech tří kategorií), proto je musíme opět přičíst³⁸. Z uvedeného postupu je patrný i původ názvu tohoto principu. Jeho přesné znění i zajímavé aplikace se dozvíte v kurzu BI-DML.21.

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í.