Kombinacja bez powtórzeń – dowolny podzbiór zbioru skończonego. Jeśli zbiór jest
-elementowy,
to
-elementowy podzbiór jest określany jako
-elementowa kombinacja zbioru
-elementowego[1]. Używa się też terminu „kombinacja z
elementów po
elementów” lub po prostu „kombinacja z
po
”.
Dopełnieniem kombinacji z
po
jest kombinacja z
po
Liczba kombinacji z
po
wyraża się wzorem[2] (patrz symbol Newtona):
![{\displaystyle C_{n}^{k}={n \choose k}={\frac {n!}{k!(n-k)!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c586efd8f25ab17eab5a0d853b4813a88e2cf3e0)
Każda kombinacja
po
jest klasą abstrakcji wszystkich
-wyrazowych wariacji bez powtórzeń zbioru
-elementowego różniących się między sobą jedynie kolejnością elementów.
Kombinację
po
można interpretować jako ściśle rosnącą funkcję
Przykłady
- Liczba kombinacji 2-elementowych zbioru 4-elementowego
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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14edbe696f6fe4400573248d8e811342dbbc03e7)
Kombinacjami są podzbiory: ![{\displaystyle \{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19b32449f74b594e17386a39eac865bd8ef112f5)
- Liczba kombinacji 6-elementowych zbioru 49-elementowego jest równa
![{\displaystyle {49 \choose 6}={\frac {49!}{6!\times (49-6)!}}=13\ 983\ 816.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff4809ef3caa61b605a986b828485433da6d7be4)
- Liczba wyników losowań w Lotto, w których dokładnie
liczb spośród 6 (na 49) jest trafnych:
![{\displaystyle {6 \choose k}\times {49-6 \choose 6-k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b450321ea348e159fc094cf024bf777e6486f807)
- Jest to bowiem iloczyn liczby kombinacji
tj. liczby sposobów, na które można trafić dokładnie
liczb spośród 6, oraz liczby kombinacji
tj. liczby sposobów, na które można chybić pozostałe
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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f166e1c7731fd133df43ecc3c534dcdf12f26011)
- liczba możliwych wyników z trafioną „piątką”:
![{\displaystyle {6 \choose 5}\times {49-6 \choose 6-5}=258,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/059767ce7124fdbb6ade0a1e85ff645d9f7c66bf)
- liczba możliwych wyników z trafioną „czwórką”:
![{\displaystyle {6 \choose 4}\times {49-6 \choose 6-4}=15\times 903=13\ 545,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a251b0b4d4e72a19bcf3c545047bc40b279aaf34)
- 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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/720d9c20242e2f2e09aeda42c25873660b5e5ec1)
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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50adc8128d039eb7c25042e9648fb8217b2f79a9)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/934f66d0a20364039ff96252a9df5c8e8b0b03d0)
lub prawdopodobieństwo trafienia dokładnie „czwórki” i odpowiednio „trójki”:
oraz ![{\displaystyle {}\quad {\frac {246\ 820}{49 \choose 6}}={\frac {246\ 820}{13\ 983\ 816}}\approx {\frac {1}{57}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd4ce1b7dda96dae6f99d3b275a2ff85354e4eb6)
Zobacz też
Przypisy
- ↑ Kombinacja, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-07-22] .
- ↑ Kenneth A. Ross, Charles R. B. Wright: Matematyka dyskretna. Wydawnictwo Naukowe PWN, 2001, s. 276. ISBN 83-01-12129-7.
Kombinatoryka
zagadnienia – znajdowanie liczby | |
---|
inne | |
---|