permutatsioonidel

Permutatsioonid on matemaatiline mõiste, mis kirjeldab finite hulga elementide järjestuste muutmist. Kui X on n-elementne hulk, on permutatsioon p: X → X bijektsioon, mis määrab igale elemendile uue positsiooni. Kõik need permutatsioonid moodustavad koos komponeerimisega rühma, mida nimetatakse S_n ehk sümmeetriliseks rühmaks.

Permutatsiooni saab esitada mitmel viisil. Ühe reale märgistamisel kirjutatakse p(i) iga i korral, mis näitab, kuhu i element edasi liigub. Tsükliline märgistamine kirjeldab permutationi kui disjunktide tsüklite kogumit: iga element liigub tsüklis järgmisesse positsiooni. Disjunktide tsüklite kaudu saab näha struktuuri ja omadusi, näiteks pariteeti, mis on permutatsiooni “kõrgem” omadus määratud selle kui mitu paari võrra vahetame.

Arvutuslikult: kui X sisaldab n erinevat elementi, on kõigi permutatsioonide arv n!. Kui elemendid on korduvad (multiset), muutub arv: n!/(n1! n2! ...), kus n1, n2, ... on vastavate korduste arvud. Need valemid kirjeldavad, kui palju erinevaid järjekordi tekib sõltuvalt kordustest.

Rühmade ja rakenduste poolest moodustavad kõik permutatsioonid rühma S_n, mille operatsioon on kompositsioon. Iga permutatsioon saab väljendada transpositsioonide (kaks elementi vahetavate toimingute) järjestusena, mis näitab, et S_n on transpositsioonide kaudu genereeritav. Permutatsioonid on olulised sorteerimisalgoritmides, kombinatorikas, molekulaarses struktuurides ja erinevates simulatsioonides.