Yhdistelmät ja permutaatiot

Permutaatio ja kombinaatio – mitä eroa niillä on?

Koko kombinatoriikka rakentuu yhdelle kysymykselle: merkitseekö järjestys vai ei. Kun lasket, monessako järjestyksessä viisi kirjaa mahtuu hyllyyn, kyseessä on permutaatio – ABC ja CBA ovat eri tuloksia. Kun valitset kolme ystävää viidestä juhliin, kyseessä on kombinaatio, koska sama kolmikko on sama joukko valintajärjestyksestä riippumatta.

Käytännön laskennan selkäranka on tuloperiaate: jos yksi vaihe voidaan tehdä a tavalla ja seuraava niistä riippumatta b tavalla, yhdistelmiä on a·b. Kahden nopan heitossa tämä tuottaa 6·6=36 tulosta, ja samaa periaatetta sovelletaan nopan todennäköisyyksien laskennassa läpi koko aihealueen.

Kertoma (faktoriaali) ja sen laskeminen

Faktoriaali on permutaation ja kombinaation rakennuspalikka. Merkintä n! tarkoittaa laskutoimitusta n·(n−1)·(n−2)·…·2·1. Viiden alkion tapauksessa 5·4·3·2·1=120 – juuri niin monessa eri järjestyksessä viisi henkilöä voi seisoa jonossa.

Kasvu on jyrkkää. Jo kymmenen esineen järjestysten määrä, 10!=3 628 800, ylittää reilusti kolme miljoonaa, ja luvut karkaavat nopeasti astronomisiin lukemiin. Tästä syystä loton kaltaisten arvontojen vaihtoehtomäärät nousevat miljooniin, vaikka numeroita on vain neljäkymmentä.

Syötä nämä luvut laskuriin yllä ja totea kertomien arvot suoraan. Faktoriaalia tarvitaan kaikissa seuraavissa kaavoissa, joten sen idea – peräkkäisten kokonaislukujen tulo – kannattaa pitää mielessä.

Permutaatio nPr: kaava P(n,r)=n!/(n−r)!

Permutaation ydin on, että jokainen eri järjestys lasketaan omaksi tuloksekseen. Kun valitset r kappaletta n:stä ilman toistoa, ensimmäiselle paikalle on n vaihtoehtoa, toiselle n−1, kolmannelle n−2 ja niin edelleen. Tämä peräkkäisten tekijöiden tulo on täsmälleen n!/(n−r)!.

Konkreettinen esimerkki: juoksukilpailun kolme parasta sijaa kymmenestä osallistujasta saadaan laskettua P(10,3)=10·9·8=720. Voittaja, hopea ja pronssi ovat eri rooleja, joten sama kolmikko eri sijoituksilla on eri permutaatio. Tämä erottaa nPr-laskennan kombinaatiosta, jossa pelkkä joukko riittäisi.

1. Tunnista n (vaihtoehtojen kokonaismäärä) ja r (valittavien määrä).
2. Laske n! ja (n−r)!.
3. Jaa: P(n,r)=n!/(n−r)!.
4. Tarkista tulos syöttämällä luvut laskuriin yllä.

Kun haluat siirtyä järjestetyistä jonoista järjestyksestä riippumattomiin valintoihin, jaat permutaation luvun r!:llä – juuri tämä askel johtaa seuraavaan kaavaan.

Kombinaatio nCr: kaava C(n,r)=n!/(r!(n−r)!)

Kombinaatio saadaan permutaatiosta poistamalla järjestyksen vaikutus. Koska r alkiota voidaan järjestää r!:llä eri tavalla, jokainen kombinaatio on laskettu permutaatioissa täsmälleen r! kertaa. Siksi C(n,r)=P(n,r)/r! eli n!/(r!(n−r)!).

Lukua C(n,r) kutsutaan myös nimellä binomikerroin, ja se esiintyy binomilauseessa ja Pascalin kolmiossa. Käytännön todennäköisyyslaskennassa nCr on yleisin työkalu: aina kun lasket suotuisien valintojen suhdetta kaikkiin valintoihin, lukumäärät tulevat kombinaatioista. Samaa logiikkaa hyödynnetään korttipelien todennäköisyyksissä, joissa kättä ei järjestetä.

Huomaa symmetria: C(n,r)=C(n,n−r). Seitsemän valitseminen 40:stä tuottaa saman luvun kuin 33:n jättäminen pois, mikä usein nopeuttaa käsinlaskua.

Toistolla vai ilman toistoa

Toiston läsnäolo muuttaa kaavan kokonaan, joten se on ratkaistava ennen laskua. Kun järjestys merkitsee ja toisto on sallittu, jokaiselle r paikalle on aina n vaihtoehtoa, joten tuloksia on nʳ. Kun toistoa ei sallita, vaihtoehtojen määrä pienenee joka askeleella ja päädytään permutaatioon n!/(n−r)!. Ero on suuri: nelinumeroinen PIN antaa 10⁴=10 000 koodia, mutta ilman toistoa vain P(10,4)=10·9·8·7=5 040.

