kombinatorika

Příklad 581

Určete počet všech přirozených čtyřciferných čísel, v jejichž dekadickém zápisu se vyskytuje jedna nula, jedna dvojka a ostatní cifry bez opakování.

Řešení	Ukázat
${3\choose1}$ (pozice pro nulu) $\times{3\choose1}$ (pozice pro dvojku) $\times{8\choose2}$ (výběr zbylých dvou číslic) $\times2$ (záměna pořadí zbylých čísel).

Příklad 582

V restauraci podávají pět druhů nápojů: pivo, kávu, minerálku, rum a slivovici. Kolika způsoby lze v této restauraci vypít tři nápoje, jestliže nepijete stejný druh nápoje vícekrát a nepřihlížíme k pořadí, ve kterém byli vypity?

Řešení	Ukázat
${5\choose3}$

Příklad 583

Kolik 5-tipísmenných slov (řetězců) můžeme vytvořit z písmen slova "CALCULUS", když žádné písmeno nepoužijeme vícekrát, než se vyskytuje ve slově "CALCULUS"?

Řešení	Ukázat
(a) 5 různých písmen: $5!$ (b) 2 stejná+3 různá: ${3\choose1}{4\choose3}\cdot\dfrac{5!}{2!}$ (c) 2+2 stejná + 1 jiné: ${3\choose2}{3\choose1}\cdot\dfrac{5!}{2!2!}$ Celkem $5!+{3\choose1}{4\choose3}\cdot\dfrac{5!}{2!}+{3\choose2}{3\choose1}\cdot\dfrac{5!}{2!2!}$

Příklad 584

Kolik existuje čtyřpísmenných řetězců vytvořených z písmen anglické abecedy, ve kterých se vyskytují současně písmena "J" a "K"?

Řešení	Ukázat
Podle PIE: $26^4-2\cdot25^4+24^4$

Příklad 585

Určete počet šestipísmenných slov tvořených písmeny "A", "B" a "C", ve kterých se nevyskytuje podslovo "AAB".

Řešení	Ukázat
Všech možných slov je $3^6$ Slov obsahujících podslovo "AAB" je $4\cdot 3^3$ (Podslovo může bý na 4 pozicích, zbylé tři pozice libovolně obsazené) Slovo "AABAAB" je v předchozím případu započteno dvakrát. Celkem $3^6-4\cdot3^3+1$

Příklad 586

Kolik různých smíšených trojic můžeme vybrat ze skupiny pěti mužů a pěti žen?

Řešení	Ukázat
$2{5\choose2}{5\choose1}$

Příklad 587

Kolika způsoby si může 8 lidí, mezi nimiž je Alice a Bob, stoupnout vedele sebe do řady, když Alice nechce stát vedle Boba?

Řešení	Ukázat
$8!-2\cdot7!$

Příklad 588

Kolika způsoby si může 8 lidí, mezi nimiž je Alice a Bob, sednout kolem kulatého stolu, když Alice nechce sedět vedle Boba?

Řešení	Ukázat
$7!-2\cdot6!$

Příklad 589

Máme čtyři karty, na kterých jsou napsaná čísla 1, 2, 3, 4 (každé jednou). Vybereme tři karty a položíme vedle sebe. Vznikne tak trojciferné číslo. Kolik takto můžeme vytvořit různých trojciferných čísel dělitelných třemi?

Řešení	Ukázat
Můžeme vybrat 4 různé trojice $\{1,2,3\},$ $\{1,2,4\},$ $\{1,3,4\}$ a $\{2,3,4\}.$ Jenom první a poslední trojice má součet dělitelný třemi. Každá permutace těchto dvou trojic bude vyhovovat. Můžeme sestavit $2\cdot3!$ požadovaných čísel.

Příklad 590

Ve třídě je 30 studentů, kteří sedí v patnácti lavicích (v každé lavici dva vedle sebe). Kolika způsoby můžeme usadit studenty do lavic, když dva konkrétně určení studenti nesmí sedět vedle sebe v lavici?

Řešení	Ukázat
Prvního určeného studenta můžeme usadit na 30 míst. Druhého na 28 míst. Zbylých 28 studentů můžeme umístit libovolně. Je $30\cdot28\cdot28!$ způsobů, jak studenty usadit.

Příklad 591

Sněhurka bydlí u 12 trpaslíků. Chce uložit jejich 12 stejných čepiček do dvou šuplíků. Kolika způsoby to může provést, pokud chce, aby v každém šuplíku byly alespoň 3 čepičky.

Řešení	Ukázat
${7\choose6}$

Příklad 592

15 přátel jede na výlet třemi různými automobily. Do každého auta se vejde 5 lidí a všech 15 lidí může řídit. Kolika různými způsoby se mohou rozdělit do automobilů, když v automobile rozlišujeme jen řidiče a ostatní sedadla nerozlišujeme?

Řešení	Ukázat
výběr řidičů $\times$ rozmístění řidičů do aut $\times$ výběr pasažérů do 1. auta $\times$ výběr pasžérů do 2. auta ${15\choose3}\cdot3!\cdot{12\choose4}\cdot{8\choose4}$

Příklad 593

