Kombinaatio

Kombinatorisessa matematiikassa joukon alkioiden kombinaatio on joukon osajoukko. k-kombinaatio on joukon S osajoukko, jossa on k kappaletta jäseniä. Jäsenten listausjärjestyksellä ei ole merkitystä kombinaatioissa:  kaikki joukot, jotka voidaan muodostaa vaihtamalla jäsenten järjestystä, esittävät samaa kombinaatiota. Sen sijaan variaatiossa jäsenten järjestyksellä on merkitystä eli eri järjestys on eri variaatio.

k-kombinaatioiden määrä on sama kuin binomikerroin "n yli
k:n", joka kirjoitetaan yleensä

,

missä 
k = kombinaation jäsenten lukumäärä,
n = pääjoukon S jäsenten lukumäärä.

Myös kirjoitusasu C(n, k) on tavallinen sen käyttökelpoisuuden vuoksi tekstirivillä.

Oheisessa taulukossa on eräitä kombinaation C(n, k) arvoja.  Erityisesti C(n, 0) = 1, C(n, 1) = n ja C(n, n) = 1.

Voidaan myös kirjoittaa differenssiyhtälö

 C(n, k) = C(n – 1, k) + C(n – 1, k – 1)

eli taulukkoarvo saadaan kahden aikaisemmin lasketun  summana.

Edelleen havaitaan, että sarakkeella n olevien lukujen  summa on



 k    luku (kelt.) on kahden muun (sin.) summa 6                        1  5                    1   6 4                1  5  15 3             1  4  10  20 2          1  3  6  10  15 1       1  2  3  4   5   6   0    1  1  1  1  1   1   1      0    1    2    3    4    5    6  n     1  2  4  8  16  32  64  

Kombinaatio voidaan esittää myös lukumäärän laskemista kuvaavilla summalausekkeilla:

 ,

 ,

 , jne.

 Esimerkkejä 
 Esimerkki 1. 
C(5, 3) kertoo, kuinka monta erilaista kolmen hengen ryhmää voidaan muodostaa viiden henkilön joukosta. Lasketaan se:

 Esimerkki 2. 

Lasketaan todennäköisyys sille, että saadaan lotossa tasan k numeroa oikein :

Lasketaan ensiksi kaikkien niiden lottorivien määrä, joissa on tasan k numeroa oikein. Tämä saadaan laskemalla kaikki 7:n oikean numeron k-kombinaatiot, joka siis kertoo, kuinka monella tavalla 7:stä numerosta voidaan valita k numeroa (muista, että k on korkeintaan 7):

Nyt väärät numerot voivat olla mitä vain, vaikka selvästikin niiden muodostamat osajoukot vaikuttavat lopullisten rivien määrään. Ongelma ratkaistaankin kertomalla yllä oleva luku kaikkien 32 arpomatta jääneiden numeroiden (7-k) kombinaatiolla, eli kaikilla mahdollisilla väärin menneiden numeroiden kombinaatioilla:

siis kertoo, kuinka monta erilaista lottoriviä voidaan muodostaa, joissa on täsmälleen k numeroa oikein ja 7-k väärin.

Kysytty todennäköisyys tapahtumalle saadaan, kun saatu luku jaetaan kaikkien mahdollisten lottorivien lukumäärällä 
:

Siten esimerkiksi todennäköisyys saada lotossa viisi oikein on 

 Katso myös 
 Permutaatio

 Lähteet 

 Aiheesta muualla 

Luokka:Joukko-oppi
Luokka:Kombinatoriikka
Luokka:Seulonnan keskeiset artikkelit