Kombinacja bez powtórzeń

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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ń


Kombinacja bez powtórzeń to każdy podzbiór zbioru skończonego, poza zbiorem pustym. Kombinacją k-elementową zbioru n-elementowego A nazywa się każdy k-elementowy podzbiór zbioru A (0 ≤ kn). 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 nk.

Liczba kombinacji z n po k wyraża się wzorem:

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

Przykłady[edytuj | edytuj kod]

  • 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 Lotto (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 Lotto 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}

Prawdopodobieństwo trafienia co najmniej trzech liczb można obliczyć jako

P(3)+P(4)+P(5)+P(6)=\frac {260~624} {13~983~816} \approx \frac{1}{53{,}66}

gdzie P(x) to prawdopodobieństwo trafienia dokładnie x liczb.

Zobacz też[edytuj | edytuj kod]