Variace, permutace, kombinace
Kombinace
Kombinace se od variací liší tím, že nezáleží na pořadí vybraných prvků.
k-členná kombinace z n prvků je neuspořádaná
k-tice sestavená z těchto prvků tak,
že každý se v ní vyskytuje nejvýše jednou.
Abychom odlišili zápisy variací a kombinací, zapisujeme variace do kulatých závorek, např. (c, a, b), a kombinace do složených závorek, např. {e, f, g}.
Ukažme si rozdíl mezi tříčlennými variacemi ze čtyř prvků a tříčlennými kombinacemi ze čtyř prvků:
| Tříčlenné variace z prvků a, b, c, d: | |||
|
(a, b, c) (a, c, b) (b, a, c) (b, c, a) (c, a, b) (c, b, a) |
(a, b, d) (a, d, b) (b, a, d) (b, d, a) (d, a, b) (d, b, a) |
(a, c, d) (a, d, c) (c, a, d) (c, d, a) (d, a, c) (d, c, a) |
(b, c, d) (b, d, c) (c, b, d) (c, d, b) (d, b, c) (d, c, b) |
| Tříčlenné kombinace z prvků a, b, c, d: | |||
| {a, b, c} | {a, b, d} | {a, c, d} | {b, c, d} |
Každé tříčlenné kombinaci ze čtyř prvků odpovídá 3! = 6 tříčlenných variací ze stejných čtyř prvků.
Obecně každé k-členné kombinaci z n prvků odpovídá k!
k-členných variací ze stejných n prvků.
Odtud můžeme odvodit vztah mezi počtem k-členných kombinací z n prvků
K(k, n)
a počtem k-členných variací z n prvků
V(k, n):
V(k, n) = k! · K(k, n).
Tento vztah můžeme dál rozepsat a vyjádřit počet k-členných kombinací
v závislosti na hodnotách k a n:
| K(k, n) = | 1 k! |
· V(k, n) | = | 1 k! |
· | n! (n − k)! |
= | n! k! · (n − k)! |
| K(k, n) | = | n! k! (n − k)! |
. |
Jak už bylo uvedeno výše, tříčlenné kombinace ze čtyř prvků jsou čtyři:
{a, b, c},
{a, b, d},
{a, c, d},
{b, c, d}.
Zkusme jejich počet určit pomocí odvozeného vzorce:
| K(3, 4) | = | 4! 3! · (4 − 3)! |
= | 4! 3! · 1! |
= | 4 |
Pro výpočet K(k, n) můžete využít následující skript:
| k = | ||
| n = | ||
| K(k, n) = | ||
Příklad
Ve třídě je 26 žáků. Kolika způsoby z nich lze vybrat dva zástupce třídy?
Řešení
| K(2, 26) = | 26! 2! · 24! |
= 325. |
Kombinace a podmnožiny
Zůstaneme ještě chvíli u tříčlenných kombinací z prvků a, b, c, d:
{a, b, c},
{a, b, d},
{a, c, d},
{b, c, d}.
Všimněte si, že tyto kombinace přesně odpovídají všem tříprvkovým podmnožinám množiny
{a, b, c, d}.
Tato vlastnost platí obecně:
k-členná kombinace z n prvků je k-členná podmnožina množiny těmito n prvky určené.
Prázdnou množinu (k = 0) lze z libovolné n-prvkové množiny vybrat vždy jen jediným způsobem, proto pro všechna n, kde n je přirozené číslo, platí K(0, n) = 1.
Příklad
Určete počet tříprvkových podmnožin množiny {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
Řešení
| K(3, 10) = | 10! 3! · 7! |
= 120. |
Kombinační číslo
Kombinační číslo je symbol, který označuje počet k-členných kombinací z n prvků.
| ( | n k | ) | = | n! k! (n − k)! |
| ( | n k | ) |
Počet K(k, n) všech k-členných kombinací z n prvků můžeme zapsat kombinačním číslem:
| K(k, n) = | ( | n k | ) |
Při počítání s kombinačními čísly se často využívá následující vlastnost:
| ( | n n − k | ) | = | ( | n k | ) |
Odvození je snadné:
| ( | n n − k | ) | = | n! (n − k)! [n − (n − k)]! |
= | n! (n − k)! k! |
= | ( | n k | ) |
Příklad
U výtahu, do něhož můžou nastoupit nejvýše tři osoby, stojí 5 osob. Označme je a, b, c, d, e. Sestavte všechny trojice osob, které mohou nastoupit, a vypište dvojice, které v daném případě nenastoupí.
Kliknutím na osobu před výtahem a ve výtahu se tyto dvě osoby vymění:
| Ve výtahu | Před výtahem |
|---|---|
| Adam, Bára, Cyril, David, Ema | Adam, Bára, Cyril, David, Ema |
Řešení
| Nastoupí | Zůstávají |
|---|---|
| {a, b, c} | {d, e} |
| {a, b, d} | {c, e} |
| {a, b, e} | {c, d} |
| {a, c, d} | {b, e} |
| {a, c, e} | {b, d} |
| {a, d, e} | {b, c} |
| {b, c, d} | {a, e} |
| {b, c, e} | {a, d} |
| {b, d, e} | {a, c} |
| {c, d, e} | {a, b} |
| ( | n n − k | ) | = | ( | n k | ) | , |
| ( | 5 3 | ) | = | ( | 5 2 | ) | = 10 |
Další vlastnosti kombinačních čísel
Úlohy k tématu: kombinační čísla, kombinace