Kombinacja bez powtórzeń

Wygląd przypnij ukryj

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

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

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

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

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

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

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

Przykłady

Liczba kombinacji 2-elementowych zbioru 4-elementowego A = { a , b , c , d } {\displaystyle A=\{a,b,c,d\}} $A=\{a,b,c,d\}$ jest równa 4 ! 2 ! ⋅ 2 ! = 1 ⋅ 2 ⋅ 3 ⋅ 4 2 ⋅ 2 = 6 . {\displaystyle {\begin{matrix}{\frac {4!}{2!\cdot 2!}}={\frac {1\cdot 2\cdot 3\cdot 4}{2\cdot 2}}=6\end{matrix}}.} ${\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 } . {\displaystyle \{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}.} $\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}.$
Liczba kombinacji 6-elementowych zbioru 49-elementowego jest równa ( 49 6 ) = 49 ! 6 ! × ( 49 − 6 ) ! = 13 983 816. {\displaystyle {49 \choose 6}={\frac {49!}{6!\times (49-6)!}}=13\ 983\ 816.} ${49 \choose 6}={\frac {49!}{6!\times (49-6)!}}=13\ 983\ 816.$
Liczba wyników losowań w Lotto, w których dokładnie k {\displaystyle k} $k$ liczb spośród 6 (na 49) jest trafnych:

( 6 k ) × ( 49 − 6 6 − k ) . {\displaystyle {6 \choose k}\times {49-6 \choose 6-k}.}

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

Jest to bowiem iloczyn liczby kombinacji ( 6 k ) , {\displaystyle {6 \choose k},}

{6 \choose k},

tj. liczby sposobów, na które można trafić dokładnie k {\displaystyle k}

k

liczb spośród 6, oraz liczby kombinacji ( 49 − 6 6 − k ) , {\displaystyle {49-6 \choose 6-k},}

{49-6 \choose 6-k},

tj. liczby sposobów, na które można chybić pozostałe 6 − k {\displaystyle 6-k}

6-k

liczb. W szczególności:

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

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

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

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

1 ( 49 6 ) + 258 ( 49 6 ) + 13 545 ( 49 6 ) + 246 820 ( 49 6 ) = 260 624 13 983 816 ≈ 1 54 {\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}}}

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

13 545 ( 49 6 ) = 13 545 13 983 816 ≈ 1 1 032 {\displaystyle {\frac {13\ 545}{49 \choose 6}}={\frac {13\ 545}{13\ 983\ 816}}\approx {\frac {1}{1\ 032}}\quad {}}

{\frac {13\ 545}{49 \choose 6}}={\frac {13\ 545}{13\ 983\ 816}}\approx {\frac {1}{1\ 032}}\quad {}

oraz 246 820 ( 49 6 ) = 246 820 13 983 816 ≈ 1 57 . {\displaystyle {}\quad {\frac {246\ 820}{49 \choose 6}}={\frac {246\ 820}{13\ 983\ 816}}\approx {\frac {1}{57}}.}

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

Zobacz też

Przypisy

↑ Kombinacja, Encyklopedia PWN .
↑ Kenneth A. Ross, Charles R. B. Wright: Matematyka dyskretna. Wydawnictwo Naukowe PWN, 2001, s. 276. ISBN 83-01-12129-7.

Kombinatoryka

Kontrola autorytatywna (pojęcie matematyczne):

BNCF: 32733

Encyklopedia internetowa: