KOMBINATORIKA

$${C(5, 18) = {18 \choose 5} = \frac{18!}{5! \cdot (18 - 5)!} = \frac{18!}{5! \cdot (13)!} = \frac{18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13!}{5! \cdot (13)!} = \frac{18 \cdot 17 \cdot 16 \cdot 15 \cdot 14}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 8~568}$$

Jedná se o kombinaci druhého řádu ze 20 prvků.

$${C(2, 20) = {20 \choose 2} = \frac{20!}{2! \cdot (20 - 2)!} = \frac{20!}{2! \cdot (18)!} = \frac{20 \cdot 19 \cdot 18!}{2! \cdot (18)!} = \frac{20 \cdot 19}{2} = 190}$$

Na ping-pongovém turnaji bude odehráno 190 zápasů v případě, že se zúčastní 20 hráčů.

a)

Jedno číslo z 5 lze vybrat pěti způsoby.

Výběr 10 studentů ze 20 je dán počtem kombinací desátého řádu z 20.

$${C(10, 20) = {20 \choose 10} = \frac{20!}{10! \cdot (20 - 10)!} = \frac{20!}{10! \cdot 10!} = 184~756}$$

b)

Pokud mají být ve vybraných studentech Martin a Pavel, vybíráme zbylých 8 studentů z 18.

Výběr 8 studentů z 18 je dán počtem kombinací osmého řádu z 18.

$${C(8, 18) = {18 \choose 8} = \frac{18!}{8! \cdot (18 - 8)!} = \frac{18!}{8! \cdot 10!} = 43~758}$$

c)

Pokud ve družstvu nemá být Petr, použijeme počet možností sestavení družstva z částí "a)" (tedy výběry 10 studentů z 20) a odečteme z něj všechny družstva, ve kterých by Petr byl (tedy výběry 9 studentů z 20, protože jedno místo v družstvě je pevně dané).

$${C(10, 20) = {20 \choose 10} = \frac{20!}{10! \cdot (20 - 10)!} = \frac{20!}{10! \cdot 10!} = 184~756}$$

Počet možností, kdy je v družstvu Petr:

$${C(9, 19) = {19 \choose 9} = \frac{19!}{9! \cdot (20 - 9)!} = \frac{19!}{9! \cdot 11!} = 92~378}$$

Celkový počet možností:

$${C(20, 10) - C(19, 9) = 184~756 - 92~378 = 92~378}$$

Mám 6 bankovek s různou nominální hodnotou. Abych získal všechny částky, které mohu použít, můžu vybrat 1 až 6 bankovek. Budu tedy tvořit kombinaci prvního až šestého řádu ze šesti prvků.

$${C(1, 6) = {6 \choose 1} = \frac{6!}{1! \cdot (6 - 1)!} = 6}$$

$${C(2, 6) = {6 \choose 2} = \frac{6!}{2! \cdot (6 - 2)!} = 15}$$

$${C(3, 6) = {6 \choose 3} = \frac{6!}{3! \cdot (6 - 3)!} = 20}$$

$${C(4, 6) = {6 \choose 4} = \frac{6!}{4! \cdot (6 - 4)!} = 15}$$

$${C(5, 6) = {6 \choose 5} = \frac{6!}{5! \cdot (6 - 5)!} = 6}$$

$${C(6, 6) = {6 \choose 6} = \frac{6!}{6! \cdot (6 - 6)!} = 1}$$

Celkový počet možných částek lze získat součtem těchto výsledků:

$${C(1, 6) + C(2, 6) + C(3, 6) + C(4, 6) + C(5, 6) + C(6, 6) = 6 + 15 + 20 + 15 + 6 + 1 = 63}$$

Z bankovek 5000 Kč, 2000 Kč, 1000 Kč, 500 Kč, 200 Kč, 100 Kč lze vytvořit 63 různých obnosů.

Pokud nejsou žádné 2 přímky rovnoběžné a žádné 3 neprocházejí jedním bodem, tak bude existovat průsečík pro každou dvojici přímek. Řešíme tedy kombinaci druhého řádu z 15 prvků.

$${C(2,15) = {15 \choose 2} = \frac{15!}{2!\cdot (15 - 2)!} = \frac{15!}{2!\cdot 13!} = \frac{15 \cdot 14}{2 \cdot 1} = 105}$$

