Přírodovědecká fakulta Masarykovy univerzity
Bc. Monika Stančíková
Kombinace bez opakování
Ve variacích (i permutacích) vždy záleželo na pořadí, v jakém jsme vybrané prvky uspořádávali. V kombinacích tomu tak není, na jejich pořadí nezáleží.
Stále prvky mezi sebou rozlišujeme (nemohou se opakovat) a každý se může vyskytovat nejvýše jednou.
Úvodní příklady
Příklad 1 - Variace a dvojice
Kolik existuje uspořádaných dvojic ze čtyř písmen - A B C D ? (Uspořádaných = záleží na pořadí.)
Řešení:(skrýt text)
Všechny dvojice ze čtyř písmen - A B C D jsou:
AB AC AD BC BD CD
BA CA DA CB DB DC
Příklad 2 - Kombinace a dvojice
Kolik existuje neuspořádaných dvojic ze čtyř písmen - A B C D ? (Nezáleží na pořadí prvků, proto dvojice AB i BA je nyní stejná kombinace.)
(Jinými slovy: Kolik existuje 2-prvkových podmnožin 4-prvkové množiny?)
Řešení:(skrýt text)
| AB BA | AC CA | AD DA | BC CB | BD DB | CD DC |
Když se pozorně podíváme na výpis, všimneme si, že neuspořádaných dvojic je přesně 2x méně.
Každý sloupec tvoří 2 stejné písmena jinak uspořádané = permutace 2 prvků.
Počet dvou-prvkových permutací je 2! = 2, to určuje i počet řádků.
Proto, pokud nezáleží na pořadí, vydělíme výsledek 2! a získáme počet neuspořádaných dvojic.
Výsledek: $\dfrac{4 \cdot 3}{2!} = \dfrac{12}{2} = 6$.
Výpis všech neuspořádaných dvojic ze 4 prvků:
AB AC AD BC BD CD
Příklad 3 - Variace a trojice
Kolik existuje uspořádaných trojic ze čtyř písmen - A B C D ? (Uspořádaných = záleží na pořadí.)
Řešení: (skrýt text)
Všechny trojice ze čtyř písmen - A B C D jsou:
ABC ABD ACD BCD
ACB ADB ADC BDC
BAC BAD CAD CBD
BCA BDA CDA CDB
CAB DAB DAC DBC
CBA DBA DCA DCB
Příklad 4 - Kombinace a trojice
Kolik existuje neuspořádaných trojic ze čtyř písmen - A B C D ? (Nezáleží na pořadí prvků.)
(Jinými slovy: Kolik existuje 3-prvkových podmnožin 4-prvkové množiny?)
Řešení:(skrýt text)
| ABC ACB BAC BCA CAB CBA |
ABD ADB BAD BDA DAB DBA |
ACD ADC CAD CDA DAC DCA |
BCD BDC CBD CDB DBC DCB |
Každý sloupec tvoří 3 stejné prvky jinak uspořádané = permutace tří prvků.
Počet tří-prvkových permutací je 3! = 6, to určuje i počet řádků.
Proto, pokud nezáleží na pořadí, vydělíme výsledek 3! a získáme počet neuspořádaných trojic.
Výsledek: $\dfrac{4 \cdot 3 \cdot 2}{3!} = \dfrac{24}{6} = 4$.
Výpis všech neuspořádaných trojic ze 4 prvků:
ABC ABD ACD BCD
Příklad 5 - Zkoušení studentů
Ve třídě je 30 žáků. Kolika způsoby můžeme vybrat 3 žáky na zkoušení? (Žáci jsou zkoušeni zároveň = nezáleží na jejich pořadí.)
Řešení:(skrýt text)
Vybereme trojici žáků: $30 \cdot 29 \cdot 28$
Nezáleží na pořadí, proto vydělíme ještě $3!$.
Výsledek: $\dfrac{30 \cdot 29 \cdot 28}{3!} = 4060$.
Shrnutí:
Všimněte si, že pokud jsme tvořili neuspořádané dvojice, vypočítali jsme variace a výsledek vydělili 2!.
Pokud jsme chtěli neuspořádané trojice, vypočítali jsme opět variace a výsledek vydělili 3!.
Jak by tomu bylo u čtveřic? ... Výsledek by se vydělil 4!.
Uvědomili jste si na příkladech, proč tomu tak bylo?
Definice
Jinak řečeno:
$k$-členná kombinace z $n$ prvků je $k$-prvková podmnožina množiny těmito $n$ prvky určená.
Pro vyjádření $K(k, n)$ užíváme i symbol $\dbinom{n}{k} $. Nazývá se kombinační číslo a čte se "$n$ nad $k$".
Pro všechna celá nezáporná čísla $n, k$, kde $k \leq n$, je: $$ K(k,n) = \dbinom{n}{k} = \frac{n!}{k!(n-k)!} $$
Kombinační číslo - odvození(zobrazit text)
Řešené příklady
Příklad 1 - Knihy
Alena má 10 knih, které ještě nepřečetla. Odjíždí na dovolenou a chtěla by si vzít 2 knihy s sebou. Kolik má různých možností, jaké knihy si vybrat?
Řešení:(skrýt text)
Z 10 knih vybíráme 2 tak, že nezáleží na jejich pořadí:
$${10 \choose 2} $$
Obvykle si s tímto výsledkem vystačíme. Ale zkusme si nyní i rozepsat:
$${10 \choose 2} = \frac{10!}{2!(10-2)!} = \frac{10!}{2!8!} = \frac{10 \cdot 9 \cdot 8!}{2!8!} = \frac{10 \cdot 9}{2 \cdot 1} = 5 \cdot 9 = 45.$$
Porovnejme s postupem z úvodu:
$\dfrac{10 \cdot 9}{2!} = \dfrac{10 \cdot 9}{2 \cdot 1} = 5 \cdot 9 = 45$.
Příklad 2 - Šachovnice
Určete, kolika způsoby lze na šachovnici (8 x 8 políček) vybrat:
A) 3 políčka?
B) 3 políčka neležící ve stejném sloupci?
C) 3 políčka neležící ve stejném sloupci ani ve stejné řadě?
D) 3 políčka, která nejsou všechna stejné barvy?
Řešení:(skrýt text)
A) Na šachovnici je 64 políček. Z nich vybíráme 3:
$${64 \choose 3} $$
Zkusme si i nyní rozepsat:
$$ {64 \choose 3} = \frac{64!}{3!(64-3)!} = \frac{64!}{3! \cdot 61!} =
\frac{64 \cdot 63 \cdot 62 \cdot 61!}{3! \cdot 61!} = \frac{64 \cdot 63 \cdot 62}{3 \cdot 2 \cdot 1} = 64 \cdot 21 \cdot 31 = 41664. $$
B) Od všech trojic odečteme ty trojice, které leží ve stejném sloupci.
Kolik je trojic, které leží ve stejném sloupci? Z 8 políček v jednom sloupci vybíráme 3:
$${8 \choose 3}$$
Sloupců je 8, proto toto číslo musíme odečíst osmkrát. Náš výsledek:
$${64 \choose 3} - 8 \cdot {8 \choose 3} \qquad [=41216]$$
C) Od výsledku v bodě B) ještě odečteme trojice, které leží ve stejné řadě. Kolik jich je? $$ 8 \cdot {8 \choose 3}$$ Výsledek: $${64 \choose 3} - 8 \cdot {8 \choose 3} - 8 \cdot {8 \choose 3} = {64 \choose 3} - 16 \cdot {8 \choose 3} \qquad [=40768] $$
D) Od všech trojic odečteme ty trojice, které jsou bílé barvy, a trojice, které jsou černé barvy.
Políček bílé barvy je 32.
Políček černé barvy je 32.
Výsledek:
$${64 \choose 3} - {32 \choose 3} - {32 \choose 3} = {64 \choose 3} - 2 \cdot {32 \choose 3} \qquad [=31744]$$
V tomto případě jsme mohli postupovat i jinak.
Chceme znát počet trojic, které nejsou stejné barvy. Tedy jsou to trojice, kde je buď 1 políčko černé a 2 bílé, nebo 1 bílé a 2 černé. Těch je:
$${32 \choose 2} \cdot {32 \choose 1} + {32 \choose 1} \cdot {32 \choose 2} = {32 \choose 2} \cdot 32 + 32 \cdot {32 \choose 2} = 64 \cdot {32 \choose 2} \qquad [=31744] $$
Příklad 3 - Ženy a muži
Určete, kolika způsoby je možno ze sedmi mužů a čtyř žen vybrat šestičlennou skupinu, v níž jsou
a) právě dvě ženy?
b) aspoň dvě ženy?
c) nejvýše dvě ženy?
Řešení:(skrýt text)
a) Vybíráme 2 ženy ze 4 a zároveň 4 muže ze 7, nezáleží na pořadí: $${4 \choose 2} \cdot {7 \choose 4} \qquad [=210]$$
b) V tomto případě můžeme vybrat:
2 ženy a 4 muže nebo
3 ženy a 3 muže nebo
4 ženy a 2 muže
Výsledek: $${4 \choose 2} \cdot {7 \choose 4} + {4 \choose 3} \cdot {7 \choose 3} + {4 \choose 4} \cdot {7 \choose 2} \qquad [=371]$$
c) V tomto případě můžeme vybrat:
2 ženy a 4 muže nebo
1 ženu a 5 mužů nebo
žádnou ženu a 6 mužů
Výsledek: $${4 \choose 2} \cdot {7 \choose 4} + {4 \choose 1} \cdot {7 \choose 5} + {4 \choose 0} \cdot {7 \choose 6} = {4 \choose 2} \cdot {7 \choose 4} + {4 \choose 1} \cdot {7 \choose 5} + {7 \choose 6} \qquad [=301]$$
Příklady k procvičení
Příklad 1
Volejbalový turnaj je rozdělen na 3 skupiny. V každé skupině je 6 týmů. V rámci skupiny hraje každý tým s každým.
A) Kolik zápasů se v turnaji odehraje?
B) Kolik zápasů se v turnaji odehraje, hrají-li ještě vítězové všech skupin každý s každým o celkové první místo?
Řešení: (zobrazit text)
Příklad 2
Jaký bude celkový počet podání rukou:
1. jsou-li v místnosti 3 lidé a každý si podává ruku s každým?
2. přijde-li dalších 5 lidí? Původní 3 lidé si už ruce mezi sebou nepodávají.
Řešení: (zobrazit text)
Příklad 3
A) Kolika způsoby je možno z 18 kamarádů vybrat 9?
B) Kolika způsoby je možno z 18 kamarádů vybrat 9 požadujeme-li, že kamarád Pepa nebude mezi vybranými?
C) Kolika způsoby je možno z 18 kamarádů vybrat 9 požadujeme-li, že mezi vybranými nebudou zároveň obě kamarádky Katka a Žofka?
D) Kolika způsoby je možno z 18 kamarádů vybrat 9 požadujeme-li, aby mezi vybranými byl alespoň jeden z kamarádů Honza nebo Sláva?
Řešení: (zobrazit text)
Příklad 4
Petr má sedm knih, o které se zajímá Ivana, Ivana má deset knih, o které se zajímá Petr. Určete, kolika způsoby si Petr může vyměnit dvě své knihy za dvě knihy Ivaniny.
Řešení: (zobrazit text)
Příklad 5
Vyjádřete kombinačními čísly, kolika způsoby může $m$ chlapců a $n$ dívek utvořit taneční pár.
Řešení: (zobrazit text)
Příklad 6
Je dán čtverec KLMN. Na každé straně čtverce zvolíme 8 vnitřních bodů.
A) Určete počet všech trojúhelníků, jejichž vrcholy leží v daných bodech.
B) Určete počet všech trojúhelníků, jejichž vrcholy leží v daných bodech a každé dva vrcholy jednoho trojúhelníku leží na různých stranách čtverce.
Řešení: (zobrazit text)
Příklad 7
Na běžecké trati běží 8 závodníků. Do finále postupují první tři. Kolik je možností na postupující trojici?
Řešení: (zobrazit text)
Příklad 8
Kolika způsoby lze rozdělit 12 hráčů na dvě šestičlenná družstva?
Řešení: (zobrazit text)
Příklad 9
Kolika způsoby lze 4 dívky a 8 chlapců rozdělit na dvě šestičlenná volejbalová družstva tak, aby v každém družstvu byla dvě děvčata a 4 chlapci?
Řešení: (zobrazit text)
Příklad 10
Ve skupině je 20 dětí, každé dvě děti mají jiné jméno. Je mezi nimi i Alena a Jana. Kolika způsoby lze vybrat 8 dětí tak, aby mezi vybranými:
a) byla Alena,
b) nebyla Alena,
c) byla Alena a Jana,
d) byla alespoň jedna z dívek Alena, Jana,
e) byla nejvýše jedna z dívek Alena, Jana,
f) nebyla ani Alena, ani Jana?
Řešení: (zobrazit text)
Příklad 11
Kolika způsoby lze 20 dětí rozdělit do tří skupin tak, aby v první skupině bylo 10 dětí, ve druhé skupině bylo 6 dětí a ve třetí zbytek?
Řešení: (zobrazit text)
Příklad 12
V sérii 12 výrobků jsou právě 3 vadné. Kolika způsoby z nich lze vybrat:
a) 6 libovolných výrobků,
b) 6 výrobků bezvadných,
c) 6 výrobků, z nichž právě 1 je vadný,
d) 6 výrobků, z nichž právě 2 jsou vadné,
e) 6 výrobků, z nichž právě 3 jsou vadné?
Řešení: (zobrazit text)
Příklad 13
Kolika způsoby je možné vybrat z přirozených čísel menších nebo rovných 30 tři různá čísla tak, aby jejich součet byl roven sudému číslu?
Řešení: (zobrazit text)
ÚMS, Přírodovědecká fakulta, Masarykova univerzita |
Návrat na úvodní stránku webu, přístupnost |
| Servisní středisko pro e-learning na MU
| Fakulta informatiky Masarykovy univerzity, 2013