Variace, permutace a kombinace s opakováním
Variace, permutace a kombinace s opakováním se od variací, permutací a kombinací bez opakování liší tím, že prvky se mohou ve výběru opakovat. Ostatní vlastnosti zůstávají stejné: u variací a permutací záleží na pořadí, v jakém prvky vybíráme, u kombinací na pořadí prvků nezáleží. Permutace s opakováním stejně jako permutace bez opakování určují pořadí všech zadaných prvků.
Zápis se většinou odlišuje apostrofem, tedy např. \(V'(2, 3)\)označuje počet dvoučlenných variací s opakováním ze tří prvků. Toto značení se používá také na těchto stránkách.
Variace s opakováním
Definice
\(k\)-členná variace s opakováním z n prvků je uspořádaná \(k\)-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše \(k\)-krát.
U variací bez opakování bylo \(k\) omezeno velikostí \(n\), které
udávalo počet různých prvků, ze kterých jsme vybírali.
U variací s opakováním má \(n\) trochu jiný význam: znamená počet druhů,
např. počet barev, cifer nebo třeba písmen, ze kterých můžeme opakovaně vybírat.
Proto může být \(k > n\).
Na ukázku jsou zde vypsané všechny tříčlenné variace s opakováním ze dvou prvků
\(a, b\):
\[(a,a,a), (a,a,b), (a,b,a), (a,b,b), (b,a,a), (b,a,b), (b,b,a), (b,b,b).\]
Počet \(V'(k,n)\) všech \(k\)-členných variací s opakováním z \(n\) prvků můžeme odvodit pomocí kombinatorického pravidla součinu. Nejprve určíme počet \(V'(3,4)\) všech tříprvkových variací s opakováním ze čtyř prvků, potom postup zobecníme.
Mějme \(4\) krabice s pastelkami. V každé krabici je neomezeně mnoho pastelek jedné barvy a žádné dvě krabice neobsahují pastelky stejné barvy. Máme tedy například jednu krabici se žlutými pastelkami, jednu s červenými, jednu se zelenými a jednu s modrými pastelkami. Kolik různých trojic pastelek lze vytvořit?
První pastelku můžeme vzít z libovolné krabice. Máme tedy čtyři možnosti, jak ji vybrat.
Druhou pastelku můžeme také vzít z libovolné krabice. Máme tedy zase čtyři možnosti, jak ji vybrat.
Stejně tak třetí pastelku, takže také pro ni máme čtyři možnosti, jak ji vybrat.
Volby jsou navzájem nezávislé, proto podle kombinatorického pravidla součinu existuje
celkem \(4 \cdot 4 \cdot 4 = 4^3 = \boldsymbol{64}\) různých trojic pastelek, vybraných ze čtyř krabic.
(Kliknutím na pastelku změníte její barvu v pořadí žlutá, červená, zelená, modrá.)
Postup se teď pokusíme zobecnit. Místo čtyř krabic budeme mít \(n\) krabic
a místo tří pastelek budeme vybírat \(k\) pastelek;
\(n\) a \(k\) jsou libovolná přirozená čísla.
První pastelku tentokrát můžeme vzít z libovolné z \(n\) krabic,
máme tedy \(n\) možností, jak ji vybrat. Stejně tak máme
\(n\) možností, jak vybrat druhou pastelku, třetí pastelku,
…, \(k\)-tou pastelku. Podle kombinatorického pravidla
součinu tedy existuje \(n \cdot n \cdot n \cdot \ldots \cdot n\) (celkem se \(n\) opakuje \(k\)-krát),
tj. \(n^k\)\(k\)-tic pastelek, vybraných z \(n\) krabic.
Počet \(V'(k,n)\) všech \(k\)-členných variací s opakováním z \(n\) prvků je \[V'(k,n) = n^k.\]
Příklad
Určete počet pěticiferných přirozených čísel, složených
pouze z cifer \(6, 7, 8, 9\).
Kolik z nich je menších než \(90\,000\)?
Řešení
V prvním případě se jedná o pětičlenné variace s opakováním ze čtyř prvků (\(k=5\)5, \(n=4\)), jejich počet je proto \(V'(5,4) = 4^5 = \boldsymbol{1\,024}\).
Chceme-li určit počet takových přirozených čísel, která se skládají pouze
z cifer \(6, 7, 8, 9\) a jsou menší než \(90\,000\),
můžeme k výpočtu použít kombinatorické pravidlo součinu: na místě desetitisíců může stát
cifra \(6, 7\), nebo \(8\), máme tedy tři možnosti výběru; na dalších čtyřech místech může stát
libovolná z cifer \(6, 7, 8, 9\), počet možností jejich výběru je proto
\(V'(4,4) = 4^4 = 256\).
Celkem je tedy \(3 \cdot 256 = \boldsymbol{768}\) pěticiferných přirozených čísel menších než
\(90\,000\), složených pouze z cifer \(6, 7, 8, 9\).
Příklad
Určete počet všech podmnožin \(k\)-prvkové množiny.
Řešení
Prvky dané \(k\)-prvkové množiny označíme čísly
\(1, 2, 3, \ldots, k\)a každé její podmnožině přiřadíme uspořádanou
\(k\)-tici složenou z nul
a jedniček takto: Je-li ve zvolené podmnožině prvek označený číslem \(j\)(\(1 \leq j \leq k\)), přiřadíme jí uspořádanou \(k\)-tici,
jejímž \(j\)-tým členem je jednička; jestliže tento prvek v podmnožině není,
bude na \(j\)-tém místě příslušné uspořádané \(k\)-tice nula.
Např. podmnožině \(\{2, 3, 5\}\) množiny
\(\{1, 2, 3, 4, 5, 6\}\) je tak přiřazena uspořádaná šestice
\((0, 1, 1, 0, 1, 0)\), podmnožině
\(\{1, 6\}\) uspořádaná šestice
\((1, 0, 0, 0, 0, 1)\) atd.
Je zřejmé, že toto přiřazení je vzájemně jednoznačné, neboť také obráceně
každé takovéto uspořádané \(k\)-tici odpovídá jediná podmnožina
\(k\)-prvkové množiny. To však znamená, že \(k\)-prvková
množina má právě tolik podmnožin, kolik existuje uspořádaných \(k\)-tic
složených z nul a jedniček; protože tyto \(k\)-tice jsou vlastně
\(k\)-člennými variacemi s opakováním ze dvou prvků, máme výsledek:
Počet podmnožin \(k\)-prvkové množiny je
\(V'(k,2) = \boldsymbol{2^k}\).
