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 · 3 = 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₁ způsoby, druhý člen
po výběru prvního členu n₂ 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₁ · n₂ · … · 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₁ = 4, n₂ = 3; n₁ · n₂ = 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 · 2 · 2 = 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?

Řešení

V prvním hodu může padnout jedno ze šesti čísel, tj. n₁ = 6, ke každému z nich může ve druhém hodu opět padnout jedno ze šesti čísel, tj. n₂ = 6. Počet různých dvojic (k = 2) je tedy 6 · 6 = 36.