Permutacija

Permutácija (oznaka $P(n, k) \,$) (iz latinske besede permutare, kar pomeni zamenjati) je v matematiki z medsebojnimi zamenjavami preurejeno zaporedje znanega končnega števila elementov (pri tem pa število elementov ostane enako). V matematiki je to bijekcija množice elementov $n \,$ samega v sebe, ki jo zapišemo kot:

$\pi : X_n \rightarrow X_n \!\, .$

Permutacije $n \,$ naravnih števil tvorijo simetrično grupo, ki jo označujemo z $S_n \,$. Grupa ima svojo identično funkcijo, vsaka permutacija ima tudi obratno permutacijo, ki povrne dano permutacijo v stanje pred zadnjo zamenjavo.

V naslednji tabeli so prikazane vse permutacije treh elementov (6 permutacij). Za vsako permutacijo so napisane tri zamenjave na treh mestih, kjer so elementi množice.

permutacija	zamenjava 1	zamenjava 2	zamenjava 3
1	$1 \to 1 \,$	$2 \to 2 \,$	$3 \to 3 \,$
2	$1 \to 2 \,$	$2 \to 1 \,$	$3 \to 3 \,$
3	$1 \to 3 \,$	$2 \to 2 \,$	$3 \to 1 \,$
4	$1 \to 1 \,$	$2 \to 3 \,$	$3 \to 2 \,$
5	$1 \to 2 \,$	$2 \to 3 \,$	$3 \to 1 \,$
6	$1 \to 3 \,$	$2 \to 1 \,$	$3 \to 2 \,$

Prva permutacija se imenuje identična permutacija Pri tej permutaciji v resnici ostanejo elementi na svojih mestih.. Pri vseh ostalih pa zamenjajo mesta.

Sam postopek preurejanja zaporedja elementov imenujemo permutiranje.

Načini označevanja permutacij

Znani so trije različni načini za opis permutacij v končni množici $S \,$.

• V dvovrstičnem načinu se v prvi vrstici napišejo elementi množice $S \,$, v drugi vrstici pa se vpiše permutacija elementov.

Za množico $S \,$, ki ima elemente {1, 2, 3, 4, 5}, eno izmed permutacij lahko zapišemo kot

$\pi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{pmatrix};$.

S tem smo permutacijo opisali z matriko, ki ima 2 vrstici in 5 stolpcev. Pri tem pa je 5 kardinalnost množice, ki jo permutiramo. Druga vrstica nam tako pove na katerem mestu je po permutaciji element, ki je napisan v prvi vrstici. To je enako kot

$\pi=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ \pi (1) & \pi (2) & \pi (3) & \pi (4) & \pi (5)\end{pmatrix};$.

Podobno zapišemo dvorstični zapis za poljubno število elementov $n \,$.

• Enovrstični način opisa vsebuje samo drugo vrstico.

Zgornji primer zapišemo kot

$\pi=\begin{pmatrix} 2 & 5 & 4 & 3 & 1\end{pmatrix};$

• Ciklični zapis temelji na dejstvu, da se permutacije izvajajo v določenem zaporedju. V tem načinu zapisa se pokaže kateri elementi so menjali položaje, če se permutacije izvajajo po vrsti. To imenujemo tudi razbijanje permutacije v zmnožek disjunktnih ciklov permutacij.

Zgornjo permutacijo na ta način zapišemo kot

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{pmatrix} = \begin{pmatrix}1 & 2 & 5 \end{pmatrix} \begin{pmatrix}3 & 4 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}1 & 2 & 5 \end{pmatrix}= \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}5 & 1 & 2 \end{pmatrix}$. Permutacija elementov $1, 2, \dots, n \,$ se lahko piše v obliki ciklov kot $(1, 2) (2,3) (3,4) \dots (n-1,n)\,$. To pomeni, da lahko vsako permutacijo napišemo kot produkt transpozicij. Vsak element množice nastopa natanko samo v enem ciklu. . Vsak cikel pa je tudi permutacija. Permutacija je soda, če je produkt sodega števila transpozicij, in liha, če je produkt lihega števila transpozicij. Sodost in lihost permutacije določa parnost permutacije. Če potrebujemo liho število permutacij, da pridemo do identične permutacije, pravimo, da je parnost permutacije liha. Podobno velja tudi za sode permutacije.

To je enako kot

$\pi (1) = 2 \,$,

$\pi (2) = 5 \,$,

$\pi (3) = 4 \,$,

$\pi (4) = 3 \,$,

$\pi (5) = 1 \,$

Ciklični zapis permutacije

$\begin{pmatrix} 1 & 2 & 5 \end{pmatrix} \begin{pmatrix} 3 & 4 \end{pmatrix}\,$

Pomeni, da 1 zamenjamo z 2, 2 zamenjamo s 5 ter 5 zamenjamo z 1. Drugi oklepaj pa pomeni, da 3 zamenjamo s 4 in 4 zamenjamo s 3. To je

$\begin{matrix}1\longmapsto 2\\2\longmapsto 5\\3\longmapsto 4\\4\longmapsto 3\\5\longmapsto 1\end{matrix}$.

Vsaka permutacija končne množice je produkt disjunktnih ciklov.

Kompozitum permutacij

