permutatsioonides

Permutatsioonid on hulga elementide järjestuste moodustamine nii, et iga element esineb täpselt ühel korral. Kui hulka kuuluvad n erinevat elementi, on kõigi võimalike järjestuste arv n! (faktoriaal). Kõigi permutatsioonide kogumit nimetatakse sümmeetriliseks rühmaks ja tähistatakse S_n. See rühm koosneb kõigist bijektsioonidest hulga X suhtes X → X ning selle toiminguks on permutatsioonide liitmine ehk kompositsioon.

Permutatsioonid võib vaadelda ka bijektsioonidena, mille mõju on hulga X elementide ümber paigutamine. Kui X on näiteks {1, 2, ..., n}, iga permutatsioon määrab, kuhu iga element liigub, ja kogu toime on invertne.

Tsükliline dekompositsioon on üks peamisi viise permutatsioonide kirjeldamiseks. Iga permutatsioon saab esitada tsüklite kogumina: näiteks (a1 a2 ... ak)(b1 b2 ... bm) jne, kus iga element kuulub täpselt ühte tsüklisse. Tsüklite pikkuste järgi määratakse permutatsiooni järk: järk on väikseim positiivne täisarv t, mille korral permutation^t on identiteet. See järk võrdub kõigi tsüklite pikkuste lõpliku täisarvu (LCM).

Pariteet: permutatsioon on paaris, kui seda saab esitada paari transpositsioonide ühendina; vastasel juhul on see paaritu. Pariteet on määratud tsüklite dekompositsiooniga: sign = (-1)^{n-c}, kus n on elementide arv ja c tsüklite arv (kaasaarvatud 1-tsüklid).

Rakendused ja seosed: permutatsioonid moodustavad aluse sünmeetilise rühma teooriale ning neid kasutatakse paljudes kombinatoorika ja algebra probleemides, sealhulgas järjestuste arvutamisel, sorteerimisanalüüsis ning rühmade teoorias, kus erinevad alamhulgad ja pariteet mängivad olulist rolli.