Kombinace, variace a permutace

Kombinace, variace a permutace jsou tři základní způsoby, jak spočítat, kolika způsoby lze vybrat nebo seřadit prvky. Rozhodují dvě otázky: záleží na pořadí? a bereme všechny prvky, nebo jen některé? Permutace seřadí všech n prvků. Variace vybírá k prvků z n a na pořadí záleží. Kombinace vybírá k prvků z n a na pořadí nezáleží:

`\begin{gathered}P(n) = n!\\[10pt] V(k,\ n) = \dfrac{n!}{(n-k)!}\\[10pt] K(k,\ n) = \dbinom{n}{k} = \dfrac{n!}{k! \cdot (n-k)!}\end{gathered}`

Na příkladu: ze čtyř kandidátů (Adam, Bára, Cyril, Dana) se dá zvolit předseda a místopředseda 4 · 3 = 12 způsoby. To je variace, protože Adam předsedou a Bára místopředsedkyní je jiný výsledek než naopak. Dvoučlenný výbor bez funkcí jde sestavit jen 6 způsoby. To je kombinace: dvojice Adam a Bára je jedna, ať ji jmenujeme v jakémkoli pořadí. A postavit všechny čtyři do fronty jde 4! = 24 způsoby, to je permutace.

Počty si můžete ověřit na kalkulačkách kombinace, variace a permutace, které ukážou i postup. Příklady s okamžitou kontrolou jsou v procvičování kombinací a variací.

Na střední škole se kombinatorika probírá obvykle ve 3. ročníku a patří k maturitním tématům. S jednoduchými úlohami typu „kolik je možností“ se ale žáci potkávají už na základní škole. Níže je nejdřív pravidlo součinu, na kterém stojí všechny vzorce, potom faktoriál, permutace, variace a kombinace s řešenými příklady, tabulka, podle které se pozná, který vzorec použít, výběry s opakováním, rovnice s kombinačními čísly, časté chyby a šest příkladů s řešením.

Pravidlo součinu a pravidlo součtu

Když se výběr skládá z několika kroků za sebou a v každém kroku je daný počet možností, počty možností se násobí. To je kombinatorické pravidlo součinu. Ze tří triček a čtyř kalhot se dá sestavit 3 · 4 = 12 různých oblečení, protože ke každému tričku jde vzít kterékoli kalhoty. Strom na obrázku to ukazuje: z každé ze tří větví vedou čtyři další.

Když se naopak vybírá buď z jedné skupiny, nebo z druhé a skupiny nemají nic společného, počty se sčítají. To je pravidlo součtu. Jedou-li ráno do Brna 3 vlaky a 5 autobusů, dá se tam ráno dostat 3 + 5 = 8 spoji. Pomůcka: „a zároveň“ znamená násobit, „nebo“ znamená sčítat.

Příklad 1: trojmístná čísla s různými číslicemi

Kolik je trojmístných čísel, ve kterých se žádná číslice neopakuje?

Číslo vyplňujeme zleva. Na místě stovek může být kterákoli číslice kromě nuly, to je 9 možností. Na místě desítek kterákoli z deseti číslic kromě té už použité, tedy zase 9 možností (nula už tu smí být). Na místo jednotek zbývá 8 číslic. Podle pravidla součinu je to 9 · 9 · 8 = 648 čísel.

Kontrola jinou cestou: kdyby nula na začátku vadit nemusela, bylo by trojic různých číslic 10 · 9 · 8 = 720. Z nich začíná nulou 9 · 8 = 72 a 720 − 72 = 648. Právě tahle nula na začátku je nejčastější chyba celé úlohy.

Faktoriál

Faktoriál čísla n, píše se n! a čte „n faktoriál“, je součin všech přirozených čísel od 1 do n:

`n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1`

Navíc se klade 0! = 1. Není to libovůle: s touto dohodou platí vzorce níže i pro výběr nula prvků a pro výběr všech prvků. Prvních jedenáct hodnot:

Faktoriál roste velmi rychle: 10! je přes tři a půl milionu a 20! má už 19 číslic. Přesně ho i pro velká čísla spočítá kalkulačka faktoriál. Ve zlomcích se faktoriály nikdy nenásobí celé, ale krátí. Větší faktoriál rozepíšeme jen po ten menší:

`\dfrac{10!}{8!} = \dfrac{10 \cdot 9 \cdot 8!}{8!} = 10 \cdot 9 = 90`

Permutace

Permutace z n prvků je každé jejich seřazení do řady. Na první místo můžeme dát kterýkoli z n prvků, na druhé kterýkoli ze zbylých n − 1 a tak dál, až na poslední místo zbude jediný. Podle pravidla součinu:

`P(n) = n \cdot (n-1) \cdots 2 \cdot 1 = n!`

Příklad 2: knihy na polici

