kombinatorika

Příklad 394

Skupina tří chlapců a dvou dívek hledá práci v sedmi firmách. Ve třech firmách mají zájem pouze o chlapce, ve dvou berou jen ženy a ve zbylých firmách mají zájem o každého. Kolika způsoby se může skupina do jednotlivých podniků rozejít? (Každá firma může přijmou libovolný počet uchazečů.)

Řešení	Ukázat
Nejprve umístíme chlapce. ${7\choose3}\cdot3!$ (3 objekty do 5 kategoríí a promíchání) Potom rozmístíme dívky. ${5\choose2}\cdot2!$ Celkem ${7\choose3}\cdot3!+{5\choose2}\cdot2!$ možností.

Příklad 395

Kolik různých deseticiferných čísel můžeme vytvořit z cifer $\{2, 3, 4, 5, 6, 8\},$ když cifry jsou seřazené vzestupně?

Řešení	Ukázat
Pokud jsou čísla seřazená vzestupně, jejich pořadí je jednoznačně určeno. Musíme proto jen určit které cifry a kolikrát se čísle vyskytují. Vlastně 10 objektů (cifer) rozdělujeme do šesti kategorií (jejich hodnot). Jde o kombinace s opakováním. ${15\choose10}$ různých čísel.

Příklad 396

Ze 7 kuliček, z nichž jsou 4 modré (navzájem nerozlišitelné), 1 bílá, 1 červená a 1 zelená máte vybrat a položit do řady vedle sebe 5 kuliček. Kolika způsoby to lze provést?

Řešení	Ukázat
Možnosti rozdělíme na případy podle počtu modrých kuliček v řadě. 1. 4+1: $3\cdot\frac{5!}{4!}=15$ 2. 3+2: ${3\choose2}\frac{5!}{3!}=30$ 3. 2+1+1+1: $\frac{5!}{2!}=10$ Celkem $55$ různých řad.

Příklad 397

Na škole si studenti musí zvolit heslo pro přístup do počítačové sítě. Při volbě hesla musí dodržet následující pravidla:

Heslo musí obsahovat pouze číslice nebo malá písmena anglické abecedy (má 26 znaků).
Heslo musí být dlouhe 4 nebo 5 znaků.
Heslo musí začínat písmenem B, nebo C.

Kolik různých hesel existuje?

Řešení	Ukázat
$2\cdot36^3+2\cdot36^4=74\cdot36^3$

Příklad 398

Na schůzi má promluvit pět řečníků A, B, C, D, E (každý právě jednou).
(a) Určete počet všech možných pořadí jejich vystoupení.
(b) Určete počet všech možných pořadí jejich vystoupení, má-li řečník B mluvit bezprostředně po A.
(c) Určete počet všech možných pořadí jejich vystoupení, má-li řečník B mluvit až poté, co promluvil řečník A.

Řešení	Ukázat
(a) $5!$ (b) $4!$ (c) Všech pořadí je podle (a) $5!$ Každé dobré pořadí, kdy B je po A, vždy můžeme změnit na špatné tak, že vyměníme A a B. Stejně tak každé špatné pořadí záměnou A a B změníme na dobré. To znamená, že dobrých i špatných pořadí je stejný počet, a to přesně polovina. $\frac125!$

Příklad 399

Kolik čtyřciferných přirozených čísel s navzájem různými ciframi lze sestavit z cifer
(a) 1, 2, 3, 4
(b) 1, 2, 3, 4, 5, 6
(c) 0, 1, 2, 3, 4, 5?
Kolik z nich je sudých? Kolik z nich je dělitelných čtyřmi?

Řešení	Ukázat
(a) Všech čísel je $4!=24.$ Sudých je polovina, tj. $12$ a dělitelných čtyřmi je čtvrtina, tj. $6.$ (b) Všech čísel je $V_4(6)=360.$ Sudých je polovina, tj. $180.$ Dělitelná čtyřmi musí končit dvojčíslím z množiny $\{12,16,24,32,36,52,56,64\}.$ Těch je tedy osm. Všech možných dvojčíslí je $6\cdot5=30.$ Takže dělitelných čtyřmi je $\frac8{30}$ celkového počtu, tj. $360\cdot\frac8{30}=96.$ (c) Všech čísel je $5\cdot5\cdot4\cdot3=300.$ Sudá čísla. Možnosti se rozpadají na dvě disjunktní množiny i) na konci je nula: $5\cdot4\cdot3=60$ ii) na konci není nula: $4\cdot4\cdot3\cdot2=96$ Celkem $156$ čísel. Čísla dělitelná čtyřmi. Možnosti se opět rozpadají na dvě disjunktní množiny i) poslední dvojčíslí obsahuje nulu $\{04;20;40\}$ - $3\cdot4\cdot3=36$ čísel ii) poslední dvojčíslí neobsahuje nulu $\{12;24;32;52\}$ - $4\cdot3\cdot3=36$ čísel Celkem $72$ čísel.

