kombinatorika

Příklad 316

Kolika způsoby můžeme 8 lidí rozsadit v kupé pro 8 lidí? Kolik z nich je takových, že
(a) Věra sedí u okna?
(b) Věra sedí u okna?
(c) Adam a Eva sedí v ruzných směrech?

Řešení	Ukázat>
(a) Jsou 4 možnosti, jak usadit Evu. Zbylé lidi můžeme usadit libovolně: $4\cdot7!$ (b) Jsou 2 možnosti, jak usadit Věru. Zbylé lidi můžeme usadit libovolně: $2\cdot7!$ (c) Vybereme směr pro Adama (2 možnosti), pak vybereme místo pro Adama (4 možnosti), pak místo pro Evu (4 možnosti) a zbytek umístíme libovolně $(6!$ možností): $2\cdot4^2\cdot6!$

Příklad 317

Ve vlaku je kupé se 4 místy v každém směru jízdy. Z 8 cestujících chtějí 3 sedět ve směru jízdy, 2 proti a třem je to jedno. Kolika způsoby si mohou sednout tak, aby byli všichni spokojeni?

Řešení	Ukázat>
$V_3(4)\cdot V_2(4)\cdot 3!$

Příklad 318

Ve vlaku je kupé se 4 místy v každém směru jízdy. Z 8 cestujících chce Věra sedět u okna, Eva sedět ve směru jízdy, Josef a Denis proti směru jízdy a zbylým je to jedno. Kolika způsoby si mohou sednout tak, aby byli všichni spokojeni?

Řešení	Ukázat>
Příklad si rozdělíme na dvě situace (a) Věra sedí u okna ve směru jízdy. Potom pro Evu zůstávají 3 možnosti, pro Josefa 4 možnosti, pro Denise 3 možnosti a ostatní $4!$ možností. (b) Věra sedí u okna proti směru jízdy. Potom pro Evu zůstávají 4 možnosti, pro Josefa 3 možnosti, pro Denise 2 možnosti a ostatní $4!$ možností. Celkem $(3\cdot4\cdot3+4\cdot3\cdot2)\cdot4!$

Řešení

Ukázat>

Příklad si rozdělíme na dvě situace
(a) Věra sedí u okna ve směru jízdy. Potom pro Evu zůstávají 3 možnosti, pro Josefa 4 možnosti, pro Denise 3 možnosti a ostatní

$4!$ možností.
(b) Věra sedí u okna proti směru jízdy. Potom pro Evu zůstávají 4 možnosti, pro Josefa 3 možnosti, pro Denise 2 možnosti a ostatní

$4!$ možností.
Celkem

$(3\cdot4\cdot3+4\cdot3\cdot2)\cdot4!$

Příklad 319

V oddíle je 6 stolních tenistů. Kolika způsoby je můžeme postavit do řady tak, aby
a) Boris nestál na kraji?
b) Andrej stál někde za Borisem?

Řešení	Ukázat>
(a) Jsou 4 místa pro Borise, zbytek můžeme umístit libovolně: $4\cdot5!$ (b) Pozic, kdy Andrej stojí za Borisem je stejně, jako když Boris stojí za Andrejem. Přitom jedna z těchto možností musí nastat. Takže jich je vždy polovina všech možností. $\frac12\cdot6!$

Příklad 320

Na zkoušce je 7 lidí. Tři z nich jsou Jan, Josef a Dan. Kolik je možných pořadí, v jakém budou tito tři studenti zkoušení, jestliže Josef chce být hned za Danem a současně Josef chce být nejvýše pátý?

Řešení	Ukázat>
Jsou 4 možnosti pro Josefa (2., 3., 4., 5.). Tím je jednoznačně určena pozice Dana. Jan pak může být na pěti místech. Celkem $4\cdot5=20$

Příklad 321

Určete počet všech čtyřciferných přirozených čísel, v jejichž dekadickém zápisu není žádná z cifer $\{1, 2, 4, 6\}$ a každá ze zbývajících je v tomto zápisu nejvýše jednou.

Řešení	Ukázat>
Všechny možnosti - ty s nulou na začátku: $V_4(6)-V_3(5)$

Příklad 322

V restauraci stojí v řadě třináct stolů. Nad ně se má umístit devět stejných slunečníkù tak, aby byly symetricky podle prostředního stolku. Kolik je možností?

Řešení	Ukázat>
Protože slunečníků je lichý počet, jeden musí být nad prostředním stolem. Ze zbytku vezmeme polovinu a rozmístíme ji nad polovinou stolů. To lze ${6\choose4}$ způsoby. Druhá polovina je už jednoznačně určená.

