Základní kombinatorická pravidla
Kombinatorické pravidlo součinu
Toto pravidlo používáme v běžném životě zcela automaticky. Než uvedeme jeho matematickou formulaci, ukážeme si jeho využití na příkladu.
Příklad
U stánku nabízejí čtyři druhy zmrzliny a tři polevy. Kolik různých zmrzlin s polevou lze vytvořit, jestliže nechceme míchat více druhů ani více polev?
Řešení
Následující diagram zobrazuje všechny možnosti:
vanilková |
čokoládová poleva | |
oříšková poleva | ||
ovocná poleva | ||
jahodová |
čokoládová poleva | |
oříšková poleva | ||
ovocná poleva | ||
meruňková |
čokoládová poleva | |
oříšková poleva | ||
ovocná poleva | ||
citrónová |
čokoládová poleva | |
oříšková poleva | ||
ovocná poleva |
Ke každému ze čtyř druhů zmrzliny můžeme přidat jednu ze tří polev, celkem je proto možné vytvořit \(4\cdot3=\boldsymbol{12}\) různých zmrzlin s polevou.
Zobecněním předchozí úvahy dojdeme k následujícímu pravidlu:
Počet všech uspořádaných \(k\)-tic, jejichž první člen lze vybrat \(n_1\) způsoby, druhý člen po výběru prvního členu \(n_2\) způsoby atd. až \(k\)-tý člen po výběru všech předcházejících členů \(n_k\) způsoby, je roven \(n_1\cdot n_2\cdot\ldots\cdot n_k\).
V úvodním příkladě jsme hledali uspořádané dvojice druh − poleva, jejichž první člen (druh) lze vybrat čtyřmi způsoby a druhý člen (polevu) lze vybrat třemi způsoby. Tedy \(k=2\), \(n_1=4\), \(n_2=3\); \(n_1\cdot n_2=12\).
Kombinatorické pravidlo součinu můžeme použít také v případě, kdy několikrát (\(k\)-krát) opakujeme výběr z určitých prvků a zajímá nás, kolik různých pořadí může vzniknout. Např. když házíme mincí, jde o opakovaný výběr ze dvou prvků (orel, panna). Po třech hodech může vniknout \(2 \cdot 2 \cdot 2 = \boldsymbol{8}\) různých výsledků:
První hod | Druhý hod | Třetí hod | ||||
---|---|---|---|---|---|---|
orel − orel − orel | 1 | |||||
orel − orel − panna | 2 | |||||
orel − panna − orel | 3 | |||||
orel − panna − panna | 4 | |||||
panna − orel − orel | 5 | |||||
panna − orel − panna | 6 | |||||
panna − panna − orel | 7 | |||||
panna − panna − panna | 8 |
Příklad
Kolik různých uspořádaných dvojic čísel můžeme dostat, když hodíme dvakrát kostkou s jedním až šesti oky na jednotlivých stěnách?
(Kliknutí na kostku znamená nový hod.)
Řešení
V prvním hodu může padnout jedno ze šesti čísel, tj. \(n_1=6\), ke každému z nich může ve druhém hodu opět padnout jedno ze šesti čísel, tj. \(n_2=6\). Počet různých dvojic (\(k=2\)) je tedy \(6 \cdot 6 = \boldsymbol{36}\).