Kombinacja bez powtórzeń

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja bez powtórzeń
permutacja z powtórzeniami


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ń – dowolny podzbiór zbioru skończonego. Jeśli zbiór jest n-elementowy, 0 ≤ kn, 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:

.

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,...k}→{1,...,n}.

Przykłady[edytuj | edytuj kod]

  • Liczba kombinacji 2-elementowych zbioru 4-elementowego jest równa
    Kombinacjami są podzbiory:
  • Liczba kombinacji 6-elementowych zbioru 49-elementowego jest równa .
  • Liczba wyników losowań w Lotto, w których dokładnie liczb spośród 6 (na 49) jest trafnych:
.
Jest to bowiem iloczyn liczby kombinacji tj. liczby sposobów, na które można trafić dokładnie k liczb spośród 6, oraz liczby kombinacji 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ą”: ,
  • liczba możliwych wyników z trafioną „piątką”: ,
  • liczba możliwych wyników z trafioną „czwórką”: ,
  • liczba możliwych wyników z trafioną „trójką”: .

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

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

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

  oraz  

Zobacz też[edytuj | edytuj kod]