Permutaatiot ja kombinaatiot

Tekijä:
Jan Jansson

Permutaatiot

Permutaatiot eli erilaiset alkioiden järjestykset on joskus helpoin selvittää taulukoimalla. Esimerkiksi kolme henkilöä (Arttu, Berit ja Cecil) voivat saapua juhliin seuraavissa järjestyksissä: ABC ACB BAC BCA CAB CBA Järjestyksien määrän laskeminen on mahdollista myös esimerkiksi puukaavion avulla. Puukaaviossa saapumisjärjestys pilkotaan pieniksi tapahtumiksi. Ensimmäisen vieraan saapuminen on arvontatilanne, jossa mahdollisuuksia on kolme. Puukaavio hajaantuu kolmeen osaan. Seuraavan vieraan saapuessa yksi vaihtoehto on jo käytetty. Jos ensimmäinen saapuja oli A, toinen saapuja voi olla B tai C. Jos B saapui ensin, jäljellä olevat kaksi vaihtoehtoa ovat A ja C jne. Kolmannen vieraan saapuessa vaihtoehtoja on enää yksi. Saadaan kuusi erilaista polkua. Toisaalta saman voisi laskea vielä helpommin tuloperiaatteen mukaan. Kerrotaan jokaisessa kohdassa käytössä olevien vaihtoehtojen määrät keskenään. Koska ensin mahdollisuuksia on 3, sitten kaksi ja viimeisessä kohdassa vain yksi, eri vaihtoehtojen määrä on . Tämä lasku voidaan kirjoittaa myös lyhyemmin 3! eli "kolmen kertoma". Kertomassa lasketaan positiivisen kokonaisluvun ja kaikkien sitä pienempien positiivisten kokonaislukujen tulo. Esimerkiksi Geogebran CAS-laskimessa kertoma on helppo kirjoittaa huutomerkin avulla. Kokeile laskea seuraavat: a) Juhliin on saapumassa viisi vierasta. Kuinka monessa eri järjestyksessä he voivat saapua? (120) b) Korttipakassa on 52 korttia. Kuinka moneen eri järjestykseen korttipakan kortit voidaan järjestää? Anna vastaus neljällä merkitsevällä. (8,066∙1067) vinkki: Jälkimmäisessä voi käyttää yläreunasta Likiarvo-painiketta. Lisäksi voit valita oikean yläreunan kolmen viivan alta Asetukset > Pyöristä, jotta saat desimaalien määrää muutettua.
Joskus ei haluta laskea koko joukon kaikkia permutaatioita eli järjestyksiä. Toisinaan halutaan tarkastella esimerkiksi tilannetta, jossa vain osa joukon jäsenistä asettuu jonoon. Ajatellaan esimerkiksi tilannetta, jossa viiden auton rallissa vain kolme pääsee mitaleille. Kuinka monella eri tavalla mitalit voidaan jakaa? Mitalien jakaminen voidaan pilkkoa taas pieniin osiin. Ensimmäisen sijan ja kultamitalin voi saada kuka vain viidestä kilpailijasta. Toisen sijan ja hopeamitalin joku jäljellä olevista neljästä. Pronssimitalin saajaksi on jäljellä enää kolme vaihtoehtoa. Erilaisia mitalien jakamistapoja on siis . Tälle on olemassa oma kaavansa, joka laskimissa ja Geogebrassa merkitään nPr. nPr kaavan avulla lasketaan kuinka monessa eri järjestyksessä k kappaletta alkioita voidaan valita n alkion joukosta. Esimerkiksi 3 mitalien saajaa valitaan 5:n joukosta. Geogebran CAS-ikkunassa lasku suoritetaan komennolla nPr ja sulkeisiin syötetään ensin koko joukon suuruus ja sitten pilkun jälkeen valittavien alkioiden määrä. Esimerkiksi nPr(5,3) Kokeile laskea seuraavat: 16 oppilaan luokasta kolme opiskelijaa pääsee nuorisokunnanvaltuustoon. c) Kuinka monessa eri järjestyksessä kolme oppilasta voidaan arpoa kuudestatoista? (3360) d) Diana, Emil ja Farah ovat hyviä kavereita ja haluaisivat kovasti valtuustoon. Kuinka monessa eri järjestyksessä voitaisiin valita juuri heidät? (6) e) Millä todennäköisyydellä juuri Diana, Emil ja Farah tulevat valituiksi? (0,2% tai )
nPr tarkoittaa kaavaa Esimerkiksi, kun lasketaan eri järjestykset kolmelle mitalien saajalle viidestä kilpailijasta kaava näyttää tältä Jos haluttaisiin laskea kuinka monella tavalla kaikki viisi kilpailijaa voidaan järjestää joudutaan käyttämään 0!, jonka on sovittu olevan 1. Viiden kilpailijan erilaiset permutaatiot saataisiin näin Permutaatiot koko joukolle tai osajoukolle voi tietysti laskea myös ilman kaavaa, koska ne voi päätellä tuloperiaatteella, mutta se voi olla vaikeaa, kun luvut ovat suuria.