Kolika způsoby lze postavit 5 různých knih vedle sebe na polici?

Řadíme všech pět knih, jde o permutace: P(5) = 5! = 5 · 4 · 3 · 2 · 1 = 120 způsobů (kalkulačka permutace).

Příklad 3: dva musí sedět vedle sebe

Šest kamarádů si sedá do řady šesti sedadel v kině. Jana a Petr chtějí sedět vedle sebe. Kolika způsoby se mohou rozesadit?

Jana s Petrem se „svážou“ do jednoho balíčku. Pak se řadí pět objektů (balíček a čtyři ostatní), to jde 5! = 120 způsoby. Uvnitř balíčku mohou Jana a Petr sedět dvěma způsoby, Jana vlevo nebo vpravo. Celkem 2 · 120 = 240 rozesazení.

Kontrola jinou cestou: dvojic sousedních sedadel je v řadě šesti sedadel pět. Na vybranou dvojici se Jana a Petr posadí 2 způsoby a zbylí čtyři na ostatní místa 4! = 24 způsoby: 5 · 2 · 24 = 240. Bez podmínky by rozesazení bylo 6! = 720, vedle sebe tedy sedí právě ve třetině z nich.

Variace

Variace k-té třídy z n prvků je uspořádaná k-tice vybraná z n prvků, ve které se žádný prvek neopakuje. Počítá se stejně jako permutace, jen se zastavíme po k místech:

`\begin{aligned}V(k,\ n) &= n \cdot (n-1) \cdots (n-k+1)\\[8pt] &= \dfrac{n!}{(n-k)!}\end{aligned}`

Součin má právě k činitelů a to je nejrychlejší kontrola: V(3, 8) = 8 · 7 · 6, tři činitelé. Pozor na zápis. Většina českých učebnic píše V(k, n), tedy nejdřív kolik vybíráme a pak z kolika. Kalkulačky na tomto webu i některé jiné texty píšou V(n; k) obráceně a kombinační číslo jako C(n; k). Rozhoduje význam, ne pořadí v závorce: u výběru bez opakování je číslo, ze kterého se vybírá, vždy to větší (nebo stejné).

Příklad 4: medaile

Závodu se účastní 8 běžců. Kolika způsoby mohou být rozdány zlatá, stříbrná a bronzová medaile?

Na pořadí záleží: zlato pro Adama a stříbro pro Báru je jiný výsledek než naopak. Nikdo nezíská dvě medaile, takže se nic neopakuje. Jsou to variace třetí třídy z osmi prvků:

`V(3,\ 8) = 8 \cdot 7 \cdot 6 = 336`

Postup ukáže kalkulačka variace.

Kombinace a kombinační číslo

Kombinace k-té třídy z n prvků je k-prvková skupina vybraná z n prvků, ve které na pořadí nezáleží. Vzorec se odvodí z variací. Každou skupinu k prvků lze seřadit k! způsoby, takže mezi variacemi je každá kombinace započítaná k!-krát. Variace proto vydělíme k!:

`K(k,\ n) = \dfrac{V(k,\ n)}{k!} = \dfrac{n!}{k! \cdot (n-k)!} = \dbinom{n}{k}`

Výraz `\binom{n}{k}` se nazývá kombinační číslo a čte se „n nad k“. Na obrázku je výběr dvou písmen ze čtyř A, B, C, D. Variací je 12, ale vždy dvě z nich tvoří tutéž dvojici, a kombinací je proto 12 : 2 = 6.

Kombinační číslo se nepočítá přes celé faktoriály. Nahoru se napíše k činitelů od n dolů, dolů k! a pak se krátí:

`\dbinom{10}{3} = \dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \dfrac{720}{6} = 120`

Výsledek ukáže i kalkulačka kombinační číslo.

Příklad 5: Sportka

Ve Sportce se tipuje 6 čísel ze 49. Kolik existuje různých tipů?

Na pořadí, v jakém čísla zaškrtneme, nezáleží a žádné číslo nejde zaškrtnout dvakrát. Jsou to kombinace šesté třídy ze 49 prvků:

`\begin{aligned}\dbinom{49}{6} &= \dfrac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\\[8pt] &= 13\,983\,816\end{aligned}`

Skoro 14 milionů. Kdyby na pořadí záleželo, bylo by variací 6! = 720krát víc. Ověřit to můžete na kalkulačce kombinace.

Příklad 6: podání rukou

Na schůzce je 10 lidí a každý si podá ruku s každým. Kolik je podání rukou?

Každé podání je dvojice lidí a v dvojici na pořadí nezáleží:

`\dbinom{10}{2} = \dfrac{10 \cdot 9}{2 \cdot 1} = 45`

Častá chybná odpověď 10 · 9 = 90 počítá každé podání dvakrát, jednou jako „Adam s Bárou“ a jednou jako „Bára s Adamem“.