Řešení

Ukázat

(a) Všech čísel je

$4!=24.$ Sudých je polovina, tj.

$12$ a dělitelných čtyřmi je čtvrtina, tj.

$6.$
(b) Všech čísel je

$V_4(6)=360.$ Sudých je polovina, tj.

$180.$ Dělitelná čtyřmi musí končit dvojčíslím z množiny

$\{12,16,24,32,36,52,56,64\}.$ Těch je tedy osm. Všech možných dvojčíslí je

$6\cdot5=30.$ Takže dělitelných čtyřmi je

$\frac8{30}$ celkového počtu, tj.

$360\cdot\frac8{30}=96.$
(c) Všech čísel je

$5\cdot5\cdot4\cdot3=300.$
Sudá čísla.
Možnosti se rozpadají na dvě disjunktní množiny
i) na konci je nula:

$5\cdot4\cdot3=60$
ii) na konci není nula:

$4\cdot4\cdot3\cdot2=96$
Celkem

$156$ čísel.
Čísla dělitelná čtyřmi.
Možnosti se opět rozpadají na dvě disjunktní množiny
i) poslední dvojčíslí obsahuje nulu

$\{04;20;40\}$ -

$3\cdot4\cdot3=36$ čísel
ii) poslední dvojčíslí neobsahuje nulu

$\{12;24;32;52\}$ -

$4\cdot3\cdot3=36$ čísel
Celkem

$72$ čísel.

Příklad 400

Kolik různých přirozených trojcifernýrch čísel menších než 400 lze sestavit z číslic $\{0, 1, 2, 7, 8\},$ jestliže se žádná číslice, kromě číslice 0, nesmí opakovat?

Řešení	Ukázat
Řešení rozdělíme na varianty podle počtu nul v čísle. 1. žádná nula: $2\cdot3\cdot2=12$ 2. jedna nula: $2\cdot2\cdot3=12$ 3. dvě nuly: $2$ Celkem $26$ čísel.

Příklad 401

Kolika způsoby můžeme na šachovnici $8\times8$ umístit věž a krále tak, aby se neohrožovaly?

Řešení	Ukázat
Řešení rozdělíme na varianty podle postavení věže. 1. Věž je v rohu: vidíme, že pro krále je vždy $48$ možností. Celkem $4\cdot48=192.$ 2. Věž je na kraji, ale ne v rohu: Pro krále je $47$ možností, pro věž $24$ možností. Celkem $47\cdot24=1128.$ 3. Věž je "uvnitř": Pro krále je $45$ možností, pro věž $36$ možností. Celkem $45\cdot36=1620.$ Existuje $192+1128+1620=2940$ různých rozmístění.

Řešení

Ukázat

Řešení rozdělíme na varianty podle postavení věže.
1. Věž je v rohu:

vidíme, že pro krále je vždy

$48$ možností. Celkem

$4\cdot48=192.$
2. Věž je na kraji, ale ne v rohu:

Pro krále je

$47$ možností, pro věž

$24$ možností.
Celkem

$47\cdot24=1128.$
3. Věž je "uvnitř":

Pro krále je

$45$ možností, pro věž

$36$ možností.
Celkem

$45\cdot36=1620.$
Existuje

$192+1128+1620=2940$ různých rozmístění.

Příklad 402

Určete součet všech trojciferných čísel, které je možné napsat pomocí cifer $\{1, 2, 3, 4\}.$