15 přímek, z nichž žádné 2 nejsou rovnoběžné a žádné 3 neprocházejí jedním bodem, se protíná ve 105 bodech.

V případě, že by nebyly žádné 2 přímky rovnoběžné a žádné 3 neprocházejí jedním bodem, tak by existovat průsečík pro každou dvojici přímek. V tom případě by se řešila kombinace druhého řádu ze 14 prvků.

$${C(2,14) = {14 \choose 2} = \frac{14!}{2!\cdot (14 - 2)!} = \frac{14!}{2!\cdot 12!} = \frac{14 \cdot 13}{2 \cdot 1} = 91}$$

Ze získaného počtu průsečíků však je nutné odečíst všechny průsečíky, které by vytvořili 4 rovnoběžné přímky:

$${C(2,4) = {4 \choose 2} = \frac{4!}{2!\cdot (4 - 2)!} = \frac{4!}{2!\cdot 2!} = \frac{4 \cdot 3}{2 \cdot 1} = 6}$$

Celkový počet průsečíků tedy bude:

$${C(2,14) - C(2,4) = {14 \choose 2} - {4 \choose 2} = 91 - 6 = 85}$$

14 přímek, z nichž žádné 3 neprocházejí jedním bodem a 4 z nich jsou rovnoběžné, bodem se protíná v 85 bodech.

Počet možností výběru tří dívek ze 20 je dán počtem kombinací třetího řádu ze 20.

$${C(3,20) = {20 \choose 3} = \frac{20!}{3!\cdot (20 - 3)!} = \frac{20!}{3!\cdot 17!} = 1~140}$$

Počet možností výběru dvou chlapců z 10 je dán počtem kombinací druhého řádu z 10.

$${C(2,10) = {10 \choose 2} = \frac{10!}{2!\cdot (10 - 2)!} = \frac{10!}{2!\cdot 8!} = 45}$$

Použitím kombinatorického pravidla součinu získáme celkový výsledek.

$${C(3,20) \cdot C(2,10) = {20 \choose 3} \cdot {10 \choose 2 = 1~140 \cdot 45 = 51~300}

Z 20 dívek a 10 chlapců lze vytvořit 51 300 pětičlenných družstev takových, aby v nich byly 3 dívky a 2 chlapci.

Úhlopříčka spojuje 2 vrcholy n-úhelníku, které nejsou sousední. Celkový počet úhlopříček získáme jako kombinaci druhého řádu z n prvků, avšak musíme odečíst počet stran.

$${C(2, n) = {n \choose 2} = \frac{n!}{2! \cdot (n - 2)!} = \frac{n \cdot (n - 1) \cdot (n - 2)!}{2! \cdot (n - 2)!} = \frac{n \cdot (n - 1)}{2}}$$

Odečteme počet stran:

$${C(2, n) - n = \frac{n \cdot (n - 1)}{2} - n = }$$

Daný vztah lze ještě upravit:

$${ = \frac{n \cdot (n - 1)}{2} - \frac{2n}{2} = \frac{n \cdot (n - 1) - 2n}{2} = \frac{n \cdot \left[(n - 1) - 2\right]}{2} = \frac{n \cdot (n - 3)}{2}}$$

Dle vzorce pro kombinaci sestavíme rovnici:

$${C(2, n) = 66}$$ $${{n \choose 2} = 66}$$ $${\frac{n!}{2! \cdot (n - 2)!} = 66}$$ $${\frac{n \cdot (n - 1) \cdot (n - 2!}{2 \cdot (n - 2)!} = 66}$$ $${\frac{n \cdot (n - 1)}{2} = 66}$$ $${n \cdot (n - 1) = 132}$$ $${n^2 - n = 132}$$ $${n^2 - n - 132 = 0}$$

$${n_{1,2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} = \frac{-(-1) \pm \sqrt{(-1)^2 - 4\cdot 1 \cdot (-132)}}{2 \cdot 1} = \frac{1 \pm \sqrt{529}}{2} = \frac{1 \pm 23}{2}}$$

$${n_1 = \frac{1 + 23}{2} = \frac{24}{2} = 12}$$

$${n_2 = \frac{1 - 23}{2} = \frac{-22}{2} = -11}$$

Protože řešením mohou být pouze přirozená čísla, je řešením pouze číslo 12.

Počet kombinací šesté třídy z neznámého počtu prvků vyjadřuje kombinační číslo ${{n \choose 6}}$. V případě počtu kombinací třetí třídy se bude jednat o kombinační číslo ${{n \choose 3}}$. Kombinací 6. třídy má být jedenáctkrát více než kombinací třetí třídy. Sestavíme tedy následující rovnici:

$${{n \choose 6} = 11 \cdot {n \choose 3}}$$

$${\frac{n!}{6!\cdot (n - 6)!} = 11 \cdot \frac{n!}{3!\cdot (n - 3)!}}$$

$${\frac{n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdot (n - 4) \cdot (n - 5) \cdot (n - 6)!}{6!\cdot (n - 6)!} = 11 \cdot \frac{n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3)!}{3!\cdot (n - 3)!}}$$

$${\frac{n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdot (n - 4) \cdot (n - 5)}{6!} = 11 \cdot \frac{n \cdot (n - 1) \cdot (n - 2)}{3!}}$$

$${\frac{n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdot (n - 4) \cdot (n - 5)}{6 \cdot 5 \cdot 4 \cdot 3!} = 11 \cdot \frac{n \cdot (n - 1) \cdot (n - 2)}{3!} | \cdot 6 \cdot 5 \cdot 4 \cdot 3!}$$

$${n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3) \cdot (n - 4) \cdot (n - 5) = 11 \cdot 6 \cdot 5 \cdot 4 \cdot n \cdot (n - 1) \cdot (n - 2) | : n(n-1)(n-2)}$$

