kombinatorika

Příkad 241

Kolik značek Morseovy abecedy je možné vytvořit, sestavujeme-li tečky a čárky do skupin o jednom až čtyřech prvcích?

Řešení	Ukázat
$2^1+2^2+2^3+2^4=30$

Příkad 242

K sestavení výboru můžeme použít 5 Demokratů a 8 Republikánů. Přitom má být sestaven tak, aby se počet Demokratů a Republikánů ve výboru lišil co nejméně.
(a) Kolika způsoby můžeme sestavit sedmičlenný výbor?
(b) Kolika způsoby můžeme sestavit dva výbory, jeden sedmičlenný a druhý pětičlenný, když nikdo nesmí být v obou výborech současně?

Řešení	Ukázat
(a) 4D+3R nebo 3D+4R, takže ${5\choose4}\cdot{7\choose3}+{5\choose3}\cdot{7\choose4}$ (b) Vybereme lidi do jednoho výboru. Zbytek jde automaticky do druhého výboru. ${7\choose3}\cdot{5\choose2}$

Příkad 243

Z podnikového večírku odjíždí několik zaměstnanců - 11 žen, 12 mužů a ředitel oddělení. Pro 8 lidí přijedou 2 taxíky (každý pobere 4 cestující). Kolika způsoby je možné do aut vybrat zaměstnance tak, aby v jednom autě jely pouze ženy a v druhém jeli pouze muži. Ostatní jedou tramvají. Ředitel může jet v kterémkoliv taxíku, nebo může jet tramvají s ostatními.

Řešení	Ukázat
4M+4Ž nebo 3MŘ+4Ž nebo 4M+3ŽŘ, takže ${12\choose4}\cdot{11\choose4}+{12\choose3}\cdot{11\choose4}+{12\choose4}\cdot{11\choose3}$

Příkad 244

Kolik různých přirozených čísel je možno utvořit z číslic 0, 1, 2, 3, 4, smí-li každá tato číslice být v čísle obsažena nejvýš jednou?

Řešení	Ukázat
$4+4\cdot4+4\cdot4\cdot3+4\cdot4\cdot3\cdot2+4\cdot4\cdot3\cdot2\cdot1$

Příkad 245

Kolika způsoby můžeme ze sedmi mužů a čtyř žen vybrat šestičlennou skupinu, tak aby v ní byly:
(a) alespoň 2 ženy?
(b) nejvýše 2 ženy?

Řešení	Ukázat
(a) ${4\choose2}\cdot{7\choose4}+{4\choose3}\cdot{7\choose3}+{4\choose4}\cdot{7\choose2}$ (b) ${4\choose0}\cdot{7\choose6}+{4\choose1}\cdot{7\choose5}+{4\choose2}\cdot{7\choose4}$

Příkad 246

Test se skládá z 5 otázek, každá maximálně za 20 bodů. Student získal postupně 10, 5, 18, 5 a 2 body, celkem 40 bodů. Kolika způsoby muže opravující přidat studentovi 5 bodů (body se nemohou dělit)?

Řešení	Ukázat
Ke třetí otázce může přidat 0, 1, nebo 2 body. Zbylé body pak do ostatních otázek může přidat libovolně (kombinace s opakováním). ${8\choose5}+{7\choose4}+{6\choose3}$

Příkad 247

Kolik existuje šestimístných přirozených čísel, která mají ve svém zápisu nejvýše jednu cifru 1?

Řešení	Ukázat
Čísel, ve kterých není žádná jednička, je $8\cdot9^5.$ Čísla, ve kterých je jedna jednčka, jsou dvojího typu. (a) jednička je na prvním místě - $9^5$ čísel (b) jednička není na prvním místě - $5\cdot8\cdot9^4$ Celkem $8\cdot9^5+9^5+5\cdot8\cdot9^4$

Příkad 249

Máme slovo "NEPŘIMĚŘENOST".
(a) Kolika způsoby mohou být uspořádána písmena v tomto slově?
(b) Kolik různých uspořádání existuje, když skupina písmen "PŘI" musí být pohromadě a v daném pořadí?
(c) Kolik různých třípísmenných množin můžeme vytvořit, když použijeme pouze písmena v daném slově?