Příklad 323

Použijeme čísla 1, 2, 3, 4, 5 k vytvoření pěticiferných čísel, v nichž se číslice neopakují. Kolik sudých čísel menších než 50000 můžeme vytvořit?

Řešení	Ukázat>
Na místě jednotek máme dvě možnosti. Na místě desettisíců pak zůstanou tři možnosti. Zbylé cifry pak můžeme umístit libovolně: $2\cdot3\cdot3!$

Příklad 324

Dvanáct žáků dostane test, který má dvě varianty (A a B). Žáci sedí ve dvou řadách po šesti tak, že žáci sedící vedle sebe nemají stejnou variantu a žáci sedící za sebou mají stejnou variantu. Kolika způsoby můžeme žáky usadit a rozdat jim testy?

Řešení	Ukázat>
$2\cdot12!$

Příklad 325

Ze skupiny 6 mužů a 4 žen chceme vybrat 4-členné družstvo v němž bude kapitan a zástupce kapitána. Přitom chceme, aby kapitán a jeho zástupce byli opačného pohlaví. Kolika způsoby můžeme družstvo sestavit?

Řešení	Ukázat>
$2\cdot6\cdot4\cdot{8\choose2}$

Příklad 326

V politické straně která ma 60 členů chtějí zvolit předsedu, tři místopředsedy a pět druhých místopředsedů. S tím, že každý člen může zastávat pouze jednu funkci a posty místopředsedů jsou nerozlišitelné. Kolika způsoby lze takovou volbu provést?

Řešení	Ukázat>
${60\choose1}\cdot{59\choose3}\cdot{56\choose5}$

Příklad 327

Kolika způsoby můžeme 9 lidí rozdělit do tří neoznačených týmů po třech lidech?

Řešení	Ukázat>
$\dfrac{1}{3!}{9\choose3}\cdot{6\choose3}$

Příklad 328

Kolik existuje pětimístných přirozených čísel, která mají ve svém zápise sudý (nenulový) počet sudých cifer?

Řešení	Ukázat>
(a) dvě sudé cifry: vybereme pozice pro sudé cifry - to lze ${5\choose2}$ způsoby. Na každou pozici pak máme 5 možností. ${5\choose2}\cdot5^5.$ Musíme odečíst možnosti s nulou na začátku: ${4\choose1}\cdot5^4$ (b) čtyři sudé cifry: ${5\choose4}\cdot5^5-{4\choose3}\cdot5^4$ Celkem ${5\choose2}\cdot5^5-{4\choose1}\cdot5^4+{5\choose4}\cdot5^5-{4\choose3}\cdot5^4$

Příklad 329

Řetězec DNA je kódován písmeny {A, C, G, T}. Kolik existuje různých řetězců délky $r,$ které obsahují $r_1$ písmen A, $r_2$ C, $r_3$ G a $r_4$ T $(r_1+r_2+r_3+r_4 = r)$ ?
Kolik procent z nich obsahuje všechna písmena stejného druhu v jednom bloku? Např. $\underbrace{A\dots A}_{r_1}\underbrace{T\dots T}_{r_4}\underbrace{C\dots C}_{r_2}\underbrace{G\dots G}_{r_3}$

Řešení	Ukázat>
Existuje $\dfrac{r!}{r_1!\cdot r_2!\cdot r_3!\cdot r_4!}$ řetězců. Všechna písmena stejného druhu v jednom bloku mohou být uspořádána $4!$ způsoby. Je jich tedy $\dfrac{4!\cdot r_1!\cdot r_2!\cdot r_3!\cdot r_4!}{r!}\cdot 100\ \%$

Příklad 330

Kolik různých deseticiferných čísel můžeme vytvořit z cifer $\{2, 3, 4, 5, 6, 8\},$ když
(a) každá lichá cifra se v čísle vyskytuje přesně 3 krát a každá sudá právě jednou?
(b) každá cifra je použita aspoň jednou a jsou seřazeny vzestupně?

Řešení	Ukázat>
(a) $\dfrac{10!}{3!\cdot3!}$ (b) Vezmeme každou cifru jednou a seřadíme je vzestupně. Nyní musíme doplnit ještě čtyři cifry. Každou můžu vybrat 6 způsoby. Jejich umístění je jednoznačné - vždy za poslední cifru stejné hodnoty. Takže existuje $6^4$ čísel.