kombinatorika

Příklad 278

Kolik existuje pětimístných přirozených čísel, která nemají ve svém zápisu všechny cifry sudé?

Řešení	Ukázat>
Všech čísel je $9\cdot10^4.$ Čísel, která mají všechny cifry sudé, je $4\cdot5^4.$ Takže hledaných čísel je $9\cdot10^4-4\cdot5^4.$

Příklad 279

Kolika způsoby můžeme vybrat 12 osob ze 17, když požadujeme, aby dva určení lidé nebyli vybraní současně?

Řešení	Ukázat>
Všech výběrů je ${17\choose12}.$ Výběrů, v nichž jsou oba určení lidé, je ${15\choose10}.$ Takže hledaných výběrů je ${17\choose12}-{15\choose10}.$

Příklad 280

Babka bylinkářka připravuje různé čajové směsi. Má 42 různých druhů bylinek a směsi vždy míchá z pěti různých druhů. Má však dvě takové bylinky, které se ve směsi nesmí nachazet spolu. Kolik různých čajových směsí může babka bylinkařka namíchat?

Řešení	Ukázat>
${42\choose5}-{40\choose3}$

Příklad 281

Slovo "DVACETIKORUNY" je zajímavé tím, že obsahuje všechny samohlásky v abecedním pořadí. Kolik je všech uspořádání písmen tohoto slova, ve kterých samohlásky nejsou v abecedním pořadí?

Řešení	Ukázat>
Všech anagramů je $13!$ Určíme počet anagramů, v nichž jsou samohlásky v abecedním pořadí: Vybereme pozice pro samohlásky, to lze ${13\choose6}$ způsoby. Na zbylých pozicích můžeme souhlásky přerovnat $7!$ způsoby. Takže existuje $13!-{13\choose6}\cdot7!$ požadovaných uspořádání.

Příklad 282

Mějme k dispozici 12 hráčů, mezi nimiž je 5 dobrých útočníků. Kolika způsoby můžeme sestavit 4-člennê družstvo, ve kterém bude alespoň jeden dobrý útočník?

Řešení	Ukázat>
Všech možných družstev je ${12\choose4}.$ Družstev, v nichž není žádný dobrý útočník, je ${7\choose4}.$ Takže požadovaných družtev je ${12\choose4}-{7\choose4}.$

Příklad 283

Z číslic 1 až 9 sestavujeme pěticiferná čísla, v nichž se žádné číslo neopakuje. Kolik z těchto čísel neobsahuje cifry 2, 4, 5 (současně)?

Řešení	Ukázat>
$V_5(9)-{6\choose2}\cdot5!$

Příklad 284

Kolik existuje takových podmnožin 6 prvkové množiny, které obsahují aspoň jeden ze tří pevně zvolených prvků?

Řešení	Ukázat>
Všech podmnožin je $2^6.$ Podmnožin, které neobsahují žádný ze zvolených prvků, je $2^3.$ Celkem tedy existuje $2^6-2^3$ požadovaných podmnožin.

Příklad 285

Zjistěte, kolik existuje ve Sportce takových tahů, které obsahují aspoň jedno z čísel 1, 2, 3.

Řešení	Ukázat>
Všech možných tahů je ${49\choose6}.$ Tahů, které neobsahují čísla 1, 2, 3, je ${46\choose6}.$ Takže požadovaných tahů je ${49\choose6}-{46\choose6}.$

Příklad 286

Kolika způsoby lze osvětlit místnost, v níž je pět různých lamp a každá má samostatný vypínač?

Řešení	Ukázat>
Všech možných nastavení vypínačů je $2^5.$ Ovšem jedno z nich místnost neosvětlí (všechny lampy jsou zhasnuté). Takže $2^5-1.$

Příklad 287

V loterii losujeme 6 čísel ze 49. Kolik existuje tahů, v nichž jsou tažena alespoň dvě sousední čísla?

Řešení	Ukázat>
Všech možných tahů je ${49\choose6}.$ Tahů, v nichž nejsou žádná sousední čísla, je ${44\choose6}$ (Příklad 159 (b)). Takže celkem ${49\choose6}-{44\choose6}.$

Příklad 288

V urně je 13 černých a 14 bílých koulí. Koule jedné barvy považujeme za nerozlišitelné. Kolika způsoby lze náhodně vybrat 4 koule tak, aby aspoň jedna byla černá?

Řešení	Ukázat>
${27\choose4}-{14\choose4}$

Příklad 289

V urně je 13 černých a 14 bílých koulí. Koule jedné barvy považujeme za nerozlišitelné. Kolika způsoby lze náhodně vybrat 4 koule tak, aby aspoň jedna byla bílá?