Řešení	Ukázat
(a) $\dfrac{13!}{2!\cdot2!\cdot2!}$ (b) $\dfrac{11!}{2!\cdot2!}$ (c) Množiny jsou dvojího typu (i) dvě stejné + 1 jiná, nebo (ii) tři různé (i) ${3\choose2}\cdot{8\choose1}$ (ii) ${10\choose3}$ Celkem ${3\choose2}\cdot{8\choose1}+{10\choose3}$

Příkad 250

Určete počet anagramů slova "COCACOLA" a která začínají i končí souhláskou.

Řešení	Ukázat
Slova jsou tří typů. (a) C-L -> $\dfrac{6!}{2!\cdot2!\cdot2!}$ slov (b) C-C -> $\dfrac{6!}{2!\cdot2!}$ slov (c) L-C -> $\dfrac{6!}{2!\cdot2!\cdot2!}$ slov Celkem $\dfrac{6!}{2!\cdot2!\cdot2!}+\dfrac{6!}{2!\cdot2!}+\dfrac{6!}{2!\cdot2!\cdot2!}$

Příkad 251

Uvažujme všechna celá čísla od 1 do 1000. Rozdělíme je na 2 skupiny. Do první dáme čísla, v jejichž zápise se vyskytuje aspoň jedna cifra 1, do druhé ostatní čísla. Která skupina obsahuje víc čísel?

Řešení	Ukázat
Čísel, která neobsahují cifru 1, je $8+8\cdot9+\cdot8\cdot9\cdot9=728.$ Vzhledem k tomu, že všech čísel je 1000, je čísel ve druhé skupině více.

Příkad 252

Máme čtyři Demokraty a šest Republikánů. Kolika způsoby můžeme sestavit pětičlenný výbor, ve kterém musí být aspoň dva Demokraté a aspoň dva Republikáni?

Řešení	Ukázat
${5\choose2}\cdot{6\choose3}+{5\choose3}\cdot{6\choose2}$

Příkad 253

Ve výboru je 7 žen a 6 mužů. Chceme z nich vybrat pětičlenný podvýbor.
(a) Kolika způsoby to můžeme udělat?
(b) Kolika způsoby to můžeme udělat, pokud v podvýboru musí být aspoň dvě ženy a aspoň dva muži?

Řešení	Ukázat
(a) ${13\choose5}$ (b) ${7\choose2}\cdot{6\choose3}+{7\choose3}\cdot{6\choose2}$

Příkad 264

Klenotník vybírá do prstenu tři drahokamy. K dispozici má tři rubíny, dva smaragdy, pět safírů a čtyři kousky ametystu. Kolika způsoby může tento výběr provést, považujeme-li kameny téhož druhu za stejné?

Řešení	Ukázat
Ve výběru je (a) nula smaragdů: ${3+3-1\choose3}=10$ (b) jeden smaragd: ${2+3-1\choose2}=6$ (c) dva smaragdy: ${3\choose1}=3$ Celkem $10+6+1=19$ výběrů.

Příkad 265

Kolik binárních osmibitových řetězců začíná "00" nebo končí "1"?

Řešení	Ukázat
Vhodné řetězce můžeme rozdělit na 4 skupiny. (a) $00-----0$ , $2^5$ řetězců (b) $1------1$ , $2^6$ řetězců (c) $00-----1$ , $2^5$ řetězců (d) $01-----1$ , $2^5$ řetězců Celkem existuje $5\cdot2^5$ požadovaných řetězců.

Příkad 266

Určete počet všech trojciferných přirozených čísel dělitelných čtyřmi, v nichž se vyskytují pouze cifry $\{1;2;3;4\}.$

Řešení	Ukázat
Čísla musí končit jedním z dvojčíslí $--12$ , $--24$ , $--32$ , $--44$ . Od každého dvojčíslí existuje $4^2$ možností jak je doplnit. Celkem $4\cdot4^2=4^3$ čísel.