Kombinace s opakováním

Všechny dvojice ze čtyř písmen - A B C D jsou:
               AB    AC    AD    BC    BD    CD
               BA    CA    DA    CB    DB    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

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

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

$$ {n \choose k} = \frac{n!}{k!(n-k)!} $$

Odvození:

Podle definice: $ K(k,n) = V(k,n) / k! $

$ V(k,n) = n(n - 1)(n - 2) \dots (n - k + 1) = \frac{n!}{(n-k)!} $     (Počítání s faktoriály.)

Dohromady: $ K(k,n) = \frac{n!}{(n-k)!} / k! = \frac{n!}{k!(n-k)!} $

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}$$

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} $$

A) $3 \cdot {6 \choose 2}$.

B) $3 \cdot {6 \choose 2} + {3 \choose 2}$.

A) ${18 \choose 9}$

B) $18-1=17, {17 \choose 9}$

C) Požadujeme, aby ve výběru nebyli obě zároveň. Tedy právě jedna z nich tam být může. Od všech možností odešteme ty, kde jsou obě kamarádky zároveň.
Všech je: ${18 \choose 9}$.
Ke Katce a Žofce vybereme dalších 7 lidí. Proto počet možností, kde jsou obě kamarádky zároveň je ${16 \choose 7}$.
Celkem: ${18 \choose 9}-{16 \choose 7}$.

D) Alespoň jeden z kamarádů Honza nebo Sláva. Tedy buď jen Honza, nebo jen Sláva, nebo oba:
K Honzovi vybereme dalších 8 kamarádů, ze skupinky, kde není Sláva. + Podobně ke Slávovi. + K oběma vybereme dalších 7 kamarádů.
${16 \choose 8}+{16 \choose 8}+{16 \choose 7} = 2 \cdot {16 \choose 8}+{16 \choose 7}$.