Kombinacja bez powtórzeń

Kombinacja bez powtórzeń – dowolny podzbiór zbioru skończonego. Jeśli zbiór jest $n$-elementowy, $0\leqslant k\leqslant n,$ to $k$-elementowy podzbiór jest określany jako $k$-elementowa kombinacja zbioru $n$-elementowego. Używa się też terminu „kombinacja z $n$ elementów po $k$ elementów” lub po prostu „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 (patrz symbol Newtona):

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

Każda kombinacja $n$ po $k$ jest klasą abstrakcji wszystkich $k$-wyrazowych wariacji bez powtórzeń zbioru $n$-elementowego różniących się między sobą jedynie kolejnością elementów.

Kombinację $n$ po $k$ można interpretować jako ściśle rosnącą funkcję $\{1,\dots k\}\to \{1,\dots ,n\}.$

Przykłady

• Liczba kombinacji 2-elementowych zbioru 4-elementowego $A=\{a,b,c,d\}$ jest równa ${\begin{matrix}{\frac {4!}{2!\cdot 2!}}={\frac {1\cdot 2\cdot 3\cdot 4}{2\cdot 2}}=6\end{matrix}}.$
  Kombinacjami są podzbiory: $\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}.$
• Liczba kombinacji 6-elementowych zbioru 49-elementowego jest równa ${49 \choose 6}={\frac {49!}{6!\times (49-6)!}}=13\ 983\ 816.$
• Liczba wyników losowań w Lotto, w których dokładnie $k$ liczb spośród 6 (na 49) jest trafnych:

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

Jest to bowiem iloczyn liczby kombinacji ${6 \choose k},$ tj. liczby sposobów, na które można trafić dokładnie $k$ liczb spośród 6, oraz liczby kombinacji ${49-6 \choose 6-k},$ tj. liczby sposobów, na które można chybić pozostałe $6-k$ liczb. W szczególności:

• liczba możliwych wyników z trafioną „szóstką”: ${6 \choose 6}\times {49-6 \choose 6-6}=1,$
• liczba możliwych wyników z trafioną „piątką”: ${6 \choose 5}\times {49-6 \choose 6-5}=258,$
• liczba możliwych wyników z trafioną „czwórką”: ${6 \choose 4}\times {49-6 \choose 6-4}=15\times 903=13\ 545,$
• liczba możliwych wyników z trafioną „trójką”: ${6 \choose 3}\times {49-6 \choose 6-3}=20\times 12\ 341=246\ 820.$

Z dwóch ostatnich przykładów łatwo ustalić prawdopodobieństwo trafienia „szóstki” Lotto:

${\frac {1}{49 \choose 6}}={\frac {1}{13\ 983\ 816}},$

prawdopodobieństwo trafienia co najmniej „trójki”:

${\frac {1}{49 \choose 6}}+{\frac {258}{49 \choose 6}}+{\frac {13\ 545}{49 \choose 6}}+{\frac {246\ 820}{49 \choose 6}}={\frac {260\ 624}{13\ 983\ 816}}\approx {\frac {1}{54}}$

lub prawdopodobieństwo trafienia dokładnie „czwórki” i odpowiednio „trójki”:

${\frac {13\ 545}{49 \choose 6}}={\frac {13\ 545}{13\ 983\ 816}}\approx {\frac {1}{1\ 032}}\quad {}$ oraz ${}\quad {\frac {246\ 820}{49 \choose 6}}={\frac {246\ 820}{13\ 983\ 816}}\approx {\frac {1}{57}}.$

Zobacz też

• kombinacja z powtórzeniami
• symbol Newtona
• teoria zbiorów
• rozkład hipergeometryczny