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: $(4 \cdot 3) / 2! = 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 ACD ABD BCD
BAC CAD BAD CBD
ACB ADC ADB BDC
BCA CDA BDA CDB
CAB DAC DAB DBC
CBA DCA DBA 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 BAC ACB BCA CAB CBA |
ACD CAD ADC CDA DAC DCA |
ABD BAD ADB BDA DAB DBA |
BCD CBD BDC 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: $(4 \cdot 3 \cdot 2) / 3! = 24 / 6 = 4$.
Výpis všech neuspořádaných trojic ze 4 prvků:
ABC ACD ABD BCD
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řikladech, 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 ${n \choose k} $. Nazývá se Kombinační číslo a čte se "n nad k".
Pro všechna celá nezáporná čísla n, k, kde k≤n, je: $$ {n \choose k} = \frac{n!}{k!(n-k)!} $$
Kombinační číslo - odvození(zobrazit text)
Řešené příklady
Příklad 1 - Šachovnice
Určete, kolika způsoby lze na šachovnici (8 x 8 políček) vybrat:
A) trojici políček?
B) trojici políček neležících ve stejném sloupci?
C) trojici políček neležících ve stejném sloupci ani ve stejné řadě?
D) trojici políček, která nejsou všechna stejné barvy?
Řešení:(skrýt text)
A) Na šachovnici je 64 políček. Z nich vybíráme trojice.
k = 3, n = 64. Výsledek:
$${64 \choose 3}$$
Obvykle si s tímto výsledkem vystačíme. Ale zkusme si nyní i 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}$$
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}$$
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}$$
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}$$
Příklad 2 - Ž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} $$
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}$$
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} $$
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 celkém 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)
Ú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