Permutatsioon

Allikas: Vikipeedia

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

Permutatsiooni mõistet kasutatakse järgnevates kontekstides.

Kombinatoorikas[muuda | redigeeri 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

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

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

 P(n) = n! \ .

Seega n elenemdilisi permutatsioone n elemendisest hulgast on täpselt n!.

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

Viited[muuda | redigeeri lähteteksti]

  1. M Kilp, Algebra I (1998)

Välislingid[muuda | redigeeri lähteteksti]