permutatsioonide

Permutatsioonid on hulga n erineva elemendi erinevad järjekorrad. Kui hulk on {1, 2, ..., n}, siis üks permutatsioon on järjestus π = (π(1), π(2), ..., π(n)). Permutatsioonide arv ehk kõigi järjestuste kogum on n! (fakultet). Näiteks hulgast {A, B, C} on 3! = 6 permutatsiooni: ABC, ACB, BAC, BCA, CAB, CBA.

Permutatsioonide tüübid: ilma kordusteta ehk järjestused, kus iga element esineb täpselt üks kord; ja korduvate elementidega järjestused, kus elemendid võivad korduda. Kui valitakse järjestus pikkusega k ilma kordusteta, on arv P(n, k) = n!/(n−k)!, kus k ≤ n. Kui kordusi lubatakse ja järjestus koosneb k positsioonist, on arv n^k.

Grupilises mõttes moodustab kõigi n elemendi permutatsioonide hulk S_n sümmeetrilise rühma, mille liikmed on kõik permutatsioonid ja mille toiminguks on järjestuste ühendamine (komponeerimine). Pariteet: iga permutatsioon on paaris või paaritu; see määratakse selle koostises olevate vahetuste (transpositsioonide) arvu põhjal.

Rakendused: permutatsioonide mõistmine on keskne kombinatoorikas ja algebras ning mängib olulist rolli arvutiteaduses, sorteerimis- ja otsingualgoritmides ning krüptograafias. Permutatsioonide teadmised aitavad lahendada ülesandeid, kus on vaja järjestada esemeid või luua järjestatud järjestusi.