kombinatorika

Příklad 52

Vlajka je složena ze tří různobarevných pruhů. K dispozici jsou barvy bílá, červená, modrá, zelená, žlutá. Kolik vlajek lze sestavit, a kolik z nich nemá zelený pruh uprostřed?

Řešení	Ukázat>
Všech možných vlajek je $V_3(5).$ Vlajek, které mají zelený pruh uprostřed je $V_2(4).$ Takže vlajek, které nemají zelený pruh uprostřed je $V_3(5)-V_2(4)=48.$

Příklad 53

Vlajka je složena ze tří různobarevných pruhů. K dispozici jsou barvy bílá, červená, modrá, zelená. Kolik vlajek lze sestavit, a kolik z nich nemá bílý pruh uprostřed?

Řešení	Ukázat>
Všech vlajek je $V_3(4).$ Vlajek bez bílého pruhu uprostřed je $V_3(4)-V_2(3)=18.$

Příklad 224

Kolik je 3-ciferných čísel s různými ciframi obsahujících cifry 0, 2, 3, 4, 5?

Řešení	Ukázat>
Všech čísel je $V_3(5)$ . Čísel začínajících nulou je $V_2(4)$ . Takže hledaných čísel je $V_3(5)-V_2(4)=48$

Příklad 232

Kolik existuje anagramů slova ABRAKADABRA,
(a) které začínají a končí písmenem B?
(b) které začínají a končí písmenem A?
(c) které začínají nebo končí písmenem B?

Řešení	Ukázat>
(a) $\dfrac{9!}{5!\cdot2!}$ (b) $\dfrac{9!}{3!\cdot2!\cdot2!}$ (c) Všech anagramů je $\dfrac{11!}{5!\cdot2!\cdot2!}$ , anagramů, které nezačínají, ani nekončí písmenem B je ${9\choose2}\cdot\dfrac{9!}{5!\cdot2!}$ (počet rozmístění písmen B na vnitřní pozice krát počet promíchání ostatních písmen) Takže hledaných slov je $\dfrac{11!}{5!\cdot2!\cdot2!}-{9\choose2}\cdot\dfrac{9!}{5!\cdot2!}$

Řešení

Ukázat>

(a)

$\dfrac{9!}{5!\cdot2!}$
(b)

$\dfrac{9!}{3!\cdot2!\cdot2!}$
(c) Všech anagramů je

$\dfrac{11!}{5!\cdot2!\cdot2!}$ , anagramů, které nezačínají, ani nekončí písmenem B je

${9\choose2}\cdot\dfrac{9!}{5!\cdot2!}$ (počet rozmístění písmen B na vnitřní pozice krát počet promíchání ostatních písmen)
Takže hledaných slov je

$\dfrac{11!}{5!\cdot2!\cdot2!}-{9\choose2}\cdot\dfrac{9!}{5!\cdot2!}$

Příklad 267

Kolika způsoby můžeme 10 lidí, mezi nimiž je Adam a Běta, posadit do řady tak, aby Adam a Běta neseděli vedle sebe?

Řešení	Ukázat>
Všech rozmístění je $10!$ Usazení, při nichž Adam a Běta sedí vedle sebe je $2\cdot9!$ Takže hledaných usazení je $10!-2\cdot9!=8\cdot9!$

Příklad 268

Kolika způsoby je možné na šachovnici $8\times8$ vybrat tři pole tak, aby neležela všechna v témže sloupci?

Řešení	Ukázat>
Všech výběrů je ${64\choose3}.$ Výběrů, při nichž jsou všechna pole v jenom sloupci, je $8\cdot{8\choose3}.$ Takže počet hledaných výběrů je ${64\choose3}-8\cdot{8\choose3}$

Příklad 269

Kolika způsoby je možno na čtvercové šachovnici s 64 poli vybrat 3 pole tak, aby všechna tři pole neměla stejnou barvu?

Řešení	Ukázat>
Všech výběrů je ${64\choose3}.$ Výběrů, při nichž mají všechna pole stejnou barvu, je $2\cdot{32\choose3}.$ Takže počet hledaných výběrů je ${64\choose3}-2\cdot{32\choose3}$

Příklad 270

