Permutaatio

Permutaatio on järjestetty järjestys alkioista. Matematiikassa permutaatioksi kutsutaan bijektiota joukossa, joka kuvaa alkioiden uuden sijoituksen. Jos joukko on n erillistä alkiota, kuten {1, 2, ..., n}, sen permutaatioita on n!, ja ne muodostavat ryhmän S_n, joka tunnetaan symmetrisenä ryhmänä.

Permutaation voi esittää sekä uuden järjestyksenä luettelona että kuvaajana σ: A → A, jossa kukin alkio siirtyy toisen alkion paikalle. Yleisimmät esitystavat ovat lista ja kierto-merkintä. Kiertokaavio havainnollistaa, miten alkioista muodostuu kiertojoukkoja; esimerkiksi kierto (1 3 5) tarkoittaa 1 → 3, 3 → 5, 5 → 1.

Identiteettiperma on se, jossa jokainen alkio pysyy omassa paikassaan. Permutaatiot voidaan luokitella parillisiin ja parittomiin sen mukaan, kuinka monta transpositiota niiden muodostamiseen tarvitaan. Pariteetti liittyy kiertojen rakenteeseen ja determinantteihin.

Kokonaismäärä, kun alkiot ovat erillisiä, on n!. Jos alkiot toistuvat, määrää laskettaessa käytetään korjauskerrointa: n! / (m1! m2! ...), missä m_i ovat toistuvuuksien lukumäärät.

Sovelluksia: permutaatiot ovat keskeisiä combinatoriikassa, algoritmeissa kuten lajittelussa ja kokeiden suunnittelussa sekä pulmapelien ja salaustekniikoiden taustalla. Ne mallintavat erilaisia järjestyksiä ja mahdollistavat niiden analysoinnin sekä laskennan.