Ze všech šachových figurek kromě krále a dámy (tj. z 8 pěšců, 2 věží, 2 jezců a dvou střelců ve 2 barvách) vybereme trojici. Kolik existuje možností?

Řešení	Ukázat
Druh figurky představuje kategorii. Tj. do osmi kategorií rozdělujem 3 "předměty". To jde ${8+3-1\choose3}$ způsoby. Musíme odečíst situace, kdy budeme mít 3 jezdce, 3 věže nebo 3 střelce. Celkem ${10\choose3}-6$

Příklad 594

Mějme osm kuliček. Dvě červené, dvě zelené, dvě žluté a dvě modré kuličky. Kuličky stené barvy považujeme za nerozlišitelné. Kolik barevně různých trojic kuliček lze sestavit?

Řešení	Ukázat
Stejný postup jako příklad 593. ${4+3-1\choose3}-4={6\choose3}-4$

Příklad 595

Kolik různých čtyřciferných čísel lze vytvořit z číslic 1,3,3,3,5,5,5,5,5?

Řešení	Ukázat
Číslo buď obsahuje jedničku, nebo ne. Pokud obsahuje jedničku, pak musíme na tři místa vybírat ze dvou možností, tj. celkem $2^3$ a jedničku můžeme doplnit čtyřmi způsoby. Tedy $4\cdot2^3$ čísel. Pokud číslo neobsahuje jedničku, vybíráme na čtyři místa ze dvou možností, tj. $2^4$ možností. Ale trojek není dost na číslo 3333, takže tuto možnost musíme odečíst. Tedy $2^4-1$ čísel. Celkem $4\cdot2^3+2^4-1$

Řešení

Ukázat

Číslo buď obsahuje jedničku, nebo ne.
Pokud obsahuje jedničku, pak musíme na tři místa vybírat ze dvou možností, tj. celkem

$2^3$ a jedničku můžeme doplnit čtyřmi způsoby. Tedy

$4\cdot2^3$ čísel.
Pokud číslo neobsahuje jedničku, vybíráme na čtyři místa ze dvou možností, tj.

$2^4$ možností. Ale trojek není dost na číslo 3333, takže tuto možnost musíme odečíst. Tedy

$2^4-1$ čísel.
Celkem

$4\cdot2^3+2^4-1$

Příklad 596

Kolika způsoby můžeme umístit do tří obálek 15 pětistovek a 10 stovek pokud musí každá obsahovat alespoň jednu bankovku? Musíme použít všechny bankovky. Bankovky stejného druhu považujeme za nerozlišitelné a obálky jsou rozlišitelné}

Řešení	Ukázat
Podle PIE: ${17\choose15}{12\choose10}$ (všechna rozdělení) $-3{16\choose15}{11\choose10}$ (aspoň jedna prázdná) $+3{15\choose0}{10\choose0}$ (dvě prázdné)

Příklad 597

Kolik existuje anagramů slova "TINKERER", ve kterých sousedí dvě, ale ne tři samohlásky?

Řešení	Ukázat
Souhlásky můžeme uspořádat $\dfrac{5!}{2!}$ způsoby. Tím vznikne 6 mezer, z nichž vybereme dvě ${6\choose2}$ způsoby. Na vybrané mezery můžeme umístit "dvojhlásku" a samohlásku dvěma způsoby. Samohlásky pak na pozicích můžeme permutovat $\dfrac{3!}{2!}$ způsoby. Celkem $\dfrac{5!}{2!}\cdot{6\choose2}\cdot2\cdot\dfrac{3!}{2!}$ anagramů

Příklad 598

Kolik existuje 11-tipísmenných slov vytvořených z písmen anglické abecedy, která obsahují podslovo "FRED"? Slova nemusí dávat žádný smysl.

Řešení	Ukázat
Slov s aspoň jedním podslovem "FRED" je $8\cdot26^7.$ Mezi nimi jsou i slova s dvěma podslovy "FRED". Těch je ${5\choose2}\cdot26^3.$ Protože tato slova jsme v prvním případě počítali dvakrát, musíme je jednou odečíst. Existuje $8\cdot26^7-{5\choose2}\cdot26^3$ slov s požadovanou vlastností.

Příklad 599

Mám balíček 52 kartiček, z toho 13 zelených, 13 modrých, 13 červených a 13 žlutých. Kartičky stejné barvy jsou nerozlišitelné. Vytáhnu 5 karet a položím vedle sebe do řady. Kolik různých barevných řad může vzniknout, když každá barva musí být zastoupena alespoň jednou?

Řešení	Ukázat
Pokud je každá barva aspoň jednou, musí být některá barva dvakrát. Pro každou barvu, která je dvakrát, existuje $\dfrac{5!}{2!}$ uspořádání. Celkem $4\cdot\dfrac{5!}{2!}$

Příklad 600

Na poličce stojí 12 různých knih. Určete, kolika způsoby můžete vybrat 5 knih tak, že žádné dvě nestojí vedle sebe.

Řešení	Ukázat
Představíme si, že vybrané knihy obarvíme bíle, nevybrané černě (je jich 7). Hledáme počet černobílých vzorů, v nichž nejsou dvě bílé vedle sebe. 7 černých vytváří 8 pozic, z nichž vybíráme 5. ${8\choose5}$

666 příkladů z kombinatoriky

Komplexní úlohy IX