Řešení	Ukázat>
${27\choose4}-{13\choose4}$

Příklad 290

V novinovém stánku je ke koupi deset druhů pohledů, přičemž každý druh je k dispozici v padesáti exemplářích. Určete, kolika způsoby lze zakoupit 51 pohledů.

Řešení	Ukázat>
Kdyby byl k dispozici dostatečný počet pohledů každého druhu, byl by počet možností (kombinace s opakováním) ${51+10-1\choose51}={60\choose51}.$ Jenže v tom jsou započítány i nákupy 51 stejných pohledů. Takových nákupů je 10, a ty musíme odečíst. Takže existuje ${60\choose51}-10$ způsobů, jak nakoupit pohledy.

Příklad 291

V košíku je 5 červených, 7 modrých a 6 žlutých velikonočních vajíček. Kolika způsoby lze z nich vybrat 5 vajíček tak, aby nebyla všechna stejná?

Řešení	Ukázat>
Stejná úvaha, jako v předešlém příkladě: ${18+3-1\choose18}-3={20\choose18}-3$

Příklad 292

V osudí je 9 bílých a 12 červených lístků. Kolika způsoby lze náhodně vybrat 3 lístky tak, aby aspoň jeden byl bílý?

Řešení	Ukázat>
${21\choose3}-{12\choose3}$

Příklad 293

Š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 takových řad?

Řešení	Ukázat>
$8!-2\cdot6!$

Příklad 294

Čtyřmi hracími kostkami (červenou, zelenou, modrou a žlutou) hodíme současně. Kolika způsoby může padnout součet 10?

Řešení	Ukázat>
Součet 10 můžeme ze čtyř přirozených čísel vytvořit ${9\choose3}$ způsoby (příklad 202). Mezi nimi jsou ale i součty obsahující sedmičku. Ty jsou čtyři a musíme je odečíst. Takže ${9\choose3}-4$ způsobů.

Příklad 295

Okolo kulatého stolu sedí hráči dvou fotbalových týmů (Poděbrady a Nymburk), 11 v každém družstvu. Hráči sedí střídavě (Poděbrady, Nymburk, Poděbrady, Nymburk ...). Kolik existuje různých rozesazení, když brankáři sedí vedle sebe a kapitáni nesmí sedět vedle sebe?

Řešení	Ukázat>
Usadíme ke stolu hráče Nymburka. To je $10!$ možností. Pak usadíme brankáře Poděbrad, $2$ možnosti a do zbylých mezer ostatní hráče Poděbrad, $10!$ možností. Všech způsobů je tedy $2\cdot10!\cdot10!$ Nyní určíme počet možností, kdy jsou brankáři vedle sebe a kapitáni také vedle sebe. Usadíme brankáře (2 možnosti). Když si nyní představíme dvojici kapitánů jako jeden "objekt", máme 19 možností, jak je usadit, protože pořadí P-N, nebo N-P už je jednoznačně dáno pozicí brankářů. Umístění zbývajících hráčů můžeme udělat $9!$ Nymburk a $9!$ Poděbrady. Celkem tedy $2\cdot19\cdot9!\cdot9!$ . Existuje tedy $2\cdot10!\cdot10!-2\cdot19\cdot9!\cdot9!$ rozesazení.

Řešení

Ukázat>

Usadíme ke stolu hráče Nymburka. To je

$10!$ možností. Pak usadíme brankáře Poděbrad,

$2$ možnosti a do zbylých mezer ostatní hráče Poděbrad,

$10!$ možností. Všech způsobů je tedy

$2\cdot10!\cdot10!$
Nyní určíme počet možností, kdy jsou brankáři vedle sebe a kapitáni také vedle sebe. Usadíme brankáře (2 možnosti). Když si nyní představíme dvojici kapitánů jako jeden "objekt", máme 19 možností, jak je usadit, protože pořadí P-N, nebo N-P už je jednoznačně dáno pozicí brankářů. Umístění zbývajících hráčů můžeme udělat

$9!$ Nymburk a

$9!$ Poděbrady. Celkem tedy

$2\cdot19\cdot9!\cdot9!$ .
Existuje tedy

$2\cdot10!\cdot10!-2\cdot19\cdot9!\cdot9!$ rozesazení.

Příklad 296

Parlament má 151 poslanců. Při volbách se do parlamentu dostalo 7 politických stran (každá aspoň jednoho poslance). Víme, že ani jedna strana nemá absolutní většinu. Kolik je různých rozdělení počtu poslanců?

