Permutaatio

Permutaatio on k-permutaation erikoistapaus, jossa meillä on n alkion joukko ja haluamme selvittää kaikkien erilaisten n-monikkojen lukumäärän.

Kaava

Kerrataan itse k-permutaatio. Olkoon meillä numeroiden joukko {1, 2, 3, 4, 5}. Kuinka monta kolminumeroista lukua voimme siitä koota, kun mikään numero ei saa toistua? Tämä on tyypillinen k-permutaatiotehtävä, joka ratkeaa tutulla kaavalla

$$\frac{n!}{(n-k)!}=\frac{5!}{(5-3)!}=60.$$

Kuinka monta viisinumeroista lukua voisimme koota?

$$\frac{n!}{(n-k)!}=\frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120.$$

Huomaamme, että kun joukossa on viisi alkiota ja etsimme kaikkien erilaisten viisikkojen lukumäärää, tulos on 5!. Tämän voi yleistää: jos joukossa on n alkiota, erilaisia n-monikkoja on yhteensä n!. Näin päädymme permutaation käsitteeseen.

Mikä permutaatio on

Jos meillä on joukko M, jossa on n alkiota, permutaatio on mikä tahansa joukon M alkioista koottu n-monikko, jossa mikään alkio ei toistu. Esimerkki: jos meillä on joukko M = {a, b, c, d}, permutaatio on esimerkiksi (a, b, d, c) tai (d, b, a, c). Kaikkien erilaisten permutaatioiden lukumäärä on

$$n!=\frac{n!}{(n-n)!}$$

eli n alkion permutaatioita on n!.

Ratkaistuja esimerkkejä

1. Sinulla on yhteensä kuusi kirjaa, ja haluat asettaa ne hyllylle johonkin järjestykseen. Kuinka monta erilaista järjestystä on olemassa? Meillä on kuusi kirjaa, permutoimme aina kaikki kirjat, joten tulos on 6! = 720.

2. Edellisen esimerkin kuuden suomenkielisen kirjasi lisäksi sinulla on nyt 4 ruotsinkielistä kirjaa. Kuinka monella eri tavalla nämä 10 kirjaa voi asettaa hyllylle, jos haluat kaikki suomenkieliset kirjat vierekkäin ja kaikki ruotsinkieliset kirjat vierekkäin?

   Millaisia mahdollisuuksia kirjojen asettamiseen on? Voimme asettaa ensin kuusi suomenkielistä kirjaa ja sitten neljä ruotsinkielistä tai päinvastoin – ensin neljä ruotsinkielistä ja sitten kuusi suomenkielistä. Suomenkieliset kirjat voi järjestää 6! tavalla ja ruotsinkieliset 4! tavalla. Käytämme kombinatoriikan tuloperiaatetta ja kerromme nämä tulokset: 6! · 4! = 17 280. Koska kirjat voi asettaa kahdella tavalla (suomenkieliset ensin ja sitten ruotsinkieliset tai päinvastoin), kerromme vielä tämän luvun kahdella. Lopputulos on 17 280 · 2 = 34 560.