kombinatorika

Příklad 541

Kolika způsoby lze seřadit do fronty 5 Čechů, 4 Slováky a 3 Maďary tak, aby všichni příslušníci žádného národa netvořili jeden souvislý blok? Příslušníci jednotlivých národů jsou nerozlišitelní. (Tedy pět Čechů v řadě za sebou stát nemůže, ale například dva ano.)

Řešení	Ukázat
Všech front je $12!$ Češi vedle sebe: $8!5!$ Slováci vedle sebe: $9!4!$ Maďaři vedle sebe: $10!3!$ Č+S: $5!5!4!$ Č+M: $6!5!3!$ S+M: $7!4!3!$ Č+S+M: $5!4!3!3!$ Podle PIE: $12!-(8!5!+9!4!+10!3!-5!5!4!-6!5!3!-7!4!3!+5!4!3!3!)$

Příklad 542

Tři děti si z krabice vytáhly 7 různých hraček. Kolika způsoby se o ně můžou podělit tak, aby každé mělo alespoň jednu hračku?

Řešení	Ukázat
Kombinace s opakováním - ${6\choose4}$

Příklad 543

Čtyřmístný kód obsahuje čislice 0-9. Platí, že 1. a 4. číslice je sudá a součet 2. a 3. číslice je roven 5. Kolik takových kódů existuje?

Řešení	Ukázat
$5$ (1. pozice) $\times5$ (4. pozice) $\times6$ (2. pozice) $=150$

Příklad 544

V poslední řadě v učebně sedí 11 studentů a čekají, že dostanou zadání zkouškové písemky. Zadávajícímu zůstalo 5 kusů zadání varianty A, 2 kusy varianty B a po jednom zadání variant C,D,E,F. Kolik je možností, jak rozdat zadání písemek mezi studenty v poslední řadě, jestliže je samozřejmě, že studenti sedící vedle sebe musí mít vždy různé varianty?

Řešení	Ukázat
Nejprve libovolně rozmístíme písmena bez Áček - to lze $\dfrac{6!}{2!}$ způsoby. Tím vznikne 7 míst pro umístění Áček $BBCDEF$ Z nich musíme vybrat pět pozic, což lze ${7\choose5}$ způsoby, takže může vzniknout $\dfrac{6!}{2!}\cdot{7\choose5}$ uspořádání. Mezi takto vzniklými uspořádáními jsou ale taková, v nichž jsou 2 Béčka vedle sebe. $\fbox{BB}CDEF*$ Těch je $5!\cdot{6\choose5}.$ Celkem $\dfrac{6!}{2!}\cdot{7\choose5}-5!\cdot{6\choose5}$ možností.

Řešení

Ukázat

Nejprve libovolně rozmístíme písmena bez Áček - to lze

$\dfrac{6!}{2!}$ způsoby. Tím vznikne 7 míst pro umístění Áček

$*B*B*C*D*E*F*$

Z nich musíme vybrat pět pozic, což lze

${7\choose5}$ způsoby, takže může vzniknout

$\dfrac{6!}{2!}\cdot{7\choose5}$ uspořádání.
Mezi takto vzniklými uspořádáními jsou ale taková, v nichž jsou 2 Béčka vedle sebe.

$*\fbox{BB}*C*D*E*F*$

Těch je

$5!\cdot{6\choose5}.$
Celkem

$\dfrac{6!}{2!}\cdot{7\choose5}-5!\cdot{6\choose5}$ možností.

Příklad 545

Kolika různými způsoby můžeme nabarvit 6 identických bílých kuliček jednou ze čtyř barev? (Každá kulička musi být nabarvena.)

Řešení	Ukázat
Kombinace s opakováním - ${9\choose6}$

Příklad 546

Kolika různými způsoby můžeme nabarvit 6 očíslovaných kuliček jednou ze čtyř barev? (Každá kulička musi být nabarvena a čísla jsou pod barvou stále vidět - jsou vyrytá.)