$${(n - 3) \cdot (n - 4) \cdot (n - 5) = 11 \cdot 6 \cdot 5 \cdot 4}$$

$${(n - 3) \cdot (n - 4) \cdot (n - 5) = 1320}$$

Zjednodušením rovnice jsme získali rovnici, kde se v součinu ${(n - 3) \cdot (n - 4) \cdot (n - 5)}$ bude vyskytovat ${n^3}$. Rovnici zkusíme vyřešit tak, že za ${n}$ budeme postupně dosazovat hodnoty tak, aby platila daná rovnost.

Situaci nám trochu zjednoduší fakt, že ${n}$ musí být přirozené číslo větší než 5.

Hodnota výrazu ${(n - 3) \cdot (n - 4) \cdot (n - 5)}$ pro:

${n = 6 \longrightarrow (6 - 3) \cdot (6 - 4) \cdot (6 - 5) = 3 \cdot 2 \cdot 1 = 6}$

${n = 7 \longrightarrow (7 - 3) \cdot (7 - 4) \cdot (7 - 5) = 4 \cdot 3 \cdot 2 = 24}$

${n = 8 \longrightarrow (8 - 3) \cdot (8 - 4) \cdot (8 - 5) = 5 \cdot 4 \cdot 3 = 60}$

${n = 9 \longrightarrow (9 - 3) \cdot (9 - 4) \cdot (9 - 5) = 6 \cdot 5 \cdot 4 = 120}$

${n = 10 \longrightarrow (10 - 3) \cdot (10 - 4) \cdot (10 - 5) = 7 \cdot 6 \cdot 5 = 210}$

${n = 11 \longrightarrow (11 - 3) \cdot (11 - 4) \cdot (11 - 5) = 8 \cdot 7 \cdot 6 = 336}$

${n = 12 \longrightarrow (12 - 3) \cdot (12 - 4) \cdot (12 - 5) = 9 \cdot 8 \cdot 7 = 504}$

${n = 13 \longrightarrow (13 - 3) \cdot (13 - 4) \cdot (13 - 5) = 10 \cdot 9 \cdot 8 = 720}$

${n = 14 \longrightarrow (14 - 3) \cdot (14 - 4) \cdot (14 - 5) = 11 \cdot 10 \cdot 9 = 990}$

${n = 15 \longrightarrow (15 - 3) \cdot (15 - 4) \cdot (15 - 5) = 12 \cdot 11 \cdot 10 = 1320}$

Pro ${n = 15}$ platí požadovaná rovnost. Počet prvků, který odpovídá našemu zadání je tedy 15.