Vlastnosti kombinačních čísel

• `\binom{n}{0} = \binom{n}{n} = 1` a `\binom{n}{1} = n`. Nic nevybrat i vybrat všechno jde jediným způsobem.
• `\binom{n}{k} = \binom{n}{n-k}`. Vybrat 3 lidi z 10, kteří pojedou na výlet, je totéž jako vybrat 7, kteří zůstanou doma. Proto `\binom{10}{7} = 120` stejně jako `\binom{10}{3}`, a místo `\binom{20}{18}` stačí počítat `\binom{20}{2} = 190`.
• `\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}`. To je pravidlo, podle kterého se staví Pascalův trojúhelník: v jeho řádcích stojí právě kombinační čísla.

Který vzorec použít

Než sáhnete po vzorci, odpovězte si na dvě otázky. Záleží na pořadí? Zkuste v jednom výsledku prohodit dva vybrané prvky. Vznikne-li jiný výsledek, na pořadí záleží. Smějí se prvky opakovat? V PIN kódu se číslice opakovat smějí, v trojici medailistů se běžec opakovat nemůže.

Typické úlohy podle druhu:

• kombinace: výbor, družstvo, tip ve Sportce, karty v ruce, podání rukou,
• variace: funkce ve výboru, medaile, první tři v cíli, čísla z různých číslic,
• permutace: pořadí v řadě, rozesazení, seřazení knih,
• variace s opakováním: PIN, kód zámku, tiket s tipy 1, 0, 2,
• permutace s opakováním: slova z písmen, cesty mřížkou,
• kombinace s opakováním: nákup kusů z několika druhů.

Výběry s opakováním

Variace s opakováním

Když se prvky smějí opakovat, nabídka se po žádném kroku nezmenší. Na každém z k míst je pořád n možností a podle pravidla součinu:

`V'(k,\ n) = n^k`

Čtyřmístných PIN kódů z číslic 0 až 9 je 10⁴ = 10 000 (kalkulačka variace s opakováním). Kdyby se číslice opakovat nesměly, bylo by jich jen V(4, 10) = 10 · 9 · 8 · 7 = 5 040. Tiket, na kterém se u každého ze 14 zápasů tipuje 1, 0 nebo 2, jde vyplnit 3¹⁴ = 4 782 969 způsoby.

Permutace s opakováním

Když jsou mezi řazenými prvky některé stejné, prohozením dvou stejných nevznikne nic nového. Počet všech seřazení n! se proto vydělí faktoriálem počtu každé skupiny stejných prvků:

`P'(k_1,\ k_2,\ \ldots,\ k_s) = \dfrac{n!}{k_1! \cdot k_2! \cdots k_s!}`

Tady n = k₁ + k₂ + … + k_s je počet všech prvků.

Příklad 7: slova z písmen

Kolik různých „slov“, i nesmyslných, vznikne přeskládáním písmen slova ANANAS?

Písmen je 6: A třikrát, N dvakrát, S jednou.

`P'(3,\ 2,\ 1) = \dfrac{6!}{3! \cdot 2! \cdot 1!} = \dfrac{720}{12} = 60`

Kdyby byla všechna písmena různá, bylo by slov 720. Každé slovo se ale v těch 720 objeví 3! · 2! = 12krát, protože tři A mezi sebou a dvě N mezi sebou lze prohodit, aniž by se slovo změnilo.

Příklad 8: cesty mřížkou

Chodec jde ve čtvercové síti z bodu A do bodu B, který je o 5 políček vpravo a o 3 nahoru. Smí jít jen doprava nebo nahoru. Kolik je takových cest?

Každá cesta je řada 8 kroků, z nichž 5 je „doprava“ a 3 „nahoru“. Na obrázku je cesta PPNPPNPN (P doprava, N nahoru). Cest je tolik, kolik je různých řad z pěti P a tří N:

`P'(5,\ 3) = \dfrac{8!}{5! \cdot 3!} = \dfrac{40\,320}{120 \cdot 6} = 56`

Stejné číslo dá `\binom{8}{3}`: stačí vybrat, které tři z osmi kroků půjdou nahoru. Dvě skupiny stejných prvků zvládne kalkulačka permutace s opakováním, slovo ANANAS se třemi skupinami je potřeba spočítat podle vzorce.

Kombinace s opakováním

Vybíráme k kusů z n druhů, druh se smí opakovat a na pořadí nezáleží:

`K'(k,\ n) = \dbinom{n+k-1}{k}`

Příklad 9: kopečky zmrzliny

V cukrárně mají 5 druhů zmrzliny. Kupujete 3 kopečky do kelímku, smějí být i stejné. Kolik je možností?

`\begin{aligned}K'(3,\ 5) &= \dbinom{5+3-1}{3} = \dbinom{7}{3}\\[8pt] &= \dfrac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35\end{aligned}`