Řešení	Ukázat
Variace s opakováním $4^6$

Příklad 547

Kolika způsoby lze obarvit některé (tj. aspoň jednu) z deseti bílých nerozlišitelných kuliček jednou ze čtyř barev (mezi nimiž není bílá barva)?

Řešení	Ukázat
Přidáme si "prázdnou barvu". Pak rozdělujeme 10 kuliček do pěti kategorií. To lze ${14\choose10}$ způsoby. Odečteme jednu možnost, kdy jsou všechny kuličky obarvené "prázdnou barvou". Celkem ${14\choose10}-1$ způsobů.

Příklad 548

Kolik existuje desetimístných řetězců sestavených ze dvou nul, tří jedniček a pěti dvojek?

Řešení	Ukázat
Permutace s opakováním $\dfrac{10!}{2!3!5!}$

Příklad 549

Kolik existuje desetimístných čísel ve trojkové soustavě která jsou zapsaná pomocí dvou nul, tří jedniček a pěti dvojek?

Řešení	Ukázat
Stejné jako příklad 548, ale musíme odečíst situace, kdy je na začátku nula. $\dfrac{10!}{2!3!5!}-\dfrac{9!}{3!5!}$

Příklad 550

Kolik osmibitových řetězců obsahuje aspoň 3 jedničky?

Řešení	Ukázat
Všech řetězců je $2^8$ 0 jedniček ${8\choose0}$ 1 jednička ${8\choose1}$ 2 jedničky ${8\choose2}$ Celkem $2^8-\left({8\choose0}+{8\choose1}+{8\choose2}\right)$

Příklad 551

Adam, Bára a Cirda chtějí do divadla, hodlají sedět hned v prvni řadě, kde je 13 sedadel a chtějí sedět vedle sebe? Kolika způsoby se tam mohou rozesadit?

Řešení	Ukázat
Místo pro prostředního můžeme vybrat 11-ti způsoby, uspořádání je pak vždy $3!$ . Celkem $11\cdot3!$

Příklad 552

Určete, kolik existuje šesticiferných čísel, v jejichž dekadickém zápisu jsou tři cifry sudé a tři cifry liché.

Řešení	Ukázat
Všechny možnosti: ${6\choose3}$ (pozice pro lichá čísla) $\times5^3$ (lichá čísla) $\times5^3$ (sudá čísla) Nula na začátku: ${5\choose3}$ (pozice pro lichá čísla) $\times5^3$ (lichá čísla) $\times5^2$ (sudá čísla) Celkem ${6\choose3}\cdot5^6-{5\choose3}\cdot5^5$

Příklad 553

(a) Kolik různých slov, i bez významu, je možno vytvořit přeskládáním písmen ve slově "LOKOMOTIVA"?
(b) Kolik je mezí nimi takových slov, v nichž nejsou žádná dvě stejná písmena vedle sebe.
(c) A v kolika slovech se pravidelně střídají souhlásky a samohlásky?

Řešení	Ukázat
(a) $\dfrac{10!}{3!}$ (b) Písmena bez "O" můžeme uspořádat $7!$ způsoby. Tím vznikne 8 mezer, z nichž vybereme 3. To lze ${8\choose3}$ způsoby. Celkem: $7!\cdot{8\choose3}$ (c) Souhlásky jsou po jedné, počet uspořádání je $5!$ Samohlásky jsou s opakováním $\dfrac{5!}{3!}$ Dále dvě možnosti - začínáme souhláskou, nebo samohláskou. Celkem $2\cdot5!\cdot\dfrac{5!}{3!}$

Příklad 554

Kolika způsoby lze rozdělit 15 stejných čokolád mezi 4 děti tak, aby každé dítě mělo maximálně 5 kusů čokolád.

Řešení	Ukázat
Představíme si, že každému dáme 5 čokolád, celkem tedy 20. Musíme proto 5 čokolád ubrat. Budeme rozdělovat 5 "mínus čokolád" do čtyř kategorií - kombinace s opakováním: ${5+4-1\choose5}={8\choose5}$ způsobů.

