Permutatsioone

Permutatsioone ehk permutatsioonid on hulga elementide järjestuste loomise tulemused. Kui hulgas on n erinevat elementi, on võimalik moodustada kõikvõimalikud järjestused ning iga üks neist on permutatsioon. Näiteks hulgaga {A, B, C} on 3! = 6 erinevat järjekorda: ABC, ACB, BAC, BCA, CAB ja CBA.

Kui elemente võivad esineda kordustega ehk on tegemist multisetiga, muutub permutatsioonide arv. See arv on n! / (n1! n2! ... nk!), kus n on kõigi elementide arv ja n1, n2, ..., nk on korduvate elementide esinemissagedused. See valem võrdleb erinevate järjestuste arvu vastavalt korduste olemasolule.

Permutatsioone saab käsitada ka bijektsioonidena hulga enda vahel: p: H -> H, kus H on hulk. See määrab üheselt, kuhu iga element liigub. Need kujutuvad rühmana S_n, kus n on hulga suurus; S_n sisaldab kõiki permutatsioonide kogusid ja toimimisega (kokkupuutel) moodustab sümmeetrilise rühma.

Transpositsioonid ehk kahe elemendi vahetused ning tsüklid on permutatsioonide lihtsad ehitusühikud; iga permutatsioon on võimalik kirjutada nende korrutisena. Erinevad tüübid hõlmavad identiteetpermutatsiooni ja derangmendi, mis ei fikseeri ühtegi elementi. Rakendused hõlmavad järjestuste korraldamist jaotuslaudades, algoritme ning krüptograafiat, samuti probleeme, kus tuleb leida parim või sobiv järjestus.