kombinatorika

Příklad 561

Kolik je čtyřbitových řetězců, které neobsahují tři nuly hned po sobě?

Řešení	Ukázat
$2^4-3$

Příklad 562

Kolik je pětibitových řetězců, které obsahují tři nuly po sobě?

Řešení	Ukázat
3 nuly a 2 jedničky: 3 možnosti 4 nuly a 1 jednička: 4 možnosti (0000 - jedničku můžeme umístit na místě *) 5 nul : 1 možnost Celekm 3+4+1=8 řetězců

Příklad 563

Kolik je všech čtyřciferných čísel vytvořených z číslic 0, 1, 2, 5, 8, 9 větších než 8552? Cifry se mohou opakovat.

Řešení	Ukázat
první cifra 9: $6^3$ první cifra 8 a druhá není 5: $2\cdot6^2$ první dvě cifry 85 třetí není 5: $2\cdot6$ první tři cifry 855: $3$ Celkem $6^3+2\cdot6^2+2\cdot6+3$

Příklad 564

Kolik existuje desetiznakových hesel, která obsahují aspoň jedno písmeno anglické abecedy a aspoň jednu cifru?

Řešení	Ukázat
$36^{10}-10^{10}-26^{10}$

Příklad 565

Kolik existuje anagramů slova "GRACEFUL", ve kterých žádné dvě samohlásky nesousedí?

Řešení	Ukázat
$5!$ (přerovnání souhlásek) $\times{6\choose3}$ (místa pro samohlásky) $\times3!$ (přerovnání souhlásek)

Příklad 566

Kolik existuje anagramů slova "DAUGHTER", ve kterých žádné dvě samohlásky nesousedí?

Řešení	Ukázat
Stejné jako příklad 565. $5!\cdot{6\choose3}\cdot3!$

Příklad 567

Osm identických předmětů rozdělujeme čtyřem lidem mezi nimiž je Adam. Kolika způsoby to lze udělat, když Adam musí dostat lichý počet předmětů?

Řešení	Ukázat
Adam má jeden: ${9\choose7}$ (kombinace s opakováním) Adam má tři: ${7\choose5}$ Adam má pět: ${5\choose3}$ Adam má sedm: ${3\choose1}$ Celkem $\displaystyle \sum_{i=0}^3{2i+3\choose2i+1}$

Příklad 568

V senátu USA je 100 senátorů, přičemž vždy dva jsou ze stejného státu Unie (USA má 50 států). Kolika způsoby je možné sestavit 4 členný výbor, kde musí býti alespoň jedna dvojice senátorů z téhož státu?

Řešení	Ukázat
Všech výborů je ${100\choose4}$ Výborů, v nichž nejsou dva ze stejného státu je ${50\choose4}\cdot2^4$ Celkem ${100\choose4}-{50\choose4}\cdot2^4$

Příklad 569

Kolik existuje anagramů slova "DEFINITION", ve kterých není písmeno "I" na první ani na poslední pozici.

Řešení	Ukázat
Všech: $\dfrac{10!}{3!2!}$ "I" na začátku: $\dfrac{9!}{2!2!}$ "I" na konci: $\dfrac{9!}{2!2!}$ "I" na začátku i na konci: $\dfrac{8!}{2!}$ Celkem podle PIE $\dfrac{10!}{3!2!}-2\cdot\dfrac{9!}{2!2!}+\dfrac{8!}{2!}$

Příklad 570

V cukrárně se prodávají 4 druhy zákusků: špičky, trubičky, větrníky a laskonky. Určete, kolika způsoby je možno nakoupit 7 zákusků tak, abychom nekoupili od jednoho druhu více než 3 zákusky.

Řešení	Ukázat
Všech možných nákupů je ${4+7-1\choose7}={10\choose7}$ $\|A_s\|$ je počet nákupů, kde jsou aspoň 4 špičky. Pak je $\|A_s\|={4+3-1\choose3}={6\choose3}.$ Stejný počet je i pro ostatní zákusky. A není možnost, že bychom počet překročili u více zákusků najednou. Celkem ${10\choose7}-4\cdot{6\choose3}.$

Příklad 571

Do kopce vedou 4 cesty a 1 lanovka.
(a) Kolik je všech možností pro cestu tam a zpět?
(b) Kolik je všech možností pro cestu tam a zpět takových, aby cesta zpět nebyla stejná jako cesta tam?
(c) Kolik je všech možností pro cestu tam a zpět, při kterých jedeme aspoň jednou lanovkou?

Řešení	Ukázat
(a) $5\cdot5=25$ (b) $5\cdot4=20$ (c) $5\cdot5-4\cdot4=9$ (všechny možné cesty mínus ty bez lanovky)

Příklad 572

Šest chlapců a dvě dívky se mají postavit do řady tak, aby nenastala situace, že na obou krajích řady současně stojí dívky. Kolik je možných řad?

Řešení	Ukázat
Všech řad, které můžou vytvořit je $8!$ V nich jsou ale i řady, kdy jsou na krajích dívky - těchto řad je $2\cdot6!$ (1. holka vlevo, druhá vpravo, nebo obráceně, proto ta dvojka) Celkem $8!-2\cdot6!$

Příklad 573