Kompozitum dveh permutacij $\pi_1 \,$ in $\pi_2 \,$ imenujemo produkt (zmnožek) permutacij (grupna operacija). Označujemo ga z $\pi_1 \circ \pi_2 \,$. V splošnem velja tudi, da produkt permutacij ni komutativen. To pomeni, da $\pi_1 \circ \pi_2 \neq \pi_1 \circ \pi_2 \,$. Je pa asociativen $\pi_1 \circ (\pi_2 \circ \pi_3) = (\pi_1 \circ \pi_2) \circ \pi_3 \,$.

Primer: Imamo dve permutaciji

$\pi_1=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 5 & 4 & 3 & 1\end{pmatrix}\qquad \pi_2=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\3&5&2&4&1\end{pmatrix}$

Rezultat lahko prikažemo v obliki matrike s tremi vrsticami:

$\begin{pmatrix}1 & 2 & 3 & 4 & 5\\3&5&2&4&1\\ 4&1&5&3&2\end{pmatrix}$

kjer smo

• v drugo vrstico vpisali permutacijo $\pi_2 \,$
• v tretji vrstici pa je vpisan rezultat kompozituma

Torej je kompozitum dveh permutacij $\pi_1 \circ \pi _2 = \pi _3 \,$ enak

$\pi_3=\pi_1\circ\pi_2= \begin{pmatrix}1 & 2 & 3 & 4 & 5\\4&1&5&3&2\end{pmatrix}$

kjer smo drugo vrstico izpustili.

Rezultat dobimo tako, da najprej opravimo permutacijo $\pi_1 \,$, na dobljeno permutacijo še izvedemo permutacijo $\pi_2 \,$.

Primer: po permutaciji $\pi_2 \,$ se 1 zamenja s 3, ki pa se zaradi permutacije $\pi_1 \,$ zamenja s 4. V nadaljevanju se 2 najprej zamenja s 5, ki se zamenja z 1. Nato sledi zamenjava 3 z 2, ki se zamenja s 5. Nato sledi zamenjava 4 s 4, ki ji sledi zamenjava s 3. Zadnja pa je zamenjava 5 z 1, ki ji sledi zamenjava z 2. S tem smo dobili končno obliko permutacije.

Obratna permutacija

Ker ima bijektivna preslikava tudi obratni (inverzni) element, lahko definiramo obratni element tudi za permutacijo. Označimo ga z $\pi^{-1}\,$. Obratna permutacija je tudi ena izmed permutacij. Z dvovrstičnim zapisom (glej spodaj) je to

$\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{pmatrix}^{-1} =\begin{pmatrix}2 & 5 & 4 & 3 & 1\\ 1 & 2 & 3 & 4 & 5 \end{pmatrix} =\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 4 & 3 & 2\end{pmatrix}.$.

Identična permutacija

Identična permutacija preslika vse elemente sama v sebe. To lahko zapišemo kot

$\begin{pmatrix}1 & 2 & 3 & \cdots & n \\ 1 & 2 & 3 & \cdots & n\end{pmatrix}.$.

V takšni permutaciji ostane prvi element na prvem mestu, drugi element na drugem in tako dalje do zadnjega elementa množice.

Transpozicija

V transpoziciji zamenjata mesti samo dva elementa iz množice. Ostali ostanejo na svojih mestih.

Krožna permutacija

Krožna permutacija je permutacija v kateri premaknemo elemente urejene množice za določen pomik v levo ali desno, višek elementov na drugi strani pa vrinemo na začetku v istem vrstnem redu. To je podobno vrtenju.

Primer: Če imamo množico $a_0, a_1 \dots, a_n \,$ in izvedemo krožno permutacijo s pomikom za eno mesto proti levi, bomo dobili zaporedje v množici $a_1, \dots, a_n, a_0 \,$ (prvi element je prišel na zadnje mesto). Če pa bi naredili krožno permutacijo s pomikom na desno, pa bi nova permutacija bila $a_n, a_0, a_1, \dots \,$ (zadnji element je prišel na prvo mesto)

Število permutacij

Število vseh permutacij reda $n \,$ je enako

$P_n=A_n^n=n!=1\cdot 2\cdot\dots\cdot n.$

kjer je

• $n! \,$ fakulteta števila $n \,$ ($0! = 1 \,$).

Kadar pa iz množice $n \,$ elementov vzamemo $k \,$ elementov, je število permutacij enako $\frac {n!} {(n - k)!} \,$. V tem primeru je seveda nekaj elementov nerazporejenih ($k < n \,$)

Poseben primer je število permutacij, če so v množici $n \,$ med seboj enaki elementi. Če je med $n \,$ elementi enakih $k_1, k_2 \dots, k_m \,$, potem je število možnih permutacij enako

$P_n^{k_1, k_2, \dots, k_m} = \frac {n!} {k_1!k_2 ! \dots k_m !} \,$

Permutacijska matrika

Vse permutacije $n \,$ elementov lahko prikažemo kot matriko z razsežnostjo $n \times n \,$. Običajno vzamemo za elemente $m_{ij} = 1 \,$ pri tistih permutacijah pri katerih je $j =\pi (j) \,$, ostali pa so enaki 0. Permutacijska matrika ima v vsaki vrstici in stolpcu samo enkrat vpisano enico, na ostalih mestih pa vedno 0.

Glej tudi

• kombinacija
• binomski koeficient
• ciklična permutacija

Zunanje povezave

• Permutacija (v slovenščini)
• Permutacija v Preseku (v slovenščini)