Řešení	Ukázat
Všech čísel je $4^3=64.$ Z nich $\frac14$ má na 1. místě jedničku, $\frac14$ má na 1. místě dvojku, $\frac14$ má na 1. místě trojku a $\frac14$ má na 1. místě čtyřku. Takže součet na 1. místě dává $16\cdot100\cdot(1+2+3+4)=160\cdot100.$ Analogicky na 2. místě bude součet $16\cdot10\cdot(1+2+3+4)=160\cdot10$ a na 3. místě $16\cdot1\cdot(1+2+3+4)=160\cdot1.$ Celkem $160\cdot(100+10+1)=160\cdot111=17760.$

Řešení

Ukázat

Všech čísel je

$4^3=64.$
Z nich

$\frac14$ má na 1. místě jedničku,

$\frac14$ má na 1. místě dvojku,

$\frac14$ má na 1. místě trojku a

$\frac14$ má na 1. místě čtyřku. Takže součet na 1. místě dává

$16\cdot100\cdot(1+2+3+4)=160\cdot100.$
Analogicky na 2. místě bude součet

$16\cdot10\cdot(1+2+3+4)=160\cdot10$ a na 3. místě

$16\cdot1\cdot(1+2+3+4)=160\cdot1.$
Celkem

$160\cdot(100+10+1)=160\cdot111=17760.$

Příklad 403

Kolik různých čtyřciferných čísel lze sestavit z číslic čísla 426269? Každou z číslic můžete použít nejvýše tolikrát, kolikrát je obsažena v čísle 426269.

Řešení	Ukázat
Všechny možnosti se rozpadají na tři disjunktní množiny. 1. každá cifra jiná: $4!$ 2. dvě stejné cifry a dvě různé cifry: Dvojici stejných cifer můžeme vybrat dvěma způsoby. Zbylé dvě cifry vybereme ${3\choose2}$ způsoby. Vybrané cifry pak můžeme uspořádat $\frac{4!}{2!}$ způsoby. 3. dvě dvojice stejných cifer: Vybrat je můžeme jen jedním způsobem a uspořádat $\frac{4!}{2!\cdot2!}$ Celkem můžeme sestavit $4!+2\cdot{3\choose2}\cdot\frac{4!}{2!}+\frac{4!}{2!\cdot2!}$ čísel.

Řešení

Ukázat

Všechny možnosti se rozpadají na tři disjunktní množiny.
1. každá cifra jiná:

$4!$
2. dvě stejné cifry a dvě různé cifry: Dvojici stejných cifer můžeme vybrat dvěma způsoby. Zbylé dvě cifry vybereme

${3\choose2}$ způsoby. Vybrané cifry pak můžeme uspořádat

$\frac{4!}{2!}$ způsoby.
3. dvě dvojice stejných cifer: Vybrat je můžeme jen jedním způsobem a uspořádat

$\frac{4!}{2!\cdot2!}$
Celkem můžeme sestavit

$4!+2\cdot{3\choose2}\cdot\frac{4!}{2!}+\frac{4!}{2!\cdot2!}$ čísel.

Příklad 404

Kolik různých čtyřciferných čísel lze sestavit z cifer čísla 238832? Každou z číslic můžete použít nejvýše tolikrát, kolikrát je obsažena v čísle 238832.

Řešení	Ukázat
Všechny možnosti se rozpadají na dvě disjunktní množiny. 1. dvě stejné cifry a dvě různé cifry: Dvojici stejných cifer můžeme vybrat třemi způsoby. Tím jsou jednoznačně určené zbylé dvě cifry. Vybrané cifry pak můžeme uspořádat $\frac{4!}{2!}$ způsoby. 2. dvě dvojice stejných cifer: Vybrat je můžeme třemi způsoby. Uspořádat pak $\frac{4!}{2!\cdot2!}$ způsoby. Celkem můžeme sestavit $3\cdot\left(\frac{4!}{2!}+\frac{4!}{2!\cdot2!}\right)$ různých čísel.

Řešení

Ukázat

Všechny možnosti se rozpadají na dvě disjunktní množiny.
1. dvě stejné cifry a dvě různé cifry: Dvojici stejných cifer můžeme vybrat třemi způsoby. Tím jsou jednoznačně určené zbylé dvě cifry. Vybrané cifry pak můžeme uspořádat

$\frac{4!}{2!}$ způsoby.
2. dvě dvojice stejných cifer: Vybrat je můžeme třemi způsoby. Uspořádat pak

$\frac{4!}{2!\cdot2!}$ způsoby.
Celkem můžeme sestavit