Järjestyksettömässä laskennassa ero näkyy yhtä selvästi. Ilman toistoa seitsemän numeron lottorivejä on C(40,7)=18 643 560, kun taas toiston salliva nʳ-tyyppinen valinta tuottaisi aivan eri lukeman. Korttikädet ovat aina ilman toistoa: kun kortti on jaettu, se ei palaa pakkaan, joten C(52,5)=2 598 960 on oikea nimittäjä.

• Kysy ensin: voiko sama alkio tulla valituksi kahdesti?
• Kysy sitten: erottaako järjestys kaksi muuten samaa valintaa?
• Vasta näiden vastausten jälkeen valitse oikea kaava neljästä.

Variaatio ja arkiesimerkit: PIN, salasanat, rekisterikilvet

Variaatio toistolla on kombinatoriikan arkisin muoto. Kun jokaiseen kohtaan kelpaa mikä tahansa n alkiosta ja sama alkio saa esiintyä uudelleen, vaihtoehtoja on n^r. Pankkikortin neljän numeron PIN-koodissa kuhunkin paikkaan käy 0–9, joten ruutuja kertyy 10^4 = 10 000. Kirjautumisessa kuusimerkkinen pelkistä pienistä kirjaimista koottu salasana venyttää saman ajatuksen lukuun 26^6 = 308 915 776 – yli 300 miljoonaa yhdistelmää.

Erotus muihin tapoihin on selvä: permutaatiossa sama alkio ei toistu (esimerkiksi 5! = 120 tapaa järjestää viisi eri korttia), ja kombinaatiossa järjestyksellä ei ole väliä lainkaan – viiden kortin käsiä 52:sta on C(52,5) = 2 598 960 ja loton kaltaisia seitsemän numeron rivejä 40:stä C(40,7) = 18 643 560. Toistollisen variaation valtava luku syntyy juuri siitä, että jokainen merkki valitaan itsenäisesti uudelleen. Sama matematiikka pyörittää korttipelien todennäköisyyksiä; lisää laskuesimerkkejä löydät etusivun laskureista. Rahapeleissä luvut ovat suuntaa-antavia ja peli-ikäraja on 18 vuotta.

Loton todennäköisyys kombinaatioilla: 7/40 vaihe vaiheelta

Loton voittotodennäköisyys johdetaan suoraan kombinaatiosta. Koska arvonnassa numeroiden tulojärjestyksellä ei ole väliä, kyse on kombinaatiosta ilman toistoa.

1. Laske kaikkien rivien määrä: C(40,7)=40!/(7!·33!)=18 643 560.
2. Täysosuman todennäköisyys on yksi suotuisa rivi jaettuna kaikilla: 1/18 643 560.
3. Pienempien luokkien todennäköisyydet saadaan laskemalla, monellako tavalla osa numeroista osuu oikein ja loput väärin.

Vertailun vuoksi Eurojackpotissa valitaan 5 päänumeroa 50:stä ja 2 tähteä 12:sta, jolloin yhdistelmiä on C(50,5)·C(12,2)=2 118 760·66=139 838 160 ja päävoiton todennäköisyys 1:139 838 160. Lotossa päävoitto on siis noin 7,5-kertaa todennäköisempi kuin Eurojackpotissa. Saman todennäköisyyden ja kertoimien muunnoksen avulla mikä tahansa näistä luvuista voidaan ilmaista myös desimaalikertoimena.

Voittoluokkien todennäköisyydet: 5, 6, 6+1 oikein

Jokainen voittoluokka lasketaan samalla kombinatorisella logiikalla: monellako tavalla osa pelaajan numeroista voi osua oikeisiin numeroihin ja loput jäädä ulkopuolelle. Mitä löyhempi ehto, sitä useampi kombinaatio C(40,7):n 18 643 560 rivistä kelpaa, joten todennäköisyys kasvaa.

Käytännössä ero on valtava: neljän oikein todennäköisyys 1:98 on noin 190 000 kertaa suurempi kuin päävoiton 1:18 643 560. Siksi pienet voitot toistuvat säännöllisesti, vaikka täysosuma jää useimmilla pelaajilla kokematta. Sama porrastus selittää, miksi arvontapelin tuotto-odotus rakentuu enimmäkseen alaluokista.

Korttikädet ja kombinatoriikka: C(52,5)

Korttikädet ovat kombinaatioiden oppikirjaesimerkki, koska kädessä järjestyksellä ei ole väliä – samat viisi korttia muodostavat saman käden riippumatta siitä, missä järjestyksessä ne jaetaan. Kaikkien käsien määrä C(52,5)=2 598 960 toimii nimittäjänä jokaisessa pokeritodennäköisyydessä.

Yksittäisen käsityypin todennäköisyys lasketaan jakamalla kyseisen käden muodostavien yhdistelmien määrä luvulla 2 598 960. Parin osuus on 42,26 % kaikista käsistä, kun taas neloset (0,024 %) ja värisuora (0,0015 %) ovat äärimmäisen harvinaisia.

Sama kombinaatiopohja tuottaa myös yksittäisten nostojen todennäköisyydet: vähintään yhden ässän saaminen viidellä nostolla ilman takaisinpanoa on 1−C(48,5)/C(52,5)≈34,12 %. Lisää tämänkaltaisia laskelmia löytyy sivulta korttien todennäköisyys, ja todennäköisyyslaskennan perusteet kootaan etusivulle.