Kombinace bez opakování

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 dvouprvkový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

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

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

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

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

Odvození:

Podle definice: $ K(k,n) = \dfrac{V(k,n)}{k!} $

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

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

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

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

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

A) $3 \cdot \dbinom{6}{2} \qquad [=45]$

B) $3 \cdot \dbinom{6}{2} + \dbinom{3}{2} \qquad [=48]$

1. Uvědomme si, že se jedná o počet neuspořádaných dvojic, které můžeme sestavit ze 3 lidí,
výsledek: $\dbinom{3}{2} \qquad [=3]$

2. $\dbinom{8}{2} - \dbinom{3}{2} \qquad [=25]$

A) $\dbinom{18}{9} \qquad [=48620]$

B) $18-1=17, \dbinom{17}{9} \qquad [=24310]$

C) Požadujeme, aby ve výběru nebyli obě kamarádky zároveň. Od všech možných způsobů výběru tedy odečteme ty, kde jsou obě kamarádky zároveň.
Všech je: $\dbinom{18}{9}$.
Ke Katce a Žofce vybereme dalších 7 lidí, proto počet možností, kde jsou obě kamarádky zároveň je $\dbinom{16}{7}$.
Celkem: $\dbinom{18}{9}-\dbinom{16}{7} \qquad [=37180]$

D) Způsoby rozdělíme na tři disjunktní případy:
I. mezi vybranými je jen Honza; II. mezi vybranými je jen Sláva; III. mezi vybranými kamarády jsou Honza i Sláva zároveň.
I. K Honzovi vybereme dalších 8 kamarádů, ze skupinky, kde není Sláva. II. Analogicky i ke Slávovi. III. K oběma kamarádům vybereme dalších 7 kamarádů.
$\dbinom{16}{8}+\dbinom{16}{8}+\dbinom{16}{7} = 2 \cdot \dbinom{16}{8}+\dbinom{16}{7} \qquad [=37180]$

$\dbinom{7}{2} \cdot \dbinom{10}{2} \qquad [=945]$

$\dbinom{m+n}{2} - \dbinom{m}{2} - \dbinom{n}{2}$

A) Od všech trojic z 32 bodů odečteme ty, které netvoří trojúhelník (ty co leží na jedné straně):
$\dbinom{32}{3} - 4 \cdot \dbinom{8}{3} \qquad [=4736]$

B) Ze čtyř stran vybere tři a z osmi bodů na každé straně jeden:
$\dbinom{4}{3} \cdot \dbinom{8}{1} \cdot \dbinom{8}{1} \cdot \dbinom{8}{1} = 4 \cdot 8^3 = 2048$

$\dbinom{8}{3} \qquad [=56]$

$\dbinom{12}{6} : 2 \qquad [= 462]$

$\dbinom{4}{2} \cdot \dbinom{8}{4} : 2 \qquad [= 210]$

a) $\dbinom{19}{7} \qquad [= 50388]$

b) $\dbinom{19}{8} \qquad [= 75582]$

c) $\dbinom{18}{6} \qquad [= 18564]$

d) $\dbinom{18}{7} + \dbinom{18}{7} + \dbinom{18}{6} \qquad [= 82212]$

e) $\dbinom{18}{7} + \dbinom{18}{7} + \dbinom{18}{8} \qquad [= 107406]$

f) $\dbinom{18}{8} \qquad [= 43758]$

$\dbinom{20}{10} \cdot \dbinom{10}{6} \cdot \dbinom{4}{4} \qquad [= 38798760] $

a) $\dbinom{12}{6} \qquad [= 924]$

b) $\dbinom{9}{6} \qquad [= 84]$

c) $\dbinom{3}{1} \cdot \dbinom{9}{5} \qquad [= 378] $

d) $\dbinom{3}{2} \cdot \dbinom{9}{4} \qquad [= 378] $

e) $\dbinom{3}{3} \cdot \dbinom{9}{3} \qquad [= 84] $

$\dbinom{15}{3} + \dbinom{15}{2} \cdot \dbinom{15}{1} \qquad [= 2030]$