permutatsioonid

Permutatsioonid on mõiste, mis kirjeldab hulga elementide järjestamist nii, et iga element esineb täpselt üks kord ja järjekord on oluline. Kui hulgas on n erinevat elementi, on kõigi võimalike järjestuste arv n! (faktoriaal). Üks järjestus võib väljendada kujul (a1, a2, ..., an).

Kõigi n-elemendi permutatsioonide kogum moodustab sümmeetrilise rühma S_n, mis tegutseb järjestuste koostamisel. Näiteks hulga {1,2,3} permutatsioonid on kuus: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) ja (3,2,1).

Pariteet: Inversioonide arv määrab permutatsiooni pariteedi. Inversioon on paar (i, j) selline, et i < j ja a_i > a_j. Kui inversioonide arv on paaris, on permutatsioon paaris; kui arv on paaritu, on permutatsioon paaritu.

Osa-permutatsioonid: Kui valime k elementi ja paigutame need järjekorda, on arv P(n,k) = n!/(n−k)!. Kui järjestatakse kõik n elementi, on tulemuseks n! permutatsioone. Kui hulgas esinevad korduvad elemendid, on järjestuste arv n!/(m1! m2! ...), kus m1, m2 on korduvuste kordsused.

Rakendused: Permutatsioone kasutatakse järjestuste leidmisel ja hindamisel, sorteerimisel, kombinatoorikas ning tõenäosuste, krüptograafia ja mälumängude lahendamisel, näiteks kaardijärjekordade või Rubiku kuubiku lahendamisel.