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.