Variace, permutace, kombinace

Variace

k-členná variace z n prvků je uspořádaná k-tice sestavená z těchto prvků tak,
že každý se v ní vyskytuje nejvýše jednou.

Definici se pokusíme vysvětlit na příkladu:

Příklad

V košíku je jablko, hruška, broskev a pomeranč. Kolika způsoby můžeme vybrat jedno ovoce k snídani, jedno ke svačině a jedno k obědu?

k-členná variace z n prvků znamená, že ze všech možných prvků (kterých je n) vybíráme jen několik (k; k ≤ n). V našem příkladu vybíráme tři kusy ovoce ze čtyř možných (k = 3, n = 4). Pokud vybíráme všechny prvky, platí k = n; v takových případech mluvíme o permutacích.
Uspořádaná k-tice znamená, že záleží na pořadí, v jakém prvky vybíráme. V našem příkladu záleží na tom, jestli vybereme jablko k snídani a pomeranč ke svačině nebo naopak.
Formulace "každý se v ní (k-tici) vyskytuje nejvýše jednou" znamená, že když některý prvek vybereme, nemůžeme ho vybrat podruhé. V našem příkladu je jasné, že pokud sníme jablko k snídani, už ho nemůžeme sníst ke svačině nebo k obědu.

Odpověď na otázku "Kolika způsoby můžeme vybrat jedno ovoce k snídani, jedno ke svačině a jedno k obědu?" budeme hledat takto:
– K snídani můžeme vybrat libovolné ovoce, máme tedy 4 možnosti.
– Ke svačině už můžeme vybírat jen ze zbývajících tří druhů ovoce.
– Při výběru ovoce k obědu už budeme mít jen dvě možnosti.
Podle kombinatorického pravidla součinu je tedy 4 · 3 · 2 = 24 způsobů, jak vybrat ze čtyř kusů ovoce jedno k snídani, jedno ke svačině a jedno k obědu.

Zobecněním předchozího postupu dostaneme vzorec pro určení počtu k-členných variací z n prvků:
– První prvek vybíráme ze všech n prvků, máme proto n možností, jak ho vybrat.
– Pro druhý prvek už máme jen n − 1 možností, protože nemůžeme znovu vybrat prvek, který byl vybraný jako první.
– Podobně pro třetí prvek máme n − 2 možností, protože dva prvky už byly vybrány.
Takto pokračujeme dál, dokud nevybereme k prvků. Poslední, k-tý prvek můžeme vybrat n − k + 1 způsoby: Z původních n prvků už jsme vybrali k − 1 prvků, zbývá proto n − (k − 1) = n − k + 1 prvků, ze kterých vybíráme ten poslední, k-tý prvek.
Využitím kombinatorického prvidla součinu dostáváme počet V(k, n) všech k-členných variací z n prvků:
V(k, n) = n · (n − 1) · (n − 2) · … · (n − k + 1).

Počet V(k, n) všech k-členných variací z n prvků je
V(k, n) = n · (n − 1) · (n − 2) · … · (n − k + 1).

Příklad

Určete počet všech pětičlenných variací ze sedmi prvků.

Řešení

Dosazením do vzorce k = 5, n = 7, dostáváme:
V(5, 7) = 7 · 6 · 5 · 4 · 3 = 2 520

Zkuste si spočítat variace také pro jiné hodnoty k a n. Výsledek si zde můžete ověřit.

k =		(k ≤ 2 000)
n =
V(k, n) =

Příklad

K sestavení vlajky, která má být složena ze tří různobarevných vodorovných pruhů, jsou k dispozici látky barvy červené, modré, zelené, bílé a žluté.
a) Určete počet vlajek, které lze z látek těchto barev sestavit.
b) Kolik jich má uprostřed modrý pruh?
c) Kolik jich má (kdekoli) bílý pruh?
d) Kolik jich nemá uprostřed červený pruh?

Řešení

a) Vzhledem k tomu, že pruhy mají mít různé barvy a že záleží na pořadí těchto pruhů, jde o tříčlenné variace z pěti prvků (tj. k = 3, n = 5). Z látek daných barev lze sestavit V(3, 5) = 5 · 4 · 3 = 60 různých vlajek.

b) Jestliže je uprostřed modrý pruh, zbývá jen vybrat barvy pro krajní pruhy. Vybíráme tedy dvě ze čtyř barev a záleží na jejich pořadí, jde proto o dvoučlenné variace ze čtyř prvků: V(2, 4) = 4 · 3 = 12 vlajek.

c) Látku bílé barvy můžeme použít na horní, prostřední nebo dolní pruh vlajky. Podobně jako v případě b) vybíráme na zbylé dva pruhy dvě barvy ze zbývajících čtyř. Celkem tedy můžeme sestavit 3 · 12 = 36 takových vlajek.

d) Všechny vlajky můžeme rozdělit na dvě disjunktní skupiny: v první skupině budou takové vlajky, které mají uprostřed červený pruh, ve druhé skupině budou vlajky, které červený pruh uprostřed nemají. Počet všech vlajek je 60 (viz případ a)); počet vlajek, které mají uprostřed červený pruh, je 12 (viz případ b)); počet vlajek, které uprostřed červený pruh nemají, je 60 − 12 = 48.

Vyjádření počtu variací pomocí faktoriálu
Několik úloh k variacím