Kombinaatiot

Kombinaatiot tarkoittavat erilaisia alkioiden yhdistelmiä. Yhdistelmässä järjestyksellä ei ole väliä toisin kuin permutaatiossa. Joskus kombinaatiotkin on helppo selvittää taulukoimalla. Ajatellaan esimerkiksi tilannetta, jossa Arttu, Berit, Cecil ja Diana ovat menossa kummitusjunaan. Ensimmäiseen vaunuun mahtuu vain kaksi heistä ja se on tietysti jännittävin paikka. Erilaisia mahdollisuuksia valita kaksi heistä ovat AB AC AD BC BD ja CD Koska vaunussa istutaan vierekkäin, järjestyksellä ei ole väliä. AB ja BA ovat sama asia, joten emme listaa molempia permutaatioita (järjestyksiä). Meille riittää tietää tämä kombinaatio eli osajoukko {A, B}, jossa järjestyksellä ei ole väliä. Erilaisten k kappaleen suuruisten kombinaatioiden määrä koko joukosta n voidaan siis laskea permutaatioiden avulla. Permutaatioista pitää vain poistaa kaikki saman joukon erilaiset järjestykset. Tämä tapahtuu jakamalla erilaisten järjestysten määrällä. Kombinaatioiden laskemiseen käytettävä kaava löytyy valmiina laskimesta nimellä nCr ja Geogebrassa käytetään komentoa Binomikerroin. Paperilla käytetään merkintää , joka luetaan "n yli koon". Geogebrassa kirjoitetaan ensin komento Binomikerroin ja sen jälkeen sulkeisiin ensin koko joukon suuruus ja sitten valittavien osajoukkojen koko. Esimerkiksi Binomikerroin(4,2) kertoo, kuinka monta erilaista kahden suuruista osajoukkoa voidaan muodostaa neljän kokoisesta perusjoukosta. Kaava kokonaisuudessaan on , kun määritetään k-kappaleen suuruisten osajoukkojen määrä n-kappaleen suuruisesta kokonaisjoukosta. Kokeile laskea vastaukset seuraaviin: f) Arttu, Berit, Cecil, Diana, Emil ja Farah etsivät istumapaikkaa ruokalassa. Vapaana on vain neljän hengen pöytiä ja he täyttävät ensin yhden pöydän. Kuinka monella eri tavalla pöytään istuvat oppilaat voidaan valita? Entä jos oppilaat ottavat vielä kaksi tuolia naapuripöydästä? (15 & 1) g) Koulutukseen osallistuu 12 henkilöä. Iltapäivällä ryhmä jaetaan sattumanvaraisesti neljän hengen ryhmiin ryhmätöitä varten. Kuinka monta erilaista neljän hengen ryhmää on mahdollista muodostaa? (495) h) Kuinka monta erilaista lottoriviä voidaan muodostaa, kun arvotaan seitsemän numeroa neljästäkymmenestä? (18 643 560)

