Kombinacja bez powtórzeń

Z Wikipedii

Niniejszy artykuł jest częścią cyklu kombinatoryka.

permutacja

kombinacja bez powtórzeń
kombinacja z powtórzeniami

wariacja bez powtórzeń
wariacja z powtórzeniami

liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera

zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń

Ten szablon: pokaż • dyskusja • edytuj

Kombinacja bez powtórzeń to każdy podzbiór zbioru skończonego. Kombinacją k-elementową zbioru n-elementowego A nazywa się każdy k-elementowy podzbiór zbioru A (0≤k≤n). Używa się też terminu "kombinacja z n elementów po k elementów" lub wręcz "kombinacja z n po k".

Dopełnieniem kombinacji z n po k jest kombinacja z n po n-k. Liczba kombinacji z n po k wyraża się wzorem:

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

[edytuj] Przykłady

Liczba kombinacji 2-elementowych zbioru 4-elementowego A={a, b, c, d} jest równa $\begin{matrix} {4! \over 2! \cdot 2!} = {1 \cdot 2 \cdot 3 \cdot 4 \over 2 \cdot 2}=6 \end{matrix}$ . Kombinacjami są podzbiory: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.
Prawdopodobieństwo trafienia "szóstki", tj. wszystkich liczb podczas losowania Dużego Lotka (wszystkich 6 z 49) wynosi $1 : {49 \choose 6}=1 : \frac{49!}{6! \times (49 - 6)!} = \frac{1}{13~983~816}$
Prawdopodobieństwo, że podczas losowania Dużego Lotka trafimy dokładnie $k$ liczb spośród 6 (na 49) wynosi

$\frac{ {6 \choose k}\times {49 - 6 \choose 6 - k} }{ {49 \choose 6} }$

Bierze się to stąd, że wszystkich możliwych wyników losowań jest ${49 \choose 6}$ ; na ${6 \choose k}$ sposobów można trafić dokładnie k liczb spośród 6; na ${49 - 6 \choose 6 - k}$ sposobów można chybić pozostałe 6-k liczb.

Zatem prawdopodobieństwo trafienia "piątki" wynosi

$\frac{ {6 \choose 5}\times {49-6 \choose 1} }{ {49 \choose 6} } = \frac{258}{13~983~816} \approx \frac{1}{54~201}$

"czwórki":

$\frac{ {6 \choose 4}\times {49-6 \choose 2} }{ {49 \choose 6} } = \frac {15 \times 903} { {49 \choose 6}} = \frac{13~545}{13~983~816} \approx \frac{1}{1~032}$

"trójki":

$\frac{ {6 \choose 3}\times {49-6 \choose 3} }{ {49 \choose 6} } = \frac {20 \times 12341} {{49 \choose 6} } = \frac{246~820}{13~983~816} \approx \frac{1}{57}$