Kombinacja bez powtórzeń

Kombinacja bez powtórzeń – dowolny podzbiór zbioru skończonego. Jeśli zbiór jest ${\displaystyle n}$-elementowy, ${\displaystyle 0\leqslant k\leqslant n,}$ to ${\displaystyle k}$-elementowy podzbiór jest określany jako ${\displaystyle k}$-elementowa kombinacja zbioru ${\displaystyle n}$-elementowego^[1]. Używa się też terminu „kombinacja z ${\displaystyle n}$ elementów po ${\displaystyle k}$ elementów” lub po prostu „kombinacja z ${\displaystyle n}$ po ${\displaystyle k}$”.

Dopełnieniem kombinacji z ${\displaystyle n}$ po ${\displaystyle k}$ jest kombinacja z ${\displaystyle n}$ po ${\displaystyle n-k.}$

Liczba kombinacji z ${\displaystyle n}$ po ${\displaystyle k}$ wyraża się wzorem^[2] (patrz symbol Newtona):

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

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

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

Przykłady

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

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

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

• liczba możliwych wyników z trafioną „szóstką”: ${\displaystyle {6 \choose 6}\times {49-6 \choose 6-6}=1,}$
• liczba możliwych wyników z trafioną „piątką”: ${\displaystyle {6 \choose 5}\times {49-6 \choose 6-5}=258,}$
• liczba możliwych wyników z trafioną „czwórką”: ${\displaystyle {6 \choose 4}\times {49-6 \choose 6-4}=15\times 903=13\ 545,}$
• liczba możliwych wyników z trafioną „trójką”: ${\displaystyle {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:

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

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

${\displaystyle {\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”:

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

Zobacz też

• teoria zbiorów
• rozkład hipergeometryczny

Przypisy