Řešení	Ukázat>
Všech možných rozdělení je ${151-1\choose7-1}={150\choose6}$ (Příklad 202). Počet rozdělení, kdy jedna strana má obsolutní většinu, určíme tak, že jedné straně dáme 75 poslanců a zbylých 76 rozdělíme tak, aby každá strana dosatala aspoň jednoho poslance. $7\cdot{76-1\choose7-1}=7\cdot{75\choose6}.$ Celkem je tedy ${150\choose6}-7\cdot{75\choose6}$ rozdělení.

Příklad 297

Máme karty očíslovaně čísly 1 až 20. Kolika způsoby z nich můžeme vybrat tři tak, aby aspoň na jednom z nich bylo dvouciferné číslo?

Řešení	Ukázat>
Všech výběrů je ${20\choose3}.$ Výběrů, které nemají dvouciferné číslo, je ${9\choose3}.$ Celkem ${20\choose3}-{9\choose3}.$

Příklad 298

Máme karty očíslovaně čísly 1 až 15. Kolika způsoby z nich můžeme vybrat čtyři tak, aby aspoň na dvou byla čísla menší než 10?

Řešení	Ukázat>
Všech výběrů je ${15\choose4}.$ Výběrů, které nemají jednociferné číslo, je ${6\choose4}.$ Výběrů, které mají právě jedno jednociferné číslo, je $9\cdot{6\choose3}.$ Celkem ${15\choose4}-{6\choose4}-9\cdot{6\choose3}.$

Příklad 299

Určete počet všech přirozených čtyřciferných čísel, v jejichž dekadickém zápisu se vyskytují právě dvě dvojky a ostatní cifry se neopakují.

Řešení	Ukázat>
Určíme počet všech možných řetězců (i s nulou na počátku): Vybereme pozice pro dvojky - ${4\choose2}$ možností Vybereme zbylé dvě číslice - ${9\choose2}$ možností. Ty pak můžeme umístit dvěma způsoby. Takže existuje $2\cdot{4\choose2}\cdot{9\choose2}$ možných řetězců. Počet řetězců začínajících nulou: $8\cdot{3\choose2}.$ Existuje tedy $2\cdot{4\choose2}\cdot{9\choose2}-8\cdot{3\choose2}$ čísel požadované vlastnosti.

Řešení

Ukázat>

Určíme počet všech možných řetězců (i s nulou na počátku): Vybereme pozice pro dvojky -

${4\choose2}$ možností
Vybereme zbylé dvě číslice -

${9\choose2}$ možností. Ty pak můžeme umístit dvěma způsoby.
Takže existuje

$2\cdot{4\choose2}\cdot{9\choose2}$ možných řetězců.
Počet řetězců začínajících nulou:

$8\cdot{3\choose2}.$
Existuje tedy

$2\cdot{4\choose2}\cdot{9\choose2}-8\cdot{3\choose2}$ čísel požadované vlastnosti.

Příklad 300

Určete počet všech anagramů slova "ALIVE" takových, že písmeno "A" je někde před písmenem "E" nebo písmeno "E" je někde před písmenem "I".

Řešení	Ukázat>
Existuje $5!$ způsobů, jak uspořádat daná písmena bez podmínek. Určíme počet nevyhovujících uspořádání. To jsou taková, že "A" je za "E" a "E" je za "I", takže písmena jsou v pořadí "I, E, A". Pozice pro tato písmena můžeme vybrat ${5\choose3}$ způsoby. Písmena "L" a "V" pak můžeme na zbylá místa umístit dvěma způsoby. Je tedy $2\cdot{5\choose3}$ špatných uspořádání. To znamená, že existuje $5!-2\cdot{5\choose3}$ požadovaných anagramů.

Řešení

Ukázat>

Existuje

$5!$ způsobů, jak uspořádat daná písmena bez podmínek. Určíme počet nevyhovujících uspořádání. To jsou taková, že "A" je za "E" a "E" je za "I", takže písmena jsou v pořadí "I, E, A". Pozice pro tato písmena můžeme vybrat

${5\choose3}$ způsoby. Písmena "L" a "V" pak můžeme na zbylá místa umístit dvěma způsoby. Je tedy

$2\cdot{5\choose3}$ špatných uspořádání.
To znamená, že existuje

$5!-2\cdot{5\choose3}$ požadovaných anagramů.

666 příkladů z kombinatoriky

Odčítání 2

Příklad 278

Příklad 279

Příklad 280

Příklad 281

Příklad 282

Příklad 283

Příklad 284

Příklad 285

Příklad 286

Příklad 287

Příklad 288

Příklad 289

Příklad 290

Příklad 291

Příklad 292

Příklad 293

Příklad 294

Příklad 295

Příklad 296

Příklad 297

Příklad 298

Příklad 299

Příklad 300

Napsat komentář Zrušit odpověď na komentář