Kombinatorika studuje konečné soubory (množny a uspořádaná k-tice, k \in \N. Základními větami kombinatoriky jsou tzv. kombinatorické pravidlo součtu a kombinatorické pravidlo součinu.
Tato pravidla jsou intuitivní a jejich výklad se může zdáti býti zbytečný. Nicméně následující dvě věty mají velké využití v úlohách zahrnující variace, kombinace a permutace.
Kombinatorické pravidlo součinu: Jestliže z prvků dané množiny (resp. daných množin) vytváříme uspořádané k-tice (x_1, x_2, ..., x_k) tak, že první člen x_1 lze vybrat n_1 způsoby, druhý člen n_2 způsoby atd., až k-tý člen lze vybrat po výběru všech předcházejících členů n_k způsoby, pak počet všech možných uspořádaných k-tic (x_1, x_2, ..., x_k) je roven n_1 \cdot n_2 \cdot ... \cdot n_k.
Příklad: Mějme číslice 1, 2, 3, 4, 5, 6, 7 a vytvořme z nich všechna čtyřmístná čísla, kde bude každá číslice nejvýše jednou.
Když dělám čtyřmístná čísla, tak dělám v tomto případě čtveřice, v obecném případě k-tice. Čtveřice (1,2,3,4) je číslo 1234. Vybírám tedy uspořádané k-tice (v našem případě čtveřice). Proč uspořádané? Protože kdybych vzal jinou čtveřici (2,3,4,1), tak dostanu jiné číslo, a to 2341. Na pořadí v k-tici tedy záleží!
Pravidlo kombinatorického součinu mi říká, že kdy vezmeme všechny k-tice, v našem případě uspořádané čtveřice, jejichž členy lze postupně vybírat n_k způsoby, pak celkový počet je n_1 \cdot n_2 \cdot … \cdot n_k.
V našem případě vytváříme čtveřice. Na prvním místě v našem výsledném čtyřmístném čísle může být 7 číslic (možností). Nejsem jakkoliv omezen. Na druhém místě může být 6 číslic (možností), jelikož ve finálním čísle je každá číslice nejvýše jednou. Potom tedy na třetím místě je nejvýše 5 možností a na čtvrtém místě nejvýše 4 možnosti.
Pak tedy platí, že celkový počet všech způsobů, kolika můžu vytvořit číslo z číslic 1, 2, 3, 4, 5, 6, 7 tak, aby každá číslice byla v čísle obsažena nejvýše jednou je:
7 \cdot 6 \cdot 5 \cdot 4 = 840
Kombinatorické pravidlo součtu: Jsou-li A_1, A_2, ..., A_k konečné množiny, které mají po řadě n_1, n_2, ..., n_k prvků, a jsou-li každé dvě z těchto množin disjunktní (tj. A_i \cap A_j = \varnothing pro každé i \neq j , pak jejich sjednocení A_1 \cup A_2 \cup ... \cup A_k má n_1 + n_2 + ... + n_k prvků, takže počet všech možných způsobů výběru právě jednoho prvku ze sjednocení A_1 \cup A_2 \cup ... \cup A_k je roven n_1 + n_2 + ... + n_k.
Příklad: Mějme čísla 1, 3, 7 a máme zjistit, kolik různých čísel se dá z těchto číslic vytvořit.
Máme tři možnosti, jelikož můžeme tvořit čísla jednomístná, dvoumístná nebo trojmístná, protože máme tři číslice. Označme:
A_1 jako množina jednomístných čísel
A_2 jako množina dvoumístných čísel
A_3 jako množina trojmístných čísel
Tyto množiny jsou navzájem disjunktní, protože je jasné, že nemohu mít jedno číslo zároveň ve dvou množinách.
Jaké číslice obsahuje množina A_1? Obsahuje 1, 3, 7, tedy:
A_1 = \{1;3;7\}.
Jaké číslice obsahuje množína A_2? Obsahuje množinu všech dvoumístných čísel vytvořených z číslic 1; 3; 7. Tedy
A_2 = \{11; 13; 17; 31; 33; 37; 71; 73; 77 \}
Jaké číslice obsahuje množína A_3? Obsahuje množinu všech trojmístných čísel vytvořených z číslic 1; 3; 7. Tedy
A_3 = \{111; 113; ...\}
Nyní mohu aplikovat pravidlo součinu:
Pokud mám jednomístné číslo, mohu využít celkem tři možnosti. Pokud mám dvoumístné číslo, mohu využít na první pozici tři možnosti a na druhou pozici také tři možnosti. Tedy mohu vytvořit 3 \cdot 3 číslic, tedy devět. Pokud mám trojmístné číslo, tak na první pozici mohu použít tři číslice, na druhou pozici také tři číslice a na třetí pozici také tři číslice. Mám tedy celkem 3 \cdot 3 \cdot 3 možností, tedy 27 číslic.
Jak zjistíme celkový výsledek? My víme, že výsledek všech čísel, které jsou nejvýše trojmístné a dají se vytvořit z číslic 1, 3, 7 je A_1 \cup A_2 \cup A_3. To jsou všechna čísla, která lze vytvořit z tří zadaných číslic a jsou jednomísntá, dvoumístná nebo trojmístná.
Nás ale zajímá počet všech prvků množiny, tedy |A_1 \cup A_2 \cup A_3|.
|A_1 \cup A_2 \cup A_3|=3+9+27=39
Uvědomme si, proč jsem mohl využít toto pravidlo. Jednotlivé množiny jsou po dvou disjunktní. Já vím, že prvky jedné množiny nemohou být prvkem jiné množiny. V tomto posledním kroku jsem užil pravidlo součtu, sečetl jsem mohutnosti všech množin.
Užil jsem také pravidlo součinu při zjišťování počtu možností jednociferných, dvouciferných a trojciferných čísel.
Příklady:
- Ve škole jsou dvě první třídy: 1. A a 1. B. Do třídy 1. A chodí 15 žáků, do třídy 1. B chodí 18 žáků. Kolik je na škole prváků? [33]
- Adam má 3 zvířata - pštrosa, býka a ovci. Rozhodl se, že 2 ze svých zvířat dá svým kamarádům. Jedno Honzovi a druhé Zbyňkovi. Kolik má možností, jak zvířata rozdělit mezi Honzu a Zbyňka? [6]
- Bára má 3 různá trička a 5 různých sukní. Kolika způsoby si může vzít tričko a sukni, aby pokaždé vypadala jinak? [15]
- Určete počet všech trojciferných přirozených čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou. [648]
- Ze Lhotky do Hradce vedou 3 různé cesty, z Hradce do Budína vedou 4 různé cesty. a) Určete počet způsobů, jimiž lze vybrat trasu:ze Lhotky přes Hradec do Budína a zpět. [144] b) Ze Lhotky přes Hradec do Budína a zpět tak, že žádná cesta není použita dvakrát. [72] c) ze Lhotky přes Hradec do Budína a zpět tak, že cesta ze Lhotky do Hradce a z Hradce do Lhotky je ta samá, z Hradce do Budína a zpátky je různá. [36]
- Čtverec o straně délky 4 cm je rozdělen rovnoběžkami se stranami na 16 stejných čtverců.Určete, kolik je v daném obrazci čtverců? [30]
- Biatlonistka Katka má 5 zlatých, 3 stříbrné a 6 bronzových medailí, každou z jiné soutěže. Chtěla by si některé ze svých medailí pověsit na poličku, která má přesně 5 háčků na pověšení. Kolik různých možností Katka má, aby si medaile rozvěsila tak, aby na prvním háčku byla jedna ze zlatých medailí, na druhém jedna ze stříbrných, na třetím jedna z bronzových a na posledních dvou libovolná medaile? [9900]
- Určete celkový počet tahů koně na šachovnici 8x8. [336]
- Kolika způsoby lze vybrat na šachovnici 8x8 jedno bílé a jedno černé pole? [1024] Kolika způsoby to lze učinit, nesmějí-li vybraná pole ležet ve stejném řádku ani ve stejném sloupci? [738]
- Kolika způsoby lze z úplného souboru domina (28 kostek) vybrat dvě tak, abychom je mohli přiložit k sobě? Tzn., aby se nějaký počet ok vyskytoval zároveň na obou kostkách? [147]
- Určete počet všech možných tanečních párů z 15 chlapců a 10 děvčat.[150]
- V košíku je 12 jablek a 10 hrušek. Petr si má z něho vybrat jedno ovoce tak, aby Věra, která si po něm vybere jedno jablko a jednu hrušku, měla co největší možnost výběru. Jaké ovoce si má Petr vybrat? [pokud si Petr vybere jablko, má Věra 110 možností. Pokud si Petr vybere hrušku, má Věra 108 možností. Petr si tedy musí vzít jablko, aby měla věra co nejvíce možností výběru].
- Ve třídě 5. A chodí 14 žáků na němčinu a 13 na francouzštinu. Každý žák navštěvuje právě jeden z uvedených předmětů. Kolika způsoby lze vybrat dvojici na týdenní službu tak, aby měl službu jeden žák z němčiny a jeden žák z francouzštiny? [182] Kolik let by žáci museli chodit do školy, aby se všechny tyto dvojice vystřídaly? (Počítejte, že školní rok má 33 vyučovacích týdnů.) [5.515, 5 a půl roku]
- Určete počet čtyřciferných čísel, které začínají cifrou 1 a nekončí cifrou 2, nebo končí cifrou 2 a nezačínají cifrou 1. [1700]