Proč právě `\binom{7}{3}`: nákup se dá zapsat jako 3 tečky a 4 přepážky, které oddělují 5 druhů. Zápis •|••||| znamená jeden kopeček prvního druhu a dva druhého. Každý nákup je jiné rozmístění 3 teček na 7 míst. Spočítá to i kalkulačka kombinace s opakováním.

Výrazy a rovnice s kombinačními čísly

K maturitě patří i úlohy, kde se s faktoriály a kombinačními čísly počítá jako s výrazy. Postup je vždy stejný: rozepsat a zkrátit. Nejdřív ale podmínky. Výraz n! má smysl jen pro přirozené n nebo nulu a `\binom{n}{k}` jen pro k ≤ n.

Zjednodušení: větší faktoriál rozepíšeme po ten menší, platí pro n ≥ 1:

`\dfrac{(n+1)!}{(n-1)!} = \dfrac{(n+1) \cdot n \cdot (n-1)!}{(n-1)!} = n^2 + n`

Rovnice: řešte `\binom{n}{2} = 28`. Podmínka je n ≥ 2. Kombinační číslo rozepíšeme a vznikne kvadratická rovnice:

`\begin{aligned}\dfrac{n(n-1)}{2} &= 28\\[8pt] n^2 - n - 56 &= 0\\[4pt] (n-8)(n+7) &= 0\end{aligned}`

Kořen −7 podmínku nesplňuje, řešením je n = 8. Zkouška: `\binom{8}{2} = \frac{8 \cdot 7}{2} = 28`.

Kombinatorika v pravděpodobnosti

Klasická pravděpodobnost je počet příznivých výsledků dělený počtem všech možných, a oba počty se získají kombinatorikou. Ve Sportce je všech tipů 13 983 816 a všech šest čísel trefí jediný. Pravděpodobnost je 1 : 13 983 816 (kalkulačka klasická pravděpodobnost).

Tip, který trefí právě tři čísla, má tři ze šesti tažených a tři ze 43 netažených. Podle pravidla součinu je takových tipů

`\dbinom{6}{3} \cdot \dbinom{43}{3} = 20 \cdot 12\,341 = 246\,820`

a pravděpodobnost je 246 820 : 13 983 816 ≐ 0,018, tedy asi 1,8 %. Takové výpočty dělá kalkulačka tahání bez vracení, a o tom, jak nepředstavitelně malá umí být pravděpodobnost, je článek Opice píší Hamleta.

Časté chyby

• Variace místo kombinace, nebo naopak. Prohoďte dva vybrané prvky. Vznikne jiný výsledek? Pak jde o variaci. Výbor, družstvo a tip ve Sportce jsou kombinace, funkce, medaile a pořadí v cíli variace.
• Zapomenuté opakování. PIN není 10 · 9 · 8 · 7, číslice se v něm opakovat smějí. Je jich 10⁴.
• Nula na začátku čísla. 10 · 9 · 8 = 720 počítá i „čísla“ jako 012. Trojmístných čísel s různými číslicemi je 9 · 9 · 8 = 648.
• Dvojí započítání. 10 · 9 = 90 podání rukou počítá každé dvakrát. Když na pořadí nezáleží, dělí se počtem pořadí jedné dvojice, 2! = 2.
• Sčítat, nebo násobit. Kroky, které nastávají zároveň (tričko a kalhoty), se násobí. Možnosti, z nichž nastane jen jedna (vlak, nebo autobus), se sčítají.
• 0! = 0. Ne, 0! = 1, a proto také `\binom{n}{0} = 1`.
• Kombinační číslo jako zlomek. `\binom{6}{2}` není 6 : 2 = 3, ale `\frac{6 \cdot 5}{2 \cdot 1} = 15`.

Příklady k procvičení

`\begin{aligned}\dbinom{12}{5} &= \dfrac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\\[8pt] &= \dfrac{95\,040}{120} = 792\end{aligned}`

`\begin{aligned}\dfrac{n(n-1)}{2} &= 45\\[8pt] n^2 - n - 90 &= 0\\[4pt] (n-10)(n+9) &= 0\end{aligned}`

`\dbinom{4}{2} \cdot \dbinom{6}{2} = 6 \cdot 15 = 90`

Kam dál

Desítky dalších příkladů s okamžitou kontrolou jsou v procvičování kombinací a variací. Kalkulačky, které ukážou postup:

• faktoriál a kombinační číslo,
• permutace, variace a kombinace,
• permutace s opakováním, variace s opakováním a kombinace s opakováním,
• Pascalův trojúhelník a binomická věta,
• všechny na jednom místě: kombinatorika.

Na kombinační čísla navazuje článek Pascalův trojúhelník s binomickou větou, na pravděpodobnost Opice píší Hamleta.