Permutatsioon

Permutatsioon tähendab kombinatoorikas lõpliku hulga elementidest moodustatud jada, kus 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.

ÜldistusedRedigeeri

Permutatsiooni mõistet kasutatakse järgnevates kontekstides.

KombinatoorikasRedigeeri

Kui on antud mingi n elemendist koosnev hulk ning me valime sellest hulgast r elementi (kus 0 ≤ rn), 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ühmateooriasRedigeeri

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 permutatsioonidRedigeeri

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.[1]

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ühmRedigeeri

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 kaRedigeeri

ViitedRedigeeri

  1. M Kilp, Algebra I (1998)

VälislingidRedigeeri