Kombinatorika
a pravděpodobnost

KOMBINATORIKA

L19: Kombinace bez opakování

<< Předchozí lekce | Seznam lekcí | Další lekce >>

Kromě variací a permutací máme ještě třetí typ kombinatorických skupin. Tím jsou kombinace. V tomto případě (narozdíl od předchozích dvou typů) již nezávisí na pořadí.

Kombinace bez opakování
k-členná kombinace bez opakování z n prvků je neuspořádaná k-tice sestavená z n-prvků tak, že každý se v ní vyskytuje právě jednou.
Příklad L19.01:

Máme 4 prvky označené A, B, C, D:
a) Kolik různých tříčlenných variací můžeme vytvořit? Vypište je.
b) Kolik různých tříčlenných kombinací můžeme vytvořit? Vypište je.

Řešení

a)

$${V(3, 4) = \frac{4!}{(4-3)!} = 4\cdot3\cdot2 = 24}$$

ABC ABD ACD BCD
ACB ADB ADC BDC
BAC BAD CAD CBD
BCA BDA CDA CDB
CAB DAB DAC DBC
CBA DBA DCA DCB

Ze 4 prvků lze vytvořit 24 tříčlenných variací.

b)

Protože zatím neznáme vzorec pro výpočet počtu kombinací, zkusíme počet zjistit na základě výpisu všech možností.

Když se podíváme na výpis v první části příkladu, tak každý sloupec představuje jednu kombinaci (řádky se liší jen pořadím).

ABC ABD ACD BCD
ACB ADB ADC BDC
BAC BAD CAD CBD
BCA BDA CDA CDB
CAB DAB DAC DBC
CBA DBA DCA DCB

Ze 4 prvků lze vytvořit 4 tříčlenné kombinace.

Pro výpočet počtu kombinací bez opakování použijeme kombinační číslo.

Počet všech k-prvkových kombinací bez opakování z n prvků
Pro počet všech k-prvkových kombinací bez opakování z n prvků platí vztah: $${C(k, n) = \binom{n}{k} = {{n!}\over{k!\cdot(n - k)!}}}$$
Příklad L19.02:

Kolikati způsoby lze vybrat 5 žáků, kteří se zúčastní matematické olympiády, ve třídě, kde je 30 žáků?

Řešení

Jedná se o kombinaci 5. řádu z 30: $${C(5,30) = {30 \choose 5} = \frac{30!}{5!\cdot (30 - 5)!} = \frac{30!}{5!\cdot 25!} = \frac{30 \cdot 29 \cdot 28 \cdot 27 \cdot 26}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 142~506}$$

Příklad L19.03:

V soutěžní porotě je 10 porotců, 7 hlasovalo pro, 3 proti. Kolika způsoby to mohlo nastat?

Řešení

Pro zjištění počtu možností výsledků hlasování stačí určit počet možností pro hlasování pro, vybíráme tedy kombinace sedmého řádu z 10.

