permutaatioita

Permutaatiot ovat kaikkien alkioiden uudelleenjärjestelyjä tietyllä joukolla. Jos joukko X sisältää n alkiota, sen permutaatiot ovat kaikki mahdolliset järjestykset, joissa kukin alkio esiintyy täsmälleen kerran. Permutaatiot voidaan esittää sekä bijektioina f: X → X että järjestettyinä jonoina (x1, x2, ..., xn).

Kun joukko on finite, permutaatiotmäärä on n!, eli n:n kertomakerto" ehk. Tämä tarkoittaa, että pienelläkin joukolla (esimerkiksi kolmin) on useita eri järjestyksiä. Permutaatiot eroavat yhdistelmistä siinä, että järjestyksellä on väliä; yhdistelmissa alkioiden määrä ja lajittelu ovat tärkeitä, mutta ei järjestys.

Permutaatiot muodostavat usein ryhmää, jota kutsutaan symmetrinen ryhmäksi ja merkitään S_n. Ryhmän operaatiota kutsutaan koostamiseksi: yhden permutaation lopputulos toisen jälkeen on uusi permutaatiio. Tämän ryhmän tunnusmerkki on identiteettiläisyy, käänteinen permutaation sekä sulautuminen ja associativiteetti.

Tavallisia tapa kuvata permutaatiota ovat yksinkertaiset merkkijonot tai kierteinen esitys. Esimerkiksi joukko {1,2,3} antaa kuusi permutaatiota: 123, 132, 213, 231, 312, 321. Kierteiset esitykset ovat esimerkiksi (12), (13), (23), (123) ja (132).

Permutaatiot löytyvät laajasti matematiikassa ja sen sovelluksissa: kombinatorikassa, algebrassa, todennäköisyyslaskennassa sekä algoritmeissa, kuten järjestysten etsimisessä ja korttien sekoittamisessa. Derangementit eli permutaatiot, joissa mikään alkio ei palaa alkuperäiselle paikalleen, ovat yksi erityinen aihe.