Variace s opakováním Variace k – té třídy 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. Příklad: Uveďte všechny 2členné variace s opakováním ze tří prvků a, b, c .
(a, a ) , (a, b ) , (a, c ) , (b, a ) , (b, b) , (b, c ) , (c, a ) , (c, b ) , (c, c ) . Poznámka: Variace k – té třídy (bez opakování) z n prvků existovaly pouze pro k ≤ n . Variace k – té třídy s opakováním z n prvků existují i pro k > n ; (a, a, b ) může být 3členná variace ze dvou prvků a, b . Jak určíme počet variací s opakováním z n prvků?
k -té
třídy
Každý člen uspořádané k – tice je možné vybrat n způsoby. Podle kombinatorického pravidla součinu je počet těchto uspořádaných k – tic roven součinu n ⋅ n ⋅ n ⋅ ... ⋅ n = n k . n – krát
Počet Vk´ (n ) všech variací k–té třídy s opakováním z n prvků je V ´k (n ) = n k .
Permutace opakováním Anagram je uskupení písmen, které vznikne přemístěním písmen slova nebo věty, jejíž obsah chceme utajit. V anagramu AABIIKKMNOORT resp. MINIKABAROTOK je ukryt název této kapitoly.
V minulosti jsme se zabývali permutacemi z n prvků, tj. uspořádanými n-ticemi, v nichž je každý z daných n prvků zastoupen právě jednou. Zkoumejme nyní uspořádané skupiny, v nichž je každý z daných n prvků, označme je a1 , a 2 , a3 , ..., a n , zastoupen aspoň jednou, a to v předem určeném počtu:
k1 -krát prvek a1 , k 2 -krát prvek a2 , ..., k n -krát prvek an . Vypišme pro ilustraci všechny tyto uspořádané skupiny pro případ dvou prvků a, b , v nichž se prvek a opakuje dvakrát a prvek b třikrát, tj. pro případ k1 = 2 , k 2 = 3 ; jde o tyto uspořádané pětice:
(a, a, b, b, b ) , (a, b, a, b, b) , (a, b, b, a, b) , (a, b, b, b, a ) , (b, a, a, b, b) , (b, a, b, a, b) , (b, a, b, b, a ) , (b, b, a, a, b) , (b, b, a, b, a ) , (b, b, b, a, a ) . Tyto skupiny jsou příkladem permutací s opakováním, přesněji permutací s opakováním ze dvou prvků, z nichž jeden se opakuje dvakrát a druhý třikrát. Permutace 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 aspoň jednou. Označíme-li k1 , k 2 ,..., k n , kolikrát se každý z daných
n prvků má opakovat, platí zřejmě k1 + k 2 + ... + k n ≥ n ; je-li k1 = k 2 = ... = k n = 1 , je k1 + k 2 + ... + k n = n , takže jde o uspořádané n -tice, v nichž je každý z n prvků právě jednou, tj. o permutace bez opakování.
Počet P (k1 , k 2 ,..., k n ) všech permutací s opakováním z n prvků, v nichž se jednotlivé prvky opakují k1 krát, k 2 -krát, ..., k n -krát, je.
P (k1 , k 2 ,..., k n ) =
(k1 + k 2 + ... + k n ) ! k1! ⋅ k 2 ! ⋅ ... ⋅ k n !
Poznámka: Postup, jak se došlo k předchozímu vzorci najdete v učebnici Matematika pro gymnázia – Kombinatorika, pravděpodobnost, statistika na straně 40 a schéma na straně 42. Všimněme si ještě zajímavého vztahu pro počet permutací s opakováním ze dvou prvků, z nichž jeden se opakuje k -krát a druhý (n − k ) -krát: P (k , n − k ) =
[k + (n − k )]! = n ! = n = C (n ) k k! ⋅ (n − k ) ! k! ⋅ (n − k ) ! k
Kombinace s opakováním Kombinace se někdy opakují, většinou ty nepříznivé.
Posledním druhem skupin, kterým se budeme zabývat, jsou skupiny, ve kterých nezáleží na pořadí a jejichž členy se mohou opakovat. Setkáváte se s nimi třeba tehdy, když k zaplacení určitého obnosu vybíráte z peněženky bankovky či mince. Kolik částek můžete např. zaplatit třemi mincemi, máte-li v peněžence korunové, dvoukorunové a pětikorunové mince, každý druh aspoň v pěti exemplářích? Každé částce odpovídá skupina tří mincí, v níž nezáleží na pořadí a v níž jednotlivé mince nemusí mít různou hodnotu; jde o tyto skupiny: 1, 1, 1;
1, 1, 2;
1, 1, 5;
1, 2, 2;
1, 2, 5
1, 5, 5;
2, 2, 2;
2, 2, 5;
2, 5, 5;
5, 5, 5
Z tohoto přehledu už snadno určíte, kolik a jaké částky můžete za daných podmínek zaplatit. Uvedené skupiny jsou příkladem kombinací s opakováním, přesněji k-členných kombinací s opakováním z n prvků. k-členná kombinace s opakováním z n prvků je neuspořádaná k-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše k-krát. Určíme nyní počet všech k-členných kombinací s opakováním z n prvků, který označíme C´k (n ) . Obecný postup si ukážeme na konkrétním příkladu z úvodu tohoto článku, kde je uveden výčet všech 3členných kombinací s opakováním ze tří prvků 1, 2, 5. Každou tuto kombinaci s opakováním zašifrujeme pomocí uspořádané skupiny teček a svislých čárek takto: Mysleme si, že máme tři přihrádky - první pro exempláře prvku 1, druhou pro exempláře prvku 2 a třetí pro exempláře prvku 5. Rozhraní mezi sousedními přihrádkami jsou znázorněna svislou čarou (potřebujeme dvě čáry: pro rozhraní mezi 1. a 2. přihrádkou a pro rozhraní mezi 2. a 3. přihrádkou). Pro každý z daných prvků zakreslíme do příslušné přihrádky tolik teček, kolikrát se v dané kombinaci tento prvek vyskytuje; nevyskytuje-li se v ní, zůstane příslušná přihrádka prázdná. Dostaneme tak toto přiřazení: 1, 1, 1 →
1, 5, 5 →
1, 1, 2 →
2, 2, 2 →
1, 1, 5 →
2, 2, 5 →
1, 2, 2 →
2, 5, 5 →
1, 2, 5 →
5, 5, 5 →
Je vidět, že každé 3členné kombinaci s opakováním ze tří prvků 1, 2, 5 odpovídá jediná uspořádaná pětice o třech tečkách a dvou čárkách a také obráceně. To však znamená, že počet C´3 (3) těchto kombinací s opakováním je roven počtu permutací s opakováním ze dvou prvků, z nichž jeden se opakuje třikrát a druhý dvakrát, tj. že platí C´3 (3) = P (3, 2 ) .
Půjde-li obecně o k -členné kombinace s opakováním z n prvků, přiřadíme stejným způsobem každé kombinaci uspořádanou skupinu s k tečkami a n − 1 čárkami, tj. permutaci s opakováním ze dvou prvků, z nichž jeden se opakuje k -krát a druhý (n − 1) -krát. Protože toto přiřazení je vzájemně jednoznačné, platí C´k (n ) = P (k , n − 1) =
[k + (n − 1)]! = (n + k − 1)! k!(n − 1)! k!(n − 1)!
⇒
(n + k − 1)! = (n + k − 1)! = n + k − 1 . k!(n − 1)! k![(n + k − 1) − k ]! k
n + k − 1 Počet C´k (n ) všech k-členných kombinací s opakováním z n prvků je C´k (n ) = k Příklady: 1) Určete počet všech trojúhelníků, z nichž žádné dva nejsou shodné a jejichž každá strana má velikost vyjádřenou některým z čísel n + 1, n + + 2, n + 3, ..., 2n, kde n je přirozené číslo. Kolik těchto trojúhelníků je a) rovnoramenných, b) rovnostranných? 2) V sáčku jsou červené, modré a zelené kuličky; kuličky téže barvy jsou nerozlišitelné. Určete, kolika způsoby lze vybrat pět kuliček, jestliže v sáčku je a) aspoň pět kuliček od každé barvy; b) pět červených, čtyři modré a čtyři zelené. 3) Určete počet kvádrů, jejichž velikosti hran jsou přirozená čísla nejvýše rovná deseti. Kolik je v tomto počtu krychlí? 4) V novinovém stánku je ke koupi deset druhů pohledů, přičemž každý druh je k dispozici v padesáti exemplářích. Určete, kolika způsoby lze zakoupit a) 15 pohledů; b) 51 pohledů; c) 8 různých pohledů. 5) Určete počet všech trojúhelníků, z nichž žádné dva nejsou shodné a jejichž každá strana má velikost vyjádřenou jedním z čísel 4, 5, 6, 7. 6) Ze všech bílých šachových figurek bez krále a dámy (tj. z osmi pěšců, dvou věží, dvou jezdců a dvou střelců) vybereme a) trojici, b) dvojici. Jaký je počet možností pro jejich složení? 7) V sadě 32 karet je každá z následujících karet čtyřikrát: sedmička, osmička, devítka, desítka, spodek, svršek, král, eso; karty téže hodnoty jsou přitom rozlišeny těmito "barvami": červená, zelená, žaludy, kule. Určete, kolika způsoby je možno vybrat čtyři karty, jestliže se a) rozlišují pouze "barvy" jednotlivých karet; b) rozlišují pouze hodnoty jednotlivých karet. 8) Apolloniovou úlohou se rozumí úloha sestrojit kružnici, která má tři z těchto vlastností: prochází daným bodem, dotýká se dané přímky, dotýká se dané kružnice. (Označíme-li tyto vlastnosti po řadě písmeny B, p, k, můžeme každou Apolloniovu úlohu zapsat pomocí trojice z těchto písmen; tak např. úloha Bkk značí úlohu sestrojit kružnici procházející daným bodem a dotýkající se dvou daných kružnic.) Určete počet všech Apolloniových úloh. 9) Kolik různých neuspořádaných trojic mohou dát počty ok na jednotlivých kostkách při vrhu třemi kostkami? (Jde o obvyklou kostku s jedním až šesti oky na jednotlivých stěnách.)
Úlohy k opakování 1) Určete, kolika způsoby lze přemístit písmena slova Mississippi; kolik z nich nezačíná písmenem M? 2) Určete počet všech trojúhelníků, z nichž žádné dva nejsou shodné a jejichž každá strana má jednu z velikostí daných čísly 4, 5, 6, 7, 8, 9. 3) Knihovna má pět regálů, do každého se vejde 20 knih. Určete, kolika způsoby lze do knihovny umístit 20 knih. [Návod: Myslete si, že regály jsou umístěny vedle sebe a každé dva sousední jsou odděleny stejným předmětem.] 4) V samoobsluze mají čtyři druhy kávy, každý po padesáti gramech. Určete, kolika způsoby lze koupit 250 gramů kávy, jestliže a) balíčků každého druhu mají dostatečný počet; b) od dvou druhů mají deset balíčků a od zbývajících dvou pouze po čtyřech balíčcích. 5) Určete, kolika způsoby lze z padesátihaléřových a korunových mincí zaplatit částku a) 6 Kč, b) 2 Kč, jsou-li oba druhy mincí k dispozici v dostatečném množství. [Návod: Každou částku lze zašifrovat pomocí písmen k (korunové mince) a p (dvě padesátihaléřové mince); např. čtyřem korunovým a čtyřem padesátihaléřovým mincím odpovídá zápis kkkkpp.]
6) Určete, kolika způsoby si mohou tři osoby rozdělit osm stejných jablek. [Návod: Každé rozdělení osmi jablek mezi tři osoby A, B, C lze zašifrovat pomocí neuspořádané osmice z těchto písmen; např. AAABBBBC značí příděl tří jablek osobě A, čtyř jablek osobě B a jednoho jablka osobě C.] 7) Určete, kolika způsoby si mohou tři osoby rozdělit čtyři stejná jablka a šest stejných hrušek. [Návod: Rozdělení jablek a hrušek jsou na sobě nezávislá, dále pak viz předchozí příklad.]
Příklady:Určete, kolik způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. Určete, v kolika z nich žádná dvojice sousedních písmen není tvořena dvěma písmeny A; žádná pětice sousedních písmen není tvořena pěti písmeny A. Určete počet všech čtyřciferných přirozených čísel dělitelných devíti, v jejich dekadickém zápisu nejsou jiné číslice než 0, 1, 2, 5, 7. Určete počet způsobů, jimiž lze umístit všechny bíle šachové figurky (král, dáma, 2 věže, 2 jezdci, 2 střelci, 8 pěšáků) na dvě pevně zvolené řady šachovnice 8 x 8; na libovolné dvě řady šachovnice 8 x 8. Určete počet všech deseticiferných přirozených čísel, jejichž ciferný součet je roven třem. Kolik z nich je sudých? Určete, kolika způsoby je možno přemístit písmena slova BATERKA tak, aby se souhlásky a samohlásky střídaly. [Návod: Na začátku a na konci musí být souhláska.] Ze sedmi kuliček, z nichž jsou čtyři modré (navzájem nerozlišitelné), jedna bílá, jedna červená a jedna zelená, máme vybrat a položit do řady vedle sebe pět kuliček. Kolika způsoby to lze provést?
