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. 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 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. thumb|200px|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:
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