Kolik existuje 6-ti písmenných slov vytvořených z písmen anglické abecedy, která obsahují aspoň jedno písmeno A?

Řešení	Ukázat>
$26^6-25^6$

Příklad 271

Kolik 10-ti ciferných čísel obsahuje aspoň 2 stejné číslice?

Řešení	Ukázat>
Všech deseticiferných čísel je $9\cdot10^9.$ Deseticiferných čísel, v nichž se cifry neopakují, je $9\cdot9!$ Takže počet hledaných čísel je $9\cdot10^9-9\cdot9!$

Příklad 272

Definujeme "platné slovo" jako řetězec písmen (anglická abeceda A až Z, opakování povoleno) délky pět a obsahujících alespoň jednu samohlásku (A, E, I, O, U, Y). Kolik "platných slov" existuje?

Řešení	Ukázat>
$26^5-20^5$

Příklad 273

Z číslic 0, 0, 0, 0, 2, 2, 8, 8 vytvoříme všechna osmimístná kladná čísla. Kolik takových čísel existuje?

Řešení	Ukázat>
$\dfrac{8!}{4!\cdot2!\cdot2!}-\dfrac{7!}{3!\cdot2!\cdot2!}$

Příklad 274

Kolik existuje anagramů slova MISSISSIPPI, které neobsahují PP?

Řešení	Ukázat>
$\dfrac{11!}{4!\cdot4!\cdot2!}-\dfrac{10!}{4!\cdot4!}$

Příklad 275

Kolik existuje anagramů slova MISSISSIPPI, které neobsahují III ani IIII?

Řešení	Ukázat>
Všech anagramů je $\dfrac{11!}{4!\cdot4!\cdot2!}.$ Určíme počet anagramů. které obsahují III ale ne IIII: Souhlásky _M_S_S_S_S_P_P_ můžeme uspořádat $\dfrac{7!}{4!\cdot2!}$ způsoby. Vznikne 8 mezer, z nichž vybereme 2 pro umístění III a I. To lze ${8\choose2}$ způsoby. Na každou vybranou dvojici míst můžeme III a I umístit dvěma způsoby. Celkem $\dfrac{7!}{4!\cdot2!}\cdot{8\choose2}\cdot2$ Určíme počet anagramů, které obsahují IIII: $\dfrac{7!}{4!\cdot2!}\cdot8$ Hledaných anagramů je $\dfrac{11!}{4!\cdot4!\cdot2!}-\dfrac{7!}{4!\cdot2!}\cdot{8\choose2}\cdot2-\dfrac{7!}{4!\cdot2!}\cdot8.$

Řešení

Ukázat>

Všech anagramů je

$\dfrac{11!}{4!\cdot4!\cdot2!}.$
Určíme počet anagramů. které obsahují III ale ne IIII: Souhlásky _M_S_S_S_S_P_P_ můžeme uspořádat

$\dfrac{7!}{4!\cdot2!}$ způsoby. Vznikne 8 mezer, z nichž vybereme 2 pro umístění III a I. To lze

${8\choose2}$ způsoby. Na každou vybranou dvojici míst můžeme III a I umístit dvěma způsoby. Celkem

$\dfrac{7!}{4!\cdot2!}\cdot{8\choose2}\cdot2$
Určíme počet anagramů, které obsahují IIII:

$\dfrac{7!}{4!\cdot2!}\cdot8$
Hledaných anagramů je

$\dfrac{11!}{4!\cdot4!\cdot2!}-\dfrac{7!}{4!\cdot2!}\cdot{8\choose2}\cdot2-\dfrac{7!}{4!\cdot2!}\cdot8.$

Příklad 276

Kolik existuje anagramů jména KUALA LUMPUR (jeden znak je mezera), které tvoří dvě slova?

Řešení	Ukázat>
$\dfrac{11!}{3!\cdot2!\cdot2!}-2\cdot\dfrac{10!}{3!\cdot2!\cdot2!}$ (všechna slova - slova s mezerou na kraji)

Příklad 277

Kolik je různých přerovnání řady čísel $1\dots9,$ ve kterých čísla 1 a 2 nejsou vedle sebe?

Řešení	Ukázat>
$9!-2\cdot8!$

666 příkladů z kombinatoriky

Odčítání 1