Příklad 555

Sadař zakoupil 4 jabloně, 4 hrušně a 4 švestky. Chce je zasadit do tří řad po čtyřech stromech. Jednotlivé stromy téhož druhu při tom nebude od sebe rozlišovat. Určete, kolika způsoby to může udělat, jestliže právě jednu řadu chce osázet stromy stejného druhu.

Řešení	Ukázat
Aspoň jedna řada stejného druhu: $3$ (řada) $\times3$ (druh) $\times\dfrac{8!}{4!\cdot4!}$ (zbytek) V tom jsou ale i situace, kdy jsou všechny tři řady osázené jedním druhem. Těchto situací je $3!,$ ale každou jsme počítali třikrát. Celkem $3\cdot3\cdot\dfrac{8!}{4!\cdot4!}-3\cdot3!$

Příklad 556

Kolik různých 4-písmenných slov můžeme vytvořit z písmen slova "PARALLELOGRAM"? Každé písmeno můžeme použít nejvýše tolikrát, kolikrát se ve slově "PARALLELOGRAM" vyskytuje.

Řešení	Ukázat
(a) 4 různá písmena: $V_4(8)=\dfrac{8!}{4!}$ (b) 2+1+1: ${3\choose1}{7\choose2}\cdot\dfrac{4!}{2!}$ (c) 2+2: ${3\choose2}\cdot\dfrac{4!}{2!2!}$ (d) 3+1: ${2\choose1}{7\choose1}\cdot\dfrac{4!}{3!}$ Celkem $\displaystyle \dfrac{8!}{4!}+{3\choose1}{7\choose2}\cdot\dfrac{4!}{2!}+{3\choose2}\cdot\dfrac{4!}{2!2!}+{2\choose1}{7\choose1}\cdot\dfrac{4!}{3!}$

Příklad 557

Máme pytlík s 12 kuličkami, z nichž 3 jsou bílé, 4 žluté a 5 modrých, přičemž kuličky stejné barvy mezi sebou rozlišujeme. Vytáhneme 5 kuliček. V kolika případech budeme mít od každé barvy alespoň jednu kuličku?

Řešení	Ukázat
Všech možností je ${12\choose5}.$ Žádná bílá: ${9\choose5}$ Žádná žlutá: ${8\choose5}$ Žádná modrá: ${7\choose5}$ Žádná bílá ani žlutá: ${5\choose5}$ Podle PIE celkem ${12\choose5}-{9\choose5}-{8\choose5}-{7\choose5}+{5\choose5}$

Příklad 558

Máme 15 různých knížek. Kolika různými způsoby je můžeme uspořádat na dvě poličky, přičemž na každé poličce musí být aspoň 1 kniha?

Řešení	Ukázat
$14\cdot15!$

Příklad 559

Pruh látky je rozdělený na 20 čtvercových částí. Čtverce se mají obarvit každý jednou ze tří barev (žlutá, zelená, modrá) tak, aby vedle sebe ležící čtverce měly různou barvu. (a) Kolika způsoby se to dá udělat? (b) Kolika způsoby se to dá udělat, když požadujeme, aby aspoň jedna deska byla modrá?

Řešení	Ukázat
(a) $3\cdot2^{19}$ (b) $3\cdot2^{19}-2$

Příklad 560

U stolu sedí 10 lidí, pět na jedné a pět na protější straně. Mezi nimi jsou tři manželské páry. Každý manželský pár chce sedět proti sobě. Kolika způsoby se můžou usadit?

Řešení	Ukázat
${5\choose3}$ (místa pro páry) $\times3!$ (uspořádání párů) $\times2^3$ (proházení párů) $\times4!$ (uspořádání zbytku) Celkem ${5\choose3}\times3!\times2^3\times4!$

666 příkladů z kombinatoriky

Komplexní úlohy VII