Laskutoimitusten yhdistäminen

Joskus on tarpeen tutkia myös tilanteita, joissa yhdistetään monia permutaatioita tai kombinaatioita. Ajatellaan esimerkiksi tilannetta, jossa korttipakka sekoitetaan. Millä todennäköisyydellä pakan päällimmäiset 13 korttia ovat kaikki herttoja? Ensin pitää selvittää kuinka monella tavalla kortit voidaan järjestää ja siihen tarvitaan kaikkien 52 kortin permutaatiot eli 52!. Sitten pitäisi selvittää kuinka monella tavalla kortit voidaan järjestää halutulla tavalla. Pilkotaan haluttu järjestys kahteen osaan. Ensin herttojen pitää olla päällimäisenä ja sitten kaikkien muiden korttien alla. Jos tiedetään mahdollisten herttojen järjestysten määrä ja kerrotaan se muiden korttien järjestyksien määrällä, saadaan kaikki suotuisat mahdollisuudet. Hertat voivat olla 13! järjestyksessä ja muut kortit 39! järjestyksessä. Saadaan lasku P(hertat päällä ja muut alla)= Ajatellaan sitten toista arvontatilannetta. Lotossa on mahdollista voittaa jos arvaa oikein neljä numeroa vaikka arvaakin väärin kolme numeroa. Kaikkiaan arvotaan siis seitsemän numeroa neljästäkymmenestä. Arvontajärjestyksellä ei kuitenkaan ole väliä. Olemme siis kiinnostuneet kombinaatioista permutaatioiden sijaan. Mikä on neljä oikein tuloksen todennäköisyys? Selvitetään ensin kaikkien erilaisten rivien määrä eli kuinka monella tavalla seitsemän numeroa voidaan valita neljästäkymmenestä. Se on . Pilkotaan sitten neljä oikein ja kolme väärin rivi kahteen osaan. Neljä oikein pitää valita seitsemän oikean numeron joukosta. Erilaisia tapoja valita neljä oikein on siis . Lisäksi pitää valita väärät numerot. Niitä valitaan 3 ja ne valitaan 33 numeron joukosta eli erilaisia kombinaatioita on siis . Jos kerrotaan keskenään oikein neljän kombinaation määrtä ja väärien kolmen kombinaation määrät saadaan kaikkien erilaisten "neljä oikein ja kolme väärin" rivien määrä. P(neljä oikein ja kolme väärin)= eli noin yksi prosentti. Harjoittele yllä olevien laskutoimitusten syöttämistä Geogebraan. Voit käyttää alla olevaa appletti-ikkunaa tai tehdä työn työpöytäversiossa, jota käytetään myös sähköisissä kokeissa. Ratkaise myös seuraavat tilanteet. i) Viiden oppilaan joukossa on kolme tummahiuksista ja kaksi vaaleahiuksista. Oppilaat järjestyvät jonoon ruokailua varten sattumanvaraisessa järjestyksessä. Kuinka monta sellaista jonoa on, jossa tummahiuksiset ovat ennen vaaleahiuksisia? Mikä on tällaisen jonon syntymisen todennäköisyys? (12, 10%) j) Varastossa on kuusi virtalähdettä, joista kaksi on rikki ja odottaa korjausta, mutta laput ovat tippuneet irti rikkinäisistä laitteista. Tiina tarvitsee kaksi toimivaa virtalähdettä. Tiina järkeilee, että ottamalla mukaan neljä virtalähdettä, ainakin kaksi toimii. Kuinka monta erilaista sellaista yhdistelmää on, jossa Tiinalla on mukanaan tasan kaksi toimivaa ja kaksi rikkinäistä virtalähdettä? Millä todennäköisyydellä hän valitsee juuri näin? (6, 40%)