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.
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 formula_1 alkiota, ne voidaan luetella formula_2 eri järjestyksessä eli permutaatioita on formula_2
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 formula_1 alkioita, variaation ensimmäinen alkio voidaan valita formula_1 eri tavalla, mutta toisen alkion osalta vaihtoehtoja on enää vain formula_6, kolmannen osalta formula_7 ja niin edelleen. Sellaisia variaatioita, joissa on formula_8 alkiota, eli "k-variaatioita", on näin ollen
formula_9 eli formula_10 erilaista.
Kombinaatiot ovat annetun joukon osajoukkoja, joissa on tietty määrä alkioita. Toisin kuin variaatioissa, kombinaatioissa alkioiden järjestyksellä ei ole merkitystä. Näin ollen formula_1 alkiota sisältävän joukon sellaisten kombinaatioiden lukumäärä, joissa on formula_8 alkiota, saadaan jakamalla vastaavien variaatioiden lukumäärä formula_8-alkioisen joukon permutaatioiden lukumäärällä. Toisin sanoen kombinaatioiden lukumäärä on
jolle käytetään myös merkintää
Koska samat luvut ovat samoja, jotka esiintyvät myös kertoimina, kun binomin formula_1:s potenssi kehitetään polynomiksi, sanotaan näitä lukuja myös binomikertoimiksi. Ne voidaan laskea myös Pascalin kolmion avulla.
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.