$3\cdot\left(\frac{4!}{2!}+\frac{4!}{2!\cdot2!}\right)$ různých čísel.

Příklad 405

Z množiny přirozených čísel máme vybrat dvě čísla tak, aby ani jedno z nich nebylo větší než 20 a jejich součet byl sudý. Kolika způsoby to můžeme udělat?

Řešení	Ukázat
Všechny možnosti se rozpadají na dvě disjunktní množiny. 1. obě čísla sudá: ${10\choose2}$ výběrů 2. obě čísla lichá: ${10\choose2}$ výběrů Celkem $2\cdot{10\choose2}$ způsobů.

Příklad 406

Máme 12 různých jednohodinových a 4 různé dvouhodinové předměty. V jeden den nemůžou být dva stejné předměty.
(a) Kolika způsoby můžeme sestavit rozvrh na jeden den se sedmi hodinami, má-li obsahovat pouze jeden dvouhodinový předmět?
(b) Kolika způsoby můžeme sestavit rozvrh na jeden den, který má sedm vyučovacích hodin, jestliže mezi vybranými mají být aspoň dva dvouhodinové předměty?

Řešení	Ukázat
(a) Vybereme dvouhodinový předmět ${4\choose1}$ způsoby a k němu pět jednohodinových ${12\choose5}$ způsoby. Promíchat je pak můžeme $6!$ způsoby. Celkem ${4\choose1}\cdot{12\choose5}\cdot6!$ (b) Vybereme dva dvouhodinové předměty ${4\choose2}$ způsoby a k němu tři jednohodinové ${12\choose3}$ způsoby. Promíchat je pak můžeme $5!$ způsoby. Nebo vybereme tři dvouhodinové předměty ${4\choose3}$ způsoby a k nim jeden jednohodinový ${12\choose1}$ způsoby. Promíchat je pak můžeme $4!$ způsoby. Celkem ${4\choose2}\cdot{12\choose3}\cdot5!+{4\choose3}\cdot{12\choose1}\cdot4!$

Řešení

Ukázat

(a) Vybereme dvouhodinový předmět

${4\choose1}$ způsoby a k němu pět jednohodinových

${12\choose5}$ způsoby. Promíchat je pak můžeme

$6!$ způsoby.
Celkem

${4\choose1}\cdot{12\choose5}\cdot6!$
(b) Vybereme dva dvouhodinové předměty

${4\choose2}$ způsoby a k němu tři jednohodinové

${12\choose3}$ způsoby. Promíchat je pak můžeme

$5!$ způsoby. Nebo vybereme tři dvouhodinové předměty

${4\choose3}$ způsoby a k nim jeden jednohodinový

${12\choose1}$ způsoby. Promíchat je pak můžeme

$4!$ způsoby.
Celkem

${4\choose2}\cdot{12\choose3}\cdot5!+{4\choose3}\cdot{12\choose1}\cdot4!$

Příklad 407

Máme 7 různých figurek a tři různé barvy. Kolik existuje možností, jak všechny figurky obarvit?

Řešení	Ukázat
Kombinace s opakováním: ${7+3-1\choose7}={9\choose7}$

Příklad 408

Máme 10 stejných figurek a čtyři různé barvy. Kolik existuje možností, jak všechny figurky obarvit?

Řešení	Ukázat
Kombinace s opakováním: ${10+4-1\choose10}={13\choose10}$

Příklad 409

Máme 10 stejných figurek a čtyři různé barvy. Kolik existuje možností, jak NĚKTERÉ figurky obarvit?

Řešení	Ukázat
Přidáme pátou "prázdnou" barvu. ${10+5-1\choose10}-1={14\choose10}-1$ (musíme odečíst možnost, kdy není obarvená žádná figurka).

Příklad 410

Máme 10 stejných fiurek a čtyři různé barvy. Kolik existuje možností, jak všechny figurky obarvit, přičemž od každé barvy by měla být alespoň jedna figurka?

Řešení	Ukázat
Podle příkladu 378 ${10-1\choose4-1}={9\choose3}$

Příklad 411

Každou stěnu krychle obarvíme právě jednou ze dvou různých barev. Kolik existuje různých způsobů obarvení? Obarvení, která se liší jen natočením krychle, považujeme za identická.

