Permutaatio

Matematiikassa permutaatioilla tarkoitetaan alkioiden järjestystä. Esimerkiksi järjestetyn joukon {1,2,3,4} yksi permutaatio on (1,3,2,4) ja toinen esimerkiksi (2,1,4,3). Permutaatioiden lukumäärä n-alkioisessa järjestetyssä joukossa on n:n kertoma ${\displaystyle n!}$.^[1] Tämä nähdään seuraavasti:

Oletetaan että joukossa on ${\displaystyle n}$ 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ä ${\displaystyle n-1}$:stä alkiosta. Tätä alkioiden asettelua jatketaan kunnes kaikki alkiot on käyty läpi. Tuloksena kaikkien mahdollisten jonojen lukumäärälle saadaan ${\displaystyle n\times (n-1)\times \ldots \times 2\times 1=n!}$

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 ${\displaystyle 4!}$ 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 ${\displaystyle X}$ on bijektio itseensä.

Voidaan myös järjestää tietyn kokoisia osajoukkoja. Esimerkiksi jos järjestettävänä ovat kirjaimet a, b ja c, niin meillä on 3! eli kuusi järjestystä: abc, acb, bac, bca, cab, cba. Jos kuitenkin haluamme järjestää niistä vain kaksi kirjainta kerrallaan, niin meillä on seuraavat kuusi järjestystä: ab, ba, ac, ca, bc, cb. Yleisemmin jos meillä on ${\displaystyle n}$ eri alkiota ja ${\displaystyle k}$ on kokonaisluku ${\displaystyle 1\leq k\leq n}$, niin ${\displaystyle k}$:n mittaisten osajonojen eli variaatioiden lukumäärä on:^[2]

${\displaystyle P(n,k)={\frac {n!}{(n-k)!}}}$

Tätä kutsutaan myös toisinaan k-permutaatioksi.

Kun halutaan tietää, kuinka monta erilaista pienempijäsenistä osajoukkoa joukosta alkioita voidaan muodostaa puhutaan kombinaatioista.

1. ↑ Viittausvirhe: Virheellinen <ref>-elementti; viitettä h1 ei löytynyt
2. ↑ Viittausvirhe: Virheellinen <ref>-elementti; viitettä Grimaldi ei löytynyt