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