Kombinatoriikka

Kombinatoriikka on matematiikan osa-alue, joka tutkii tietyt ominaisuudet toteuttavien joukkojen lukumääriä. Enumeratiivinen kombinatoriikka laskee saadun joukon alkioiden lukumäärän. Matroiditeoria tutkii joukkojen konstruoimista ja analysointia. Ekstremaalinen kombinatoriikka pyrkii löytämään jollakin tapaa optimaalisen kokoelman objekteja. Algebrallinen kombinatoriikka tutkii, mitä algebrallisia rakenteita joukon alkioille voidaan muodostaa.

Kombinatoriikka on yhtä paljon ongelman ratkaisemista kuin teorian rakentamista. Erityisesti 1900-luvulla kombinatoriikkaan on kehitetty paljon teoreettisia tuloksia, jotka helpottavat kombinatoristen ongelmien laskemista huomattavasti.

Peruskäsitteet

Permutaatio

Permutaatio on jokainen jono, joka sisältää annetun joukon alkiot lueteltuna jossakin järjestyksessä. Annetun äärellisen joukon permutaatioiden lukumäärä on sen alkioiden lukumäärän kertoma, eli luku, joka saadaan kertomalla keskenään kaikki kokonaisluvut yhdestä alkioiden lukumäärään saakka. Jos siis joukossa on $n$ alkiota, ne voidaan luetella $n!$ eri järjestyksessä eli permutaatioita on $n!$

Variaatio

Variaatiot ovat jonoja, jotka sisältävät vain tietyn määrän perusjoukon alkioista määrätyssä järjestyksessä ja joissa ei sama alkio esiinny enempää kuin kerran. Jos joukossa on $n$ alkioita, variaation ensimmäinen alkio voidaan valita $n$ eri tavalla, mutta toisen alkion osalta vaihtoehtoja on enää vain $n-1$, kolmannen osalta $n-2$ ja niin edelleen. Sellaisia variaatioita, joissa on $k$ alkiota, eli k-variaatioita, on näin ollen

$n(n-1)(n-2)...(n-k+1)$ eli ${\frac {n!}{(n-k)!}}$ erilaista.

Kombinaatio

Kombinaatiot ovat annetun joukon osajoukkoja, joissa on tietty määrä alkioita. Toisin kuin variaatioissa, kombinaatioissa alkioiden järjestyksellä ei ole merkitystä. Näin ollen $n$ alkiota sisältävän joukon sellaisten kombinaatioiden lukumäärä, joissa on $k$ alkiota, saadaan jakamalla vastaavien variaatioiden lukumäärä $k$-alkioisen joukon permutaatioiden lukumäärällä. Toisin sanoen kombinaatioiden lukumäärä on

${\frac {n!}{k!(n-k)!}}$,

jolle käytetään myös merkintää

${n \choose k}$

Koska samat luvut ovat samoja, jotka esiintyvät myös kertoimina, kun binomin $n$:s potenssi kehitetään polynomiksi, sanotaan näitä lukuja myös binomikertoimiksi. Ne voidaan laskea myös Pascalin kolmion avulla.

Esimerkkejä

Kombinatoriikkaa sovelletaan ennen kaikkea todennäköisyyslaskennassa, erityisesti tilanteissa, joissa jonkin joukon permutaatioita, variaatioita tai kombinaatioita voidaan pitää symmetrisinä alkeistapauksina.

Esimerkkinä kombinatorisesta kysymyksestä on seuraava: Monellako tavalla 52 kortin pakka voidaan järjestää? Osoittautuu, että erilaisia järjestyksiä eli 52 alkion joukon permutaatioita on 52! = 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000 kappaletta.

Toisentyyppinen kombinatoriikan tehtävä on seuraava: Olkoon annettu n henkilöä. Onko mahdollista järjestää henkilöt eri joukkoihin siten, että jokainen henkilö on ainakin yhdessä joukossa, jokainen kahden henkilön pari on täsmälleen yhdessä joukossa, jokaisella kahdella joukolla on täsmälleen yksi yhteinen henkilö ja mikään joukko ei sisällä kaikkia henkilöitä, kaikkia paitsi yhtä henkilöä tai täsmälleen yhtä henkilöä. Vastaus riippuu n:stä.

Lottovoiton todennäköisyys voidaan laskea myös kombinatoriikan avulla. Kuinka monta erilaista lottoriviä voidaan muodostaa, kun arvotaan seitsemän erilaista numeroa 40 numeron joukosta? Ensimmäinen numero voi olla mikä tahansa 40:stä numerosta, seuraava mikä tahansa loppujen 39:n numeron joukosta, sitä seuraava mikä tahansa numero jäljellä olevien 38:n numeron joukosta. Erilaisia vaihtoehtoja on 40*39*38*37*36*35*34=93963542400 kappaletta. Lotossa ei ole merkitystä sillä, missä järjestyksessä rivin numerot arvotaan. Sama lottorivi voidaan arpoa 7*6*5*4*3*2*1=5040 eri järjestyksessä. Yhdistämällä edelliset kaksi tietoa nähdään, että erilaisia lottorivejä on 93963542400/5040=18643560 kappaletta, jolloin päävoiton todennäköisyys yhdellä rivillä pelaamalla on 1/18643560 ( 0,0000053638% ) eli yksi noin yhdeksästätoista miljoonasta. Lottorivit ovat siis 40 alkion joukosta muodostettuja 7 alkion kombinaatioita.

Kirjallisuutta

• Haukkanen, Pentti: Kombinatoriikkaa

Katso myös

• Kombinaatio