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 se jo zapiše kot:

$\pi :X_n\to X_n.$

Permutacije $n$ naravnih števil tvorijo simetrično grupo, ki se jo označuje s $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 razpredelnici 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 se imenuje 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}, se eno izmed permutacij lahko zapiše kot

$\pi =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right);$.

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

$\pi =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ \pi (1)& \pi (2)& \pi (3)& \pi (4)& \pi (5)\end{array}\right);$.

Podobno se zapiše dvovrstični zapis za poljubno število elementov $n$.

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

Zgornji primer se zapiše kot:

$\pi =\left(\begin{array}{ccccc}2& 5& 4& 3& 1\end{array}\right);$

• 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 lege, če se permutacije izvajajo po vrsti. To se imenuje tudi razbijanje permutacije v zmnožek disjunktnih ciklov permutacij.

Zgornjo permutacijo se na ta način zapiše kot:

$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right)=\left(\begin{array}{ccc}1& 2& 5\end{array}\right)\left(\begin{array}{cc}3& 4\end{array}\right)=\left(\begin{array}{cc}3& 4\end{array}\right)\left(\begin{array}{ccc}1& 2& 5\end{array}\right)=\left(\begin{array}{cc}3& 4\end{array}\right)\left(\begin{array}{ccc}5& 1& 2\end{array}\right)$. 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 se lahko vsako permutacijo napiše 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 se potrebuje liho število permutacij, da se pride do identične permutacije, se reče, 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:

$\left(\begin{array}{ccc}1& 2& 5\end{array}\right)\left(\begin{array}{cc}3& 4\end{array}\right)$

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

$\begin{array}{c}1⟼2\\ 2⟼5\\ 3⟼4\\ 4⟼3\\ 5⟼1\end{array}$.

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

Kompozitum permutacij

Kompozitum dveh permutacij ${\pi }_1$ in ${\pi }_2$ se imenuje produkt permutacij (grupna operacija). Označuje se 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\ne {\pi }_2\circ {\pi }_1$. Je pa asociativen ${\pi }_1\circ ({\pi }_2\circ {\pi }_3)=({\pi }_1\circ {\pi }_2)\circ {\pi }_3$.

Zgled: obravnavata se dve permutaciji:

${\pi }_1=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right){\pi }_2=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 5& 2& 4& 1\end{array}\right)$

Rezultat se lahko prikaže v obliki matrike s tremi vrsticami:

$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 5& 2& 4& 1\\ 4& 1& 5& 3& 2\end{array}\right)$

kjer se je

• v drugo vrstico vpisalo 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=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 4& 1& 5& 3& 2\end{array}\right)$

kjer se je drugo vrstico izpustilo.

Rezultat se dobi tako, da se najprej opravi permutacijo ${\pi }_1$, na dobljeno permutacijo se izvede še permutacijo ${\pi }_2$.

Zgled: 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 se je dobilo končno obliko permutacije.

Obratna permutacija

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

${\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right)}^{-1}=\left(\begin{array}{ccccc}2& 5& 4& 3& 1\\ 1& 2& 3& 4& 5\end{array}\right)=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& 1& 4& 3& 2\end{array}\right).$.

Identična permutacija

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

$\left(\begin{array}{ccccc}1& 2& 3& \cdots & n\\ 1& 2& 3& \cdots & n\end{array}\right).$

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. Drugi ostanejo na svojih mestih.

Krožna permutacija

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

Zgled: če je množica $a_0,a_1,\dots ,a_n$ in se izvede krožno permutacijo s pomikom za eno mesto proti levi, se bo dobilo zaporedje v množici $a_1,\dots ,a_n,a_0$ (prvi element je prišel na zadnje mesto). Če pa bi se naredila krožna permutacija s pomikom na desno, bi bila nova permutacija $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 se iz množice $n$ elementov vzame $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 se lahko prikaže kot matriko z razsežnostjo $n\times n$. Običajno se vzame za elemente $m_{ij}=1$ pri tistih permutacijah pri katerih je $j=\pi (j)$, drugi pa so enaki 0. Permutacijska matrika ima v vsaki vrstici in stolpcu samo enkrat vpisano enico, na drugih mestih pa vedno 0.

Glej tudi

• kombinacija
• binomski koeficient
• ciklična permutacija
• variacija
• particija
• kompozicija

Zunanje povezave

• Permutacija Predloga:Ikona sl
• Permutacija v Preseku Predloga:Ikona sl
• Predloga:MathWorld