Kombinatoriikka

Haluatko tietää, kuinka monta erilaista viiden kortin kättä voit valita 52 kortin pakasta? Juuri tällaisia tehtäviä kombinatoriikka ratkaisee. Kombinatoriikassa on kaksi perusperiaatetta – summaperiaate ja tuloperiaate. Kaikki muut menetelmät ovat vain näiden perusajatusten laajennuksia.

Kombinatoriikan summaperiaate

Summaperiaate on hyvin yksinkertainen. Sen mukaan, jos meillä on joukot A, B, joilla ei ole yhtään yhteistä alkiota, yhden alkion valintatapojen lukumäärä yhdisteestä A ∪ B on |A| + |B| eli joukkojen alkioiden lukumäärien summa.

Aloitetaan helpolla esimerkillä. Meillä on 6 punaista ja 8 sinistä palloa. Kaadamme pallot samaan uurnaan. Kuinka monta vaihtoehtoa meillä on yhteensä, kun arvomme yhden pallon? Alussa meillä oli punaisten pallojen joukko, jota merkitsemme A:lla, ja sinisten pallojen joukko, jota merkitsemme B:llä. Nämä joukot ovat pistevieraat eli niillä ei ole yhtään samaa palloa. Haluamme arpoa yhden pallon, joten vaihtoehtoja on yhteensä |A| + |B| = 6 + 8 = 14. Siinä kaikki.

Kombinatoriikan tuloperiaate

Meillä on taas kaksi joukkoa, N ja M. Joukossa N on kolme naista ja joukossa M neljä miestä. Nyt kysymme, kuinka monta erilaista paria ”mies–nainen” näistä joukoista voidaan muodostaa. Otamme aina yhden naisen ja annamme hänelle pariksi jonkin miehen. Parien kokonaismäärän saamme näin: otamme yhden naisen, Ainon, ja annamme hänelle pariksi yksi kerrallaan kaikki miehet. Saamme 4 eri paria, koska hänen parikseen sopii yhteensä 4 eri miestä. Samoin teemme kahdelle muulle naiselle, ja heistäkin muodostuu aina 4 paria. Siinä kaikki, pareja on yhteensä 4 + 4 + 4 = 12.

Mitä oikeastaan teimme? Kerroimme molempien joukkojen koot keskenään. Naisia oli 3 ja miehiä 4, joten parien kokonaismäärä on 3 · 4 = 12. Siksi tätä kutsutaan tuloperiaatteeksi. Jos siis muodostamme pareja kahdesta joukosta, kerromme yhden joukon alkioiden lukumäärän toisen joukon alkioiden lukumäärällä.

Voit myös tarkistaa, että tämä todella pitää paikkansa. Alla ovat kaikki parit, jotka voidaan muodostaa 3 naisesta ja 4 miehestä. Jokainen rivi vastaa yhden naisen vaihtoehtoja ja jokainen sarake yhden miehen vaihtoehtoja. Rivejä on siis kolme ja sarakkeita neljä, yhteensä rivit · sarakkeet vaihtoehtoa.

$$\begin{array}{rcl}& & (N_1,M_1),(N_1,M_2),(N_1,M_3),(N_1,M_4),\\ & & (N_2,M_1),(N_2,M_2),(N_2,M_3),(N_2,M_4),\\ & & (N_3,M_1),(N_3,M_2),(N_3,M_3),(N_3,M_4)\end{array}$$

Ratkaistuja esimerkkejä

1. Kuinka monta erilaista kaksinumeroista lukua on olemassa? Miltä tällainen kaksinumeroinen luku näyttää? Ensimmäisellä paikalla on yksi numeroista 1, …, 9, kun taas toisella paikalla voi lisäksi olla nolla: 0, …, 9. Ensimmäisessä joukossa on siis 9 numeroa ja toisessa 10. Käytämme tuloperiaatetta ja saamme lopputuloksen: 9 · 10 = 90.

• Kuinka monta erilaista kolminumeroista lukua on olemassa, kun mikään numero ei saa esiintyä kahdesti? Ensimmäisellä paikalla voi taas olla yhdeksän numeroa, sillä luku ei voi alkaa nollalla. Toisella paikalla voivat olla kaikki numerot nolla mukaan lukien, mutta siellä ei saa olla ensimmäisellä paikalla olevaa numeroa, joten kymmenestä mahdollisesta numerosta vähennämme yhden (jos kolminumeroinen lukumme alkaa esimerkiksi neloselta, on selvää, ettei toisella paikalla voi enää olla nelosta, koska se esiintyisi luvussa kahdesti). Kolmannella paikalla voivat taas olla kaikki numerot, mutta siellä ei saa olla ensimmäisellä eikä toisella paikalla olevaa numeroa. Syy on jälleen sama. Jos ensimmäisellä paikalla on numero 4 ja toisella numero 7, voimme kolmannelle paikalle lisätä yhden numeron joukosta {0, …, 9} ∖ {4, 7}. Kymmenestä numerosta on siis vähennettävä kaksi. Nyt tarvitsee enää kertoa: 9 · 9 · 8 = 648. Tällaisia lukuja on siis yhteensä 648.
• Heitämme tavallista noppaa kahdesti peräkkäin. Kuinka monta erilaista tulosta voimme saada? Ensimmäisessä heitossa nopalla voi tulla 6 eri tulosta. Toisessa heitossa myös, joten vaihtoehtojen kokonaismäärä on 6 · 6 = 36.
• Heitämme noppaa kahdesti peräkkäin. Kuinka monta erilaista tulosta voimme saada, jos ensimmäisessä heitossa tuli parillinen luku? Ensimmäisessä heitossa tuli parillinen luku eli jokin luvuista 2, 4, 6, joten vaihtoehtoja on 3. Toisessa heitossa voi jo tulla mikä tahansa luku, joten vaihtoehtoja on yhteensä 3 · 6 = 18.