Přechod na menu, Přechod na obsah, Přechod na patičku
     

Kombinace s opakováním



Ú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)

dvojice: _ _ $4 \cdot 3 = 12$.

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)

Uspořádaných dvojic bylo: $4 \cdot 3 = 12$.
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)

trojice: _ _ _ $4 \cdot 3 \cdot 2 = 24$

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)

Uspořádaných trojic bylo: $4 \cdot 3 \cdot 2 = 24$.
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

Definice: k-členná kombinace z n prvků je neuspořádaná k-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje nejvýše jednou.

Jinak řečeno:

k-členná kombinace z n prvků je k-prvková podmnožina množiny těmito n prvky určená.


Definice: Počet K(k,n) všech k-členných kombinací z n prvků je:

K(k, n) = V(k, n) / k! .


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 kn, 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)


Autor_1, Autor_2 |
ÚMS, Přírodovědecká fakulta, Masarykova univerzita |
Návrat na úvodní stránku webu, přístupnost |
Stránky Přírodovědecká fakulty MU
| Šablonu poskytlo:
| Servisní středisko pro e-learning na MU
| Fakulta informatiky Masarykovy univerzity, 2013