Variace, permutace a kombinace s opakováním
Úlohy
Odkazy na úlohy podle témat:
Variace s opakováním
Permutace s opakováním
Kombinace s opakováním
Souhrnné úlohy
Variace s opakováním
Úloha 3.1
Vypište všechny dvoučlenné variace s opakováním ze tří prvků
a, b, c.
Výsledek:
(a, a), (a, b), (a, c)
(b, a), (b, b), (b, c)
(c, a), (c, b), (c, c)
Úloha 3.2
Kolik různých pěticiferných čísel lze vytvořit z číslic 2 a 5?
Výsledek:
V'(5, 2) = 25 = 32
Úloha 3.3
Kolik různých pěticiferných čísel lze sestavit z číslic 0, 2, 3?
Výsledek:
V'(5, 3) − V'(4, 3) = 35 − 34 = 243 − 81 = 162
Úloha 3.4
Kolik slov skládajících se z p písmen
(tj. slov "délky p") lze utvořit z abecedy, která má
n písmen?
Výsledek: V'(p, n)
= np
Úloha 3.5
Kufřík má heslový zámek, který se otevře, když na každém z pěti
kotoučů nastavíme správnou číslici; těchto číslic je na každém kotouči devět.
Určete největší možný počet pokusů, které je nutno provést, chceme-li kufřík
otevřít, jestliže jsme zapomněli heslo.
Výsledek:
V'(5, 9) = 95 = 59 049
Úloha 3.6
Kolik znaků, které jsou složeny z jednoho až čtyř signálů,
může obsahovat Morseova abeceda? (Signálem rozumíme "tečku" nebo "čárku".)
Výsledek: 30
V'(1, 2) + V'(2, 2) + V'(3, 2) + V'(4, 2)
= 21 + 22 + 23 + 24
= 2 + 4 + 8 + 16 = 30
Úloha 3.7
Na panelu je r žárovek, z nichž každá může svítit
zeleně, žlutě nebo červeně. Určete, kolik různých stavů může panel signalizovat.
Kolik žárovek bychom potřebovali, kdybychom chtěli rozlišit 50 různých stavů?
Výsledek:
V'(r, 3) = 3r
4
Úloha 3.8
Kolik různých státních poznávacích značek pro automobily
lze použít, je-li k dispozici 21 písmen a 10 číslic a značka se skládá
ze tří písmen na prvních třech místech a dále ze čtyř číslic?
Výsledek:
V'(3, 21) · V'(4, 10) = 213 · 104
= 92 610 000
Úloha 3.9
Určete počet čtyřciferných přirozených čísel dělitelných čtyřmi,
v nichž se vyskytují pouze číslice 1, 2, 3, 4, 5.
Přirozené číslo je dělitelné čtyřmi, pokud je jeho poslední dvojčíslí
dělitelné čtyřmi.
Výsledek: 125
Možná poslední dvojčíslí jsou: 12, 24, 32, 44, 52; je jich tedy pět.
Na místě stovek a tisíců může stát libovolná z uvedených pěti číslic, jedná se
tedy o dvojčlenné variace s opakováním z pěti prvků.
5 · V'(2, 5) = 5 · 52 = 125
Úloha 3.10
Určete, z kolika prvků lze utvořit 1 024 pětičlenných
variací s opakováním.
Výsledek: 4
Úloha 3.11
V množině přirozených čísel řešte rovnici:
V'(2, x) − x · V'(2, 3) = 10
Výsledek: {10}
V'(2, x) − x · V'(2, 3) = 10
x2 − x · 32 = 10
x2 − 9x − 10 = 0
(x − 10)(x + 1) = 0
x1 = 10, x2 = −1;
číslo (−1) nepatří do množiny přirozených čísel, řešením je tedy pouze číslo 10.
Permutace s opakováním
Úloha 3.12
Určete, kolika způsoby je možné srovnat do řady 2 šedé, 3 modré
a 4 černé kostky.
Výsledek: P'(2, 3, 4) = 1 260
Úloha 3.13
Určete počet uspořádání těchto šesti prvků:
a, a, a, b, b, c.
Výsledek: P'(3, 2, 1) = 60
Úloha 3.14
Určete kolika způsoby lze přemístit písmena slova Mississippi.
Kolik z nich nezačíná písmenem M?
Výsledky:
| P'(1, 4, 4, 2) = |
11! 4! 4! 2! |
= 34 650; |
| P'(1, 4, 4, 2) − P'(4, 4, 2) = 34 650 − 3 150
= 31 500 |
Úloha 3.15
Určete počet všech pěticiferných přirozených čísel,
jež lze sestavit z číslic 5 a 7, má-li v každém z nich být číslice 5
a) právě třikrát;
b) nejvýše třikrát;
c) aspoň třikrát.
Výsledky:
a) P'(3, 2) = 10
b) P'(3, 2) + P'(2, 3) + P'(1, 4) + P'(5) = 10 + 10 + 5 + 1 = 26
c) P'(3, 2) + P'(4, 1) + P'(5) = 10 + 5 + 1 = 16
Úloha 3.16
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?
Výsledky: 55;
46
Deseticiferné číslo, jehož ciferný součet je 3, je např. číslo
1 101 000, 1 000 200
nebo
3 000 000.
Každé takové číslo se skládá buď ze tří jedniček a sedmi nul, nebo z jedné jedničky, jedné dvojky
a osmi nul, nebo z jedné trojky a devíti nul. Určíme počty čísel v jednotlivých skupinách:
a) čísla složená ze tří jedniček a sedmi nul:
Na místě milionů je nenulové číslo, tedy číslo 1.
Ostatní dvě jedničky a sedm nul můžeme rozmístit libovolně. Počet takových čísel je
P'(2, 7).
b) čísla složená z jedné jedničky, jedné dvojky a osmi nul:
Na místě milionů je nenulové číslo, tedy číslo 1 nebo číslo 2. Druhé nenulové číslo a osm nul
můžeme rozmístit libovolně. Počet takových čísel je
2 · P'(1, 8).
c) čísla složená z jedné trojky a devíti nul:
Na místě milionů je nenulové číslo, tedy číslo 3, ostatní cifry jsou nuly. Takové číslo je jen jedno.
Sečtením počtů v jednotlivých skupinách dostaneme celkový výsledek:
| P'(2, 7) + 2 · P'(1, 8) + 1 = |
9! 2! 7! |
+ 2 · | 9! 1! 8! |
+ 1 = 36 + 18 + 1 = 55 |
Při počítání sudých čísel postupujeme podobně:
a) čísla složená ze tří jedniček a sedmi nul:
Na místě milionů je nenulové číslo, tedy číslo 1, na místě jednotek je sudé číslo, tedy číslo 0.
Ostatní dvě jedničky a šest nul můžeme rozmístit libovolně. Počet takových čísel je
P'(2, 6).
b) čísla složená z jedné jedničky, jedné dvojky a osmi nul:
Na místě milionů je nenulové číslo, tedy číslo 1 nebo číslo 2. Pokud je na místě milionů číslo 1,
můžeme číslo 2 a osm nul rozmístit libovolně (číslo 2 je sudé). Pokud je místě milionů číslo 2, tak na místě jednotek
je nula. Jedničku a sedm nul můžeme rozmístit libovolně.
Počet takových čísel je
P'(1, 8) + P'(1, 7).
c) čísla složená z jedné trojky a devíti nul:
Na místě milionů je nenulové číslo, tedy číslo 3, ostatní cifry jsou nuly. Takové číslo je jen jedno a je sudé,
proto ho můžeme započítat do výsledku.
Sečtením počtů v jednotlivých skupinách dostaneme celkový výsledek:
| P'(2, 6) + P'(1, 8) + P'(1, 7) + 1 = |
8! 2! 6! |
+ | 9! 1! 8! |
+ | 8! 1! 7! |
+ 1 = 28 + 9 + 8 + 1 = 46 |
Úloha 3.17
Ze sedmi kuliček, z nichž čtyři jsou modré (navzájem nerozlišitelné),
jedna bílá, jedna červená a jedna zelená, máme vybrat a položit do řady pět kuliček.
Kolika způsoby to lze provést?
Výsledek: 135
Úkol rozdělíme na několik disjunktních podúkolů a mezivýsledky potom sečteme:
1) Mezi pěti vybranými kuličkami budou všechny čtyři modré kuličky:
Počet rozmístění pěti kuliček, kde jsou čtyři modré a jedna jiná, je
P'(4, 1) = 5. Tento počet vynásobíme třemi, protože
zbývající kulička může být buď bílá, červená nebo zelená, tedy máme tři způsoby,
jak ji vybrat. Celkem je proto 3 · 5 = 15 takových pětic.
2) Mezi pěti vybranými kuličkami jsou tři modré kuličky:
Počet rozmístění pěti kuliček, kde jsou tři modré a zbylé dvě jiné, navzájem různé,
je P'(3, 1, 1) = 20. Tento počet opět vynásobíme třemi,
protože zbývající dvě kuličky můžeme vybrat třemi způsoby: bílá + červená,
bílá + zelená, červená + zelená. Těchto pětic je tedy
20 · 3 = 60.
3) Mezi pěti vybranými kuličkami jsou jen dvě modré kuličky:
K nim musíme přidat všechny tři zbývající kuličky jiných barev. Počet rozmístění
takových pětic je P'(2, 1, 1, 1) = 60.
4) Další možnost není.
Tyto mezivýsledky sečteme (podle kombinatorického pravidla součtu) a dostáváme:
3 · P'(4, 1) + 3 · P'(3, 1, 1) + P'(2, 1, 1, 1) = 15 + 60 + 60 = 135.
* Úloha 3.18
Určete počet všech čtyřciferných čísel dělitelných devíti,
která můžeme napsat užitím číslic 0, 1, 2, 5, 7.
Přitom se mohou číslice v čísle i opakovat.
Číslo je dělitelné devíti, jestliže je jeho ciferný součet dělitelný devíti.
Výsledek: 54
Číslo je dělitelné devíti, jestliže je jeho ciferný součet dělitelný devíti.
V našem případě přicházejí v úvahu pouze ciferné součty 9 nebo 18, protože
ciferný součet 27 ani vyšší násobek devíti nelze pomocí daných číslic vytvořit.
Jakými způsoby je možné v našem případě vytvořit součet 9,
jestliže nás zatím nezajímá pořadí sčítanců?
9 = 7 + 2 + 0 + 0,
9 = 7 + 1 + 1 + 0,
9 = 5 + 2 + 2 + 0,
9 = 5 + 2 + 1 + 1.
Podobně pro součet 18 najdeme
18 = 7 + 7 + 2 + 2,
18 = 7 + 5 + 5 + 1.
U jednotlivých součtů zjistíme, kolika způsoby z nich lze sestavit
čtyřciferné číslo:
Kolik čtyřciferných čísel lze napsat, máme-li užít číslice 7, 2, 0, 0?
Jde o počet čtyřciferných permutací s opakováním ze tří prvků, v nichž se jeden
prvek opakuje dvakrát. Takových permutací je
| P'(1, 1, 2) = |
4! 2! |
= 12. |
Z tohoto počtu musíme vyloučit čtyřciferné zápisy, které mají na místě tisíců nulu.
Těch je právě tolik, kolik lze sestavit trociferných zápisů z čísel 7, 2, 0
(bez opakování).
Těch je
P(3) = 3! = 6. Zápisu
9 = 7 + 2 + 0 + 0 tedy odpovídá
12 − 6 = 6 čtyřciferných čísel.
Podobně zjistíme, kolik čtyřciferných čísel odpovídá ostatním zápisům:
| 9 = 7 + 1 + 1 + 0 | ... |
| P'(1, 2, 1) − P'(1, 2) = |
4! 2! |
− | 3! 2! |
= 12 − 3 = 9 |
|
| 9 = 5 + 2 + 2 + 0 | ... |
| P'(1, 2, 1) − P'(1, 2) = |
4! 2! |
− | 3! 2! |
= 12 − 3 = 9 |
|
| 9 = 5 + 2 + 1 + 1 | ... |
|
| 18 = 7 + 7 + 2 + 2 | ... |
| P'(2, 2) = |
4! 2! · 2! |
= 6 |
|
| 18 = 7 + 5 + 5 + 1 | ... |
|
Teď už zbývá jen sečíst všechny mezivýsledky:
6 + 9 + 9 + 12 + 6 + 12 = 54.
Z daných číslic se dá sestavit celkem 54 čtyřciferných čísel
dělitelných devíti.
Úloha 3.19
Určete počet způsobů, jimiž lze na šachovnici 8 × 8 rozmístit
všechny figurky šachové hry (bílý král, bílá dáma, 2 bílí střelci, 2 bílí jezdci,
2 bílé věže, 8 bílých pěšců + totéž černé barvy).
K 32 figurkám přidejte 32 shodných prvků, třeba korunových mincí.
Výsledek:
| P'(1, 1, 2, 2, 2, 8, 1, 1, 2, 2, 2, 8, 32) = |
64! (2!)6 (8!)2 32! |
Úloha 3.20
Určete, kolika způsoby lze na černá políčka šachovnice
8 × 8
rozmístit 12 bílých (nerozlišitelných) a 12 černých (nerozlišitelných) kostek tak,
aby toto rozmístění bylo symetrické podle středu šachovnice.
Na černá políčka zvolené poloviny šachovnice rozmístíme 6 bílých a 6 černých kostek
a další 4 nerozlišitelné předměty, čímž je postavení zbývajících bílých a černých kostek
jednoznačně určeno.
Výsledek:
P'(6, 6, 4) = 1 681 680
Kombinace s opakováním
Úloha 3.21
V obchodě mají tři druhy sirupu: jahodový, malinový a pomerančový.
Určete počet všech možností nákupu pěti lahví sirupu v tomto obchodě.
Výsledek:
| K'(5, 3) = |
( | 3 + 5 − 1
5 | ) |
= |
( | 7
5 | ) |
= |
7! 5! (7 − 5)! |
= 21 |
Úloha 3.22
Určete, kolika způsoby si mohou tři osoby rozdělit osm (stejných) jablek.
Výsledek:
K'(8, 3) = 45
Úloha 3.23
Určete počet kvádrů, jejichž velikosti hran jsou přirozená
čísla nejvýše rovná deseti. Kolik je v tomto počtu krychlí?
Výsledky: K'(3, 10) = 220, krychlí je 10
Úloha 3.24
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.
Výsledek: K'(3, 6) − 3 = 53
Délkám stran trojúhelníka vzhledem k trojúhelníkové nerovnosti nevyhovují následující tři trojice čísel:
4–4–8,
4–4–9,
4–5–9.
Musíme je proto odečíst od celkového počtu trojic, které lze
sestavit ze šesti zadaných čísel.
Na pořadí čísla v trojici nezáleží, počet trojic je proto
K'(3, 6) = 56.
Trojic, které odpovídají velikostem stran trojúhelníka, je tedy
56 − 3 = 53.
Úloha 3.25
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) dvojici,
b) trojici.
Jaký je počet možností pro jejich složení?
Výsledky:
a) K'(2, 4) = 10
b) K'(3, 4) − 3 = 17
Úloha 3.26
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
Bpp značí úlohu sestrojit kružnici procházející daným bodem a dotýkající se
dvou daných přímek.)
Určete počet všech Apolloniových úloh.
Výsledek: K'(3, 3) = 10
Úloha 3.27
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.)
Výsledek: K'(3, 6) = 56
Úloha 3.28
V železničním depu je dvacet osobních, sedm lůžkových a pět poštovních vozů.
Kolik různých souprav s pěti vozy je možno v tomto depu sestavit, jestliže nezáleží
na pořadí vozů v soupravě?
Výsledek: K'(5, 3) = 21
Úloha 3.29
Klenotník vybírá do prstenu tři drahokamy; k dispozici má
tři rubíny, dva smaragdy a pět safírů. Kolika způsoby může tento výběr provést,
považujeme-li kameny téhož druhu za stejné?
Výsledek: K'(3, 3) − 1 = 9
Úloha 3.30
Určete, kolika různými způsoby lze rozdělit 15 korunových mincí
mezi 10 dětí, jestliže
a) neklademe žádná omezení;
b) každé dítě dostane alespoň jednu minci;
c) nejstarší dítě dostane alespoň dvě mince.
Výsledky:
| a) K'(15, 10) = |
( | 10 + 15 − 1
15 | ) |
= | 24! 15! · 9! |
= 1 307 504; |
| b) K'(5, 10) = |
( | 10 + 5 − 1
5 | ) |
= | 14! 5! · 9! |
= 2 002; |
| c) K'(13, 10) = |
( | 10 + 13 − 1
13 | ) |
= | 22! 13! · 9! |
= 497 420 |
Souhrnné úlohy
Úloha 3.31
Je dáno slovo ABRAKADABRA. Určete:
a) počet všech možných pořadí z daných písmen;
b) počet všech pořadí, v nichž nejsou vedle sebe dvě písmena A;
c) počet všech pořadí, v nichž není vedle sebe pět písmen A.
Výsledky:
/AAAAA BB D K RR/
| a) P'(5, 2, 1, 1, 2) = |
11! 5! 2! 1! 1! 2! |
= 83 160 |
| b) |
( | 7
5 | ) |
· P'(2, 1, 1, 2) = 3 780 |
| c) P'(5, 2, 1, 1, 2) − P'(1, 2, 1, 1, 2) |
= 81 900 |
Úloha 3.32
Určete počet způsobů, jimiž lze umístit všechny bílé šachové figurky
(král, dáma, 2 věže, 2 jezdci, 2 střelci, 8 pěšáků)
a) na dvě pevně zvolené řady šachovnice 8 × 8;
b) na libovolné dvě řady šachovnice 8 × 8.
Výsledky:
| a) P'(1, 1, 2, 2, 2, 8) = |
16! 1! 1! 2! 2! 2! 8! |
= |
16! 8 · 8! |
= 64 864 800 |
| b) |
( | 8
2 | ) |
· P'(1, 1, 2, 2, 2, 8) |
Úloha 3.33
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.
Výsledek:
| P(4) · P'(2, 1) = 4! · |
3! 2! |
= 24 · 3 = 72 |
Úloha 3.34
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ů.
Výsledky:
| a) K'(15, 10) = |
( | 24
15 | ) |
= 1 307 504 |
| b) K'(51, 10) − 10 = |
( | 60
51 | ) |
− 10 = 14 783 142 650 |
Úloha 3.35
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.
(V jednotlivých regálech záleží jen na pořadí knih, nezáleží na jejich posunutí.)
Představte si regály tak, že jsou umístěny vedle sebe a každé dva
sousední jsou odděleny stejným předmětem.
Výsledek: 23!
Hledáme počet různých pořadí 20 knih a čtyř přepážek, tedy celkem 24 předmětů.
Počet všech pořadí 24 různých předmětů je P(24) = 24!. Protože jsou přepážky
nerozlišitelné, je každých P(4) = 4! pořadí stejných. Proto musíme počet všech pořadí
vydělit 4!:
Úloha 3.36
V samoobsluze mají čtyři druhy kávy v balíčcích 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.
Výsledky:
a) K'(5, 4) = 56
b) K'(5, 4) − 2 = 54
Úloha 3.37
Určete, kolika způsoby lze rozdat 18 (různých) knih třem žákům A, B, C
tak, aby A a B dohromady měli dvakrát více knih než C.
Vyberte 6 knih pro C a zbývajících 12 rozdělte mezi A a B.
Úloha 3.38
Tři děvčata − Anna, Dana a Hana − se mají rozdělit
o sedm stejných růží a pět stejných tulipánů. Kolika způsoby to lze provést?
Výsledek: K'(7, 3) · K'(5, 3) = 756
Úloha 3.39
Určete, kolika způsoby si mohou tři osoby rozdělit
čtyři stejná jablka a šest stejných hrušek.
Výsledek:
K'(4, 3) · K'(6, 3) = 420