Permutatsioon

Permutatsioon on kombinatoorikas lõpliku hulga elementidest moodustatud jada, milles iga element esineb täpselt üks kord.

Iga rida neist kuuest reast on erinev permutatsioon kolmest erinevast pallist.

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

$P(n,r)={\frac {n!}{(n-r)!}}.$

erineval moel. Sümbol ! tähistab faktoriaali. Erijuhul, kui r = n

$P(n)=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 S_n. 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 S_n alamrühmaga.

Vaata ka

• Püsipunktita permutatsioon
• Kombinatsioon

Välislingid

• Kombinatsioonide ja permutatsioonide kalkulaator