 | See artikkel vajab toimetamist. (Veebruar 2008) |
Permutatsioon on kombinatoorikas lõpliku hulga elementidest moodustatud jada, milles iga element esineb täpselt üks kord.
Hulk erineb jadast, kuna erinevalt viimasest pole hulgas elementide järjestus oluline. Näiteks {1,2,3} ja {1,3,2} tähistavad samu hulki, kuid erinevaid permutatsioone.
Permutatsiooni mõistet kasutatakse järgnevates kontekstides.
Kui on antud mingi n elemendist koosnev hulk ning me valime sellest hulgast r elementi (kus 0 ≤ r ≤ n), siis on neid elemente võimalik järjestada
erineval moel. Sümbol ! tähistab faktoriaali. Erijuhul, kui r = n
Seega n elemendilisi permutatsioone n elemendisest hulgast on täpselt n!.
Rühmateoorias käsitletakse suvaliste (isegi lõpmatute) hulkade permutatsioone. Hulga S permutatsiooniks on bijektsioon hulgast S hulka S, mis annabki võimaluse permutatsioonide koostamiseks ja see omakorda võimaldab defineerida permutatsioonide rühma. Kui hulk S on lõplik, sisaldades n elementi, siis hulgal S on n! permutatsiooni.
Inversiooni moodustavad elemendid i ja j parajasti siis, kui i on eespool j-st kuid i > j.
Permutatsiooni paarsus on seotud inversioonide arvuga permutatsioonis. Kui permutatsioonis leidub paaris või paaritu arv inversioone, siis nimetatakse permutatsiooni vastavalt paarispermutatsiooniks või paarituks permutatsiooniks.
Transpositsioon on kahe elemendi ümbervahetamine, kusjuures kõik ülejäänud elemendid jäävad samaks. Transpositsioonide jaoks kehtib:
Bijektiivseid teisendusi hulgal nimetatakse substitutsioonideks. Saab näidata, et hulga substitutsioonid moodustavad rühma. Kui tegu on n elemendist koosneva lõpliku hulgaga, siis nimetatakse selle substitutsioonidest moodustunud rühma substitutsioonide rühmaks ja tähistatakse Sn. Substitutsioone on võimalik väljendada permutatsioonide abil.
Cayley-Hamiltoni teoreem ütleb, et iga lõplik rühm G on isomorfne mõne substitutsioonide rühma Sn alamrühmaga.