$${C(7,10) = {10 \choose 7} = \frac{10!}{7!\cdot (10 - 7)!} = \frac{10!}{7!\cdot 3!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120}$$

Zadaný výsledek hlasování mohl nastat 120 způsoby.

Příklad L19.04:

Kolika způsoby lze ze 7 chlapců a 5 dívek sestavit volejbalové družstvo o šesti členech, mají-li v něm být právě 3 dívky?

Řešení

Z 5 dívek vybíráme trojici. Jedná se tedy o kombinaci třetího řádu z 5 prvků. Dosadíme do vzorečku z úvodu kapitoly:

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

Zbývá ještě obsadit 3 místa v týmu pro chlapce. Protože je celkem 7 chlapců, jedná se o kombinaci třetího řádu ze 7 prvků. Opět dosadíme:

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

Zjistili jsme, že dívky lze vybrat 10 způsoby a chlapce 35 způsoby. Použitím kombinatorického pravidla součinu získáme celkový výsledek.

$${10 \cdot 35 = 350}$$

Volejbalové družstvo lze sestavit 350 způsoby.

Příklad L19.05:

Určete, kolik přímek je určeno deseti různými body, z nichž žádné 3 neleží na jedné přímce.

Řešení

Přímka je dána dvěma body (kdy nezáleží na pořadí - přímka AB je stejná jako přímka BA). Vytváříme tedy kombinace druhého řádu z 10 prvků.

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

Deseti různými body, z nichž žádné 3 neleží na jedné přímce, je určeno 45 přímek.

Příklad L19.06:

Určete, kolik přímek je určeno deseti různými body, jestliže právě 4 leží na jedné přímce.

Řešení

Řešení úkolu rozdělíme na 2 části. Nejprve určíme počet přímek v situaci, kdy by žádné 3 body neležely na stejné přímce.

Přímka je dána dvěma body (kdy nezáleží na pořadí - přímka AB je stejná jako přímka BA). Vytváříme tedy kombinace druhého řádu z 10 prvků.

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

Následně budeme řešit situaci, kdy 4 body leží na jedné přímce. Je třeba zjistit, kolik přímek by mohly vytvořit tyto čtyři body. Všechny takové přímky budou totožné, budeme je tedy počítat jako jednu přímku. V tomto případě se bude jednat o kombinaci druhého řádu ze 4 prvků:

$${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 přímek tedy bude:

$${C(2,10) - C(2,4) + 1 = {10 \choose 2} - {4 \choose 2} + 1 = 45 - 6 + 1 = 40}$$

Deseti různými body, z nichž právě 4 leží na jedné přímce, je určeno 45 přímek.

Příklad L19.07:

V obchodě prodávají 2 typy kódových zámků. Na obou zámcích jsou tlačítka označená čísly 0 až 9. U prvního zámku je nutné zmáčknout 4 tlačítka (zůstanou zamáčknuté), u druhého zámku stejným způsobem 6 tlačítek. Který zámek je bezpečnější?

Řešení

O bezpečnosti zámku rozhodneme na základě počtu kombinací.

V prvním případě se jedná o kombinaci 4. řádu z 10 prvků. $${C(4,10) = {10 \choose 4} = \frac{10!}{4!\cdot (10 - 4)!} = \frac{10!}{4!\cdot 6!} = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210}$$

Ve druhém případě se jedná o kombinaci 6. řádu z 10 prvků. $${C(6,10) = {10 \choose 6} = \frac{10!}{6!\cdot (10 - 6)!} = \frac{10!}{6!\cdot 4!} = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = 210}$$

Zjistili jsme, že v obou případech se jedná zámek s 210 kombinacemi - zámky jsou tedy stejně bezpečné.

Pozn.: Z lekce věnující se vlastnostem kombinačních čísel již víme, že ${{n \choose k} = {n \choose n - k}}$, tedy ${{10 \choose 4} = {10 \choose 6}}$

Příklad L19.08:

V sázkové hře EUROMILIONY vybíráme 7 čísel z 35 a jedno číslo z 5.
a) Kolik možností vyplnění tiketu máme?
b) Kolik možností vyplnění tiketu tak, aby ve skupině 7 čísel byla čísla 1 a 2, máme?
c) Kolik možností vyplnění tiketu tak, aby ve skupině 7 čísel nebylo číslo 12, máme?

Řešení

a)

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

Výběr 7 čísel z 35 je dán počtem kombinací sedmého řádu z 35.

$${C(7, 35) = {35 \choose 7} = \frac{35!}{7! \cdot (35 - 7)!} = \frac{35!}{7! \cdot 28!} = 6~724~520}$$

Dle kombinatorického pravidla součinu získáme celkový počet:

$${5 \cdot C(7, 35) = 5 \cdot 6~724~520 = 33~622~600}$$

b)

Pokud mají být v losovaných číslech čísla 1 a 2, vybíráme 5 čísel ze 33 (2 jsou totiž pevně daná) a k tomu 1 z 5.

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

Výběr 5 čísel ze 33 je dán počtem kombinací pátého řádu ze 33.

$${C(5, 33) = {33 \choose 5} = \frac{33!}{5! \cdot (33 - 5)!} = \frac{33!}{5! \cdot 28!} = 237~336}$$

Dle kombinatorického pravidla součinu získáme celkový počet:

$${5 \cdot C(5, 33) = 5 \cdot 237~336 = 1~186~680}$$

c)

Pokud v losovaných číslech nemá být číslo 12, zjistíme počet možností výběru 7 čísel z 35, následně odečteme všechny možnosti, které obsahují číslo 12 (tedy 6 čísel z 34). Následně také vybíráme 1 číslo z 5.

$${C(7, 35) = {35 \choose 7} = \frac{35!}{7! \cdot (35 - 7)!} = \frac{35!}{7! \cdot 28!} = 6~724~520}$$

Počet možností, které obsahují číslo 12:

$${C(6, 34) = {34 \choose 6} = \frac{34!}{6! \cdot (34 - 6)!} = \frac{34!}{6! \cdot 28!} = 1~344~904}$$

Celkový počet možností:

$${\left[C(7, 35) - C(6, 34)\right] \cdot 5 = \left(6~724~520 - 1~344~904\right) \cdot 5 = 26~898~080}$$

Příklad L19.09:

Určete, kolika způsoby lze vyplnit tiket hry "Šťastných 10", pokud víte, že vybíráte 1 až 10 čísel z 80 (pozn.: vyjádřete kombinačními čísly).

Řešení

V tomto případě si řešení rozdělíme na jednotlivé varianty dle počtu vsazených čísel.

1. Pokud vsadíme jedno číslo, bude se jednat o kombinaci prvního řádu z 80:

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

2. Pokud vsadíme jedno číslo, bude se jednat o kombinaci druhého řádu z 80:

$${C(2, 80) = {80 \choose 2} = \frac{80!}{2! \cdot (80 - 2)!} = \frac{80!}{2! \cdot 78!} = 3160}$$

3. Pokud vsadíme jedno číslo, bude se jednat o kombinaci třetího řádu z 80:

