Permutaatio
Wikipedia
Matematiikassa permutaatioilla tarkoitetaan alkioiden järjestystä. Esimerkiksi järjestetyn joukon (1,2,3,4) yksi permutaatio on (1,3,2,4). Permutaatioiden lukumäärä k-alkioisessa järjestetyssä joukossa on k:n kertoma k!. Tämä nähdään seuraavasti:
Oletetaan että joukossa on k kappaletta alkioita. Otetaan ensimmäinen paikka jonosta: tähän voidaan asettaa mikä tahansa alkio alkuperäisestä joukosta. Jonon seuraavaan paikkaan voi asettaa minkä tahansa jäljelle jääneistä k-1:stä alkiosta. Tätä alkioiden asettelua jatketaan kunnes kaikki alkiot on käyty läpi. Tuloksena kaikkien mahdollisten jonojen lukumäärälle saadaan k * (k − 1) * ... * 2 * 1 = k!
Jos järjestettävissä alkioissa on samoja alkioita, esimerkiksi (1,1,2,4) permutaatioiden lukumäärässä samat alkiot luetaan eriäviksi. Näin ollen kertoma k! sisältää esimerkiksi järjestyksen (1,2,1,4) kaksi kertaa, sillä 1-alkioiden paikat voidaan vaihtaa keskenään. Siten voidaan myös sanoa, että permutaatio äärellisestä joukosta X on bijektio itseensä.