Řešení	Ukázat
Řešení rozdělíme a jednotlivé případy: 1. jednobarevné krychle: $2$ možnosti. 2. 5 stěn jednou barvou + 1 stěna druhou: $2$ možnosti. 3. 4+2: jsou tva typy Vzhledem k záměně barev jsou $4$ možnosti. 4. 3+3: jsou dva typy Záměna barev vede ke stejnému výsledku. Celkem $2+2+4+2=10$ způsobů obarvení.

Příklad 412

Kolik různých součinů můžeme dostat z čísel $\{1, 2, 3, 5, 7\},$ jestliže se v jednom součinu činitelé neopakují?

Řešení	Ukázat
Jednička jako činitel součin nezmění, takže není důležitá. U ostatních čísel platí, že buďto v součinu jsou, nebo nejsou. Je tedy $2^4=16$ různých součinů.

Příklad 413

Z osmi kuliček, z nichž jsou čtyři bíle, dvě žluté, jedna červená a jedna modrá, máme vybrat a položit do řady pět kuliček. Určete, kolik různých řád můžeme vytvořit. Kuličky stejné barvy jsou nerozlišitelné.

Řešení	Ukázat
Všechny možnosti se rozpadají na pět disjunktních množin. 1. 4 kuličky jedné barvy a 1 kulička jiná: Odlišnou kuličku můžeme vybrat třemi způsoby a umístit ji na pět míst - $15$ možností. 2. 3+2: barvy jsou jednoznačně určené, pro jejich rozmístění je ${5\choose3}=10$ možností. 3. 3+1+1: Barvy odlišných kuliček můžeme vybrat ${3\choose2}$ způsoby a pro rozmístění je $\frac{5!}{3!}$ možností. Celkem ${3\choose2}\cdot\frac{5!}{3!}=60$ možností. 4. 2+2+1: $2\cdot\frac{5!}{2!\cdot2!}=60$ možností. 5. 2+1+1+1: $2\cdot\frac{5!}{2!}=120$ možností. Celkem je $265$ různých možných řad.

Řešení

Ukázat

Všechny možnosti se rozpadají na pět disjunktních množin.
1. 4 kuličky jedné barvy a 1 kulička jiná: Odlišnou kuličku můžeme vybrat třemi způsoby a umístit ji na pět míst -

$15$ možností.
2. 3+2: barvy jsou jednoznačně určené, pro jejich rozmístění je

${5\choose3}=10$ možností.
3. 3+1+1: Barvy odlišných kuliček můžeme vybrat

${3\choose2}$ způsoby a pro rozmístění je

$\frac{5!}{3!}$ možností. Celkem

${3\choose2}\cdot\frac{5!}{3!}=60$ možností.
4. 2+2+1:

$2\cdot\frac{5!}{2!\cdot2!}=60$ možností.
5. 2+1+1+1:

$2\cdot\frac{5!}{2!}=120$ možností.
Celkem je

$265$ různých možných řad.

Příklad 414

Máme 4 kuličky, které jsou očíslované a 4 stejně očíslované krabičky. Do každé krabičky můžeme dát právě jednu kuličku. Kolika způsoby můžeme uložit kuličky tak aby:
(a) aspoň 2 kuličky byly v krabičce se stejným číslem jaké má kulička
(b) číslo žádné kuličky nesouhlasilo s číslem na krabičce?

Řešení	Ukázat
(a) Právě dvě kuličky můžeme správně umístit ${4\choose2}$ způsoby. Právě tři kuličky umístit nejdou. Právě čtyři kuličky můžeme umístit jedním způsobem. Celkem ${4\choose2}+1$ možností. (b) Všech možností je $4!$ Aspoň jedna správně umístěná kulička: ${4\choose1}\cdot3!$ Aspoň dvě správně umístěné kuličky: ${4\choose2}\cdot2!$ Aspoň tři správně umístěné kuličky: ${4\choose3}\cdot1!$ Aspoň čtyři správně umístěné kuličky: ${4\choose4}\cdot0!$ Podle PIE je celkový počet rozmístění $4!-{4\choose1}\cdot3!+{4\choose2}\cdot2!-{4\choose3}\cdot1!+{4\choose4}\cdot0!=9.$

Řešení

Ukázat

(a) Právě dvě kuličky můžeme správně umístit

${4\choose2}$ způsoby.
Právě tři kuličky umístit nejdou.
Právě čtyři kuličky můžeme umístit jedním způsobem.
Celkem