Permutatsioon

Allikas: Vikipeedia
Jump to navigation Jump to search

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.

Üldistused[muuda | muuda lähteteksti]

Permutatsiooni mõistet kasutatakse järgnevates kontekstides.

Kombinatoorikas[muuda | muuda lähteteksti]

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ühmateoorias[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

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ühm[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

Viited[muuda | muuda lähteteksti]

  1. M Kilp, Algebra I (1998)

Välislingid[muuda | muuda lähteteksti]