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ä

(nk)=n!k!(n−k)!,

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. Huomaa, että taulukko vastaa myös Pascalin kolmiona tunnettua järjestelmää.

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=0nC(n,k)=2n
k  luku (kelt.) on kahden muun (sin.) summa
6  1
5  16
4  1515
3  141020
2  1361015
1  123456
  0  1111111
  0  1  2  3  4  5  6n
12481632642n

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

(n1)=∑i=1n1,
(n2)=∑i=1n−1∑j=i+1n1,
(n3)=∑i=1n−2∑j=i+1n−1∑k=j+1n1, jne.

Esimerkkejä

Esimerkki 1.

Luettelo eri tapauksista, kun viidestä ihmisestä (luvusta 1, 2, 3, 4 tai 5) valitaan kolme ihmistä (lukua).

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

(53)=5!3!(5−3)!=5⋅4⋅3⋅2!3!⋅2!=5⋅4⋅33!=5⋅4⋅36=5⋅2=10.

Esimerkki 2.

Lasketaan todennäköisyys sille, että saadaan lotossa tasan k numeroa oikein (0≤k≤7):

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):

(7k)

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:

(7k)(327−k)

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ä (397):

(7k)(327−k):(397)

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

(75)(327−5):(397)=(75)(322):(397)=21⋅496:15380937=10416:15380937≈1:1477≈0,0006772

Katso myös