Kombinatoriikka

Wikipedia
Loikkaa: valikkoon, hakuun

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[muokkaa | muokkaa wikitekstiä]

Permutaatio[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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-alkoisen 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ä[muokkaa | muokkaa wikitekstiä]

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 39 numeron joukosta? Ensimmäinen numero voi olla mikä tahansa 39:stä numerosta, seuraava mikä tahansa loppujen 38:n numeron joukosta, sitä seuraava mikä tahansa numero jäljellä olevien 37:n numeron joukosta. Erilaisia vaihtoehtoja on 39*38*37*36*35*34*33=77519922480 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 77519922480/5040=15380937 kappaletta, jolloin päävoiton todennäköisyys yhdellä rivillä pelaamalla on 1/15380937 eli yksi noin viidestätoista miljoonasta. Lottorivit ovat siis 39 alkion joukosta muodostettuja 7 alkion kombinaatioita.

Katso myös[muokkaa | muokkaa wikitekstiä]