Součet 20 lze získat sčítáním pouze čísel 2 a 5 (v součtu mohou být i jen samá čísla 2, nebo i jen samá čísla 5). Kolik je takových součtů, když záleží na pořadí sčítanců?

Řešení	Ukázat
Číslo 20 je sudé. Sudé číslo získáme jakou součet dvou sudých čísel, nebo dvou lichých čísel. Protože z dvojky liché číslo neuděláme, musíme z pětky udělat sudé číslo. To v dané úloze jde jen třemi způsoby (a) 0 pětek: jedna možnost (b) dvě pětky: dvě pětky a 5 dvojek lze zaranžovat $\frac{7!}{2!5!}=21$ způsoby (c) čtyři pětky: jedna možnost Celkem $1+21+1=23$ různých součtů.

Řešení

Ukázat

Číslo 20 je sudé. Sudé číslo získáme jakou součet dvou sudých čísel, nebo dvou lichých čísel. Protože z dvojky liché číslo neuděláme, musíme z pětky udělat sudé číslo. To v dané úloze jde jen třemi způsoby
(a) 0 pětek: jedna možnost
(b) dvě pětky: dvě pětky a 5 dvojek lze zaranžovat

$\frac{7!}{2!5!}=21$ způsoby
(c) čtyři pětky: jedna možnost
Celkem

$1+21+1=23$ různých součtů.

Příklad 574

Šest chlapců a šest děvčat (mezi nimi Emil, Felix, Gertruda a Hanka) si chtějí zatančit. Jaký je počet způsobů, jak mohou utvořit šest (smíšených) párů, pokud Emil nechce tančit s Gertrudou a Hanka chce tančit s Felixem?

Řešení	Ukázat
Aby sestavili 6 párů, musí se každému splnit jeho přání. Takže: Felix má jedinou možnost - musí tančit s Hankou. Emil už si může vybrat ze čtyř holek (Gertrudu nechce a Hanka je obsazená) 1. kluk si může taky vybrat ze 4. holek - (H je obsazená, obsazená je ta, kterou si vybral E, ale přibyla G) 2. kluk má na výběr už jenom 3 3. kluk má na výběr už jenom 2 4. kluk má na "výběr" už jen jednu. Celkem $4\cdot4!$

Řešení

Ukázat

Aby sestavili 6 párů, musí se každému splnit jeho přání. Takže:
Felix má jedinou možnost - musí tančit s Hankou.
Emil už si může vybrat ze čtyř holek (Gertrudu nechce a Hanka je obsazená)
1. kluk si může taky vybrat ze 4. holek - (H je obsazená, obsazená je ta, kterou si vybral E, ale přibyla G)
2. kluk má na výběr už jenom 3
3. kluk má na výběr už jenom 2
4. kluk má na "výběr" už jen jednu.
Celkem

$4\cdot4!$

Příklad 575

Kolik existuje jedenácticiferných čísel, ve kterých jsou použité všechny cifry (a tudíž právě jedna cifra dvakrát)?

Řešení	Ukázat
První cifra může být vybrána 9-ti způsoby. Nyní jsou dvě možnosti (a) První cifra je použita dvakrát. Pak zbylé cifry můžeme permutovat $10!$ způsoby. (b) První cifra je použita jednou. Opakující se cifru vybereme 9-ti způsoby, jejich umístění pak ${10\choose2}$ způsoby. Zbytek můžeme permutovat $8!$ způsoby. Celkem $9\cdot\left(10!+9\cdot{10\choose2}\cdot8!\right)$

Příklad 576

Do deseti očíslovaných obálek vložíme 6 jednokorunových mincí tak, že v každé obálce je nejvýše 1 mince. Určete počet všech možností.

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

Příklad 577

Na pískovišti si hrají 4 děti, dohromady mají 10 modrých, 15 červených a 8 zelených kuliček. Kolika způsoby si je mohou mezi sebou rozdělit tak, aby každé dítě mělo alespoň jednu kuličku od každé barvy?

Řešení	Ukázat
${9\choose6}+{14\choose11}+{7\choose4}$

Příklad 578

Prodejna domácích zvířat má šest psů, pět koček a čtyři morčata, zvířata stejného druhu považujeme za stejná. Kolika různými způsoby lze vybrat čtyři zvířata z této nabídky?

Řešení	Ukázat
${3+4-1\choose4}={6\choose4}$

Příklad 579

V železničním depu je 20 osobních, 7 lůžkových a 4 poštovníh vozy. Kolik různých souprav s pěti vozy je možné sestavit?

Řešení	Ukázat
${3+5-1\choose5}-1={7\choose5}-1$

Příklad 580

Při karetní hře Prší se rozdává 5 karet z balíčku 32 karet (4 barvy, každá barva má 8 karet s hodnotami 7, 8, 9, 10, J, Q, K, A). Kolik je možností, ve kterých dostaneme do ruky
(a) pět karet s různou hodnotou (na barvě nezáleží)
(b) pět karet stejné barvy
(c) dvě esa, dva krále a jednu dámu

Řešení	Ukázat
(a) $\dfrac{32\cdot28\cdot24\cdot20\cdot16}{5!}$ (b) ${4\choose1}\cdot{8\choose5}$ (c) ${4\choose2}\cdot{4\choose2}\cdot{4\choose1}$

666 příkladů z kombinatoriky

Komplexní úlohy VIII