Permutatsioon

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.

Üldistused 
Permutatsiooni mõistet kasutatakse järgnevates kontekstides.

Kombinatoorikas 
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 
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.

Permutatsioonide omadused ja erilised permutatsioonid 

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 ineverisoone, 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:
 Iga permutatsioon on esitatav transpositsioonide järjestikuse rakendamise teel.
 Transpositsioon muudab permutatsiooni paarsust.
 Viimast arvesse võttes võib permutatsiooni paarsuse defineerida ka järjestikku rakendavate transpositsioonide arvu kaudu, mis on antud transpositsiooni moodustamiseks tarvis.

Substitutsioonide rühm 
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.

Vaata ka 
Püsipunktita permutatsioon
 Kombinatsioon

Viited

Välislingid 
Kombinatsioonide ja permutatsioonide kalkulaator

Kombinatoorika
Elementaarmatemaatika