$${C(3, 80) = {80 \choose 3} = \frac{80!}{3! \cdot (80 - 3)!} = \frac{80!}{3! \cdot 77!} = 82160}$$

4. Pokud vsadíme jedno číslo, bude se jednat o kombinaci čtvrtého řádu z 80:

$${C(4, 80) = {80 \choose 4} = \frac{80!}{4! \cdot (80 - 4)!} = \frac{80!}{4! \cdot 76!} = 1581580}$$

5. Pokud vsadíme jedno číslo, bude se jednat o kombinaci pátého řádu z 80:

$${C(5, 80) = {80 \choose 5} = \frac{80!}{5! \cdot (80 - 5)!} = \frac{80!}{5! \cdot 75!} = 24040016}$$

6. Pokud vsadíme jedno číslo, bude se jednat o kombinaci šestého řádu z 80:

$${C(6, 80) = {80 \choose 6} = \frac{80!}{6! \cdot (80 - 6)!} = \frac{80!}{6! \cdot 74!} = 300500200}$$

7. Pokud vsadíme jedno číslo, bude se jednat o kombinaci sedmého řádu z 80:

$${C(7, 80) = {80 \choose 7} = \frac{80!}{7! \cdot (80 - 7)!} = \frac{80!}{7! \cdot 73!} = 3176716400}$$

8. Pokud vsadíme jedno číslo, bude se jednat o kombinaci osmého řádu z 80:

$${C(8, 80) = {80 \choose 8} = \frac{80!}{8! \cdot (80 - 8)!} = \frac{80!}{8! \cdot 72!} = 28987537150}$$

9. Pokud vsadíme jedno číslo, bude se jednat o kombinaci devátého řádu z 80:

$${C(9, 80) = {80 \choose 9} = \frac{80!}{9! \cdot (80 - 9)!} = \frac{80!}{9! \cdot 71!} = 2,319 \cdot 10^{11}}$$

10. Pokud vsadíme jedno číslo, bude se jednat o kombinaci desátého řádu z 80:

$${C(10, 80) = {80 \choose 10} = \frac{80!}{10! \cdot (80 - 10)!} = \frac{80!}{10! \cdot 70!} = 1,646 \cdot 10^{12}}$$

Celkový výsledek získáme sečtením jednotlivých výsledků:

$${C(1, 80) + C(2, 80) + C(3, 80) + C(4, 80) + C(5, 80) + C(6, 80) + C(7, 80) + C(8, 80) + C(8, 80) + C(9, 80) + C(10, 80) = }$$ $${= {80 \choose 1} + {80 \choose 2} + {80 \choose 3} + {80 \choose 4} + {80 \choose 5} + {80 \choose 6} + {80 \choose 7} + {80 \choose 8} + {80 \choose 9} + {80 \choose 10} = }$$

Zápis za pomocí vlastností kombinačních čísel můžeme zjednodušit:

$${= {81 \choose 2} + {81 \choose 4} + {81 \choose 6} + {81 \choose 8} + {81 \choose 10} \doteq 1,91 \cdot 10^12 }$$

Příklad L19.10:

Kolik je třeba vzít prvků, aby z nich šlo vytvořit třikrát více kombinací šesté třídy než kombinací čtvrté třídy?

Řešení

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í čtvrté třídy se bude jednat o kombinační číslo ${{n \choose 4}}$. Kombinací 6. třídy má být třikrát více než kombinací čtvrté třídy. Sestavíme tedy následující rovnici:

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

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

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

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

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

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

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

$${n^2 - 9n + 20 = 90}$$

$${n^2 - 9n - 70 = 0}$$

$${D = b^2 - 4ac = (-9)^2 - 4 \cdot 1 \cdot (-70) = 81 + 280 = 361}$$

$${n_{1,2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} = \frac{-(-9) \pm \sqrt{(-9)^2 - 4\cdot 1 \cdot (-70)}}{2 \cdot 1} = \frac{9 \pm \sqrt{361}}{2} = \frac{9 \pm 19}{2}}$$

$${n_1 = \frac{9 + 19}{2} = \frac{28}{2} = 14}$$

$${n_2 = \frac{9 - 19}{2} = \frac{-10}{2} = -5}$$

Protože počet prvků je z množiny přirozených čísel, je řešením pouze ${n_1 = 14}$.

Kontrolní otázky
  1. Co je to "kombinace bez opakování"?
  2. Pomocí jakého vzorce vypočítáme počet kombinací bez opakování?
  3. V sázkové hře "Sportka" se vybírá 6 čísel ze 49. Kolik existuje možností vyplnění tiketu?
Řešení
  1. k-členná kombinace bez opakování z n prvků je neuspořádaná k-tice sestavená z n-prvků tak, že každý se v ní vyskytuje právě jednou.
  2. $${C(k, n) = \binom{n}{k} = {{n!}\over{k!\cdot(n - k)!}}}$$
  3. $${{49 \choose 6} = 13~983~816}$$

<< Předchozí lekce | Seznam lekcí | Další lekce >>

Copyright © 2014 Ing. Michal Heczko