Parnost permutacije

Parnost permutacije je v matematiki za končno množico vsaj dveh elementov $X\,$ značilnost vsake posamezne permutacije. Po parnosti se permutacije delijo v

• sode (parne) permutacije
• lihe (neparne) permutacije

Parnost permutacije se določi kot sodost ali lihost števila transpozicij, ki so potrebne za permutacijo $\sigma \,$, to je število elementov $x\,$ in $y\,$ iz množice $X\,$, tako, da je $x<y\,$ oziroma $\sigma (x)>\sigma (y)\,$. To seveda pomeni, da parnost pomeni lihost ali sodost števila permutacij, ki so potrebne, da se dano permutacijo prevede v identično permutacijo. Če se potrebuje liho število permutacij, da se pride do identične permutacije, je parnost permutacije liha. Podobno velja tudi za sode permutacije.

Parnost permutacije $\sigma \,$ se označuje s sign(σ) , ki pa je enaka 1, če je $\sigma \,$ sodo število, in -1, če je $\sigma \,$ liho število. Permutacija je soda, če je zanjo potrebno sodo število permutacij, in je liha, če je zanjo zanjo potrebno liho število permutacij.

$\operatorname {sgn}(\sigma )=(-1)^{N(\sigma )}\!\,,$

kjer je:

• $N(\sigma )\,$ število transpozicij v permutaciji $\sigma \,$

Parnost se menja pri zamenjavi dveh elementov (transpozicija), pri tem pa drugi ostanejo na istih mestih. Vsaka permutacija se lahko obravnava kot produkt transpozicij. Vedno je število sodih permutacij enako številu lihih permutacij.

Določanje parnosti permutacije

Permutacijo se zapiše v obliki ciklov. Število elementov, ki nastopajo v ciklu, se imenuje dolžina cikla. Od dolžine cikla se odšteje 1 in nato sešteje vse vrednosti, ki se ji dobi. Če je vsota sodo število, je tudi permutacija soda in obratno. Transpozicija je liha permutacija.

Zgled

Dana je permutacija

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

Dolžina prvega cikla je 3, drugega 2. To pomeni, da je treba sešteti $2\,$ in $1\,$, ter se dobi $3\,$. To pomeni, da je permutacija liha. To permutacijo se lahko zapiše kot kompozitum transpozicij

$\sigma =(23)(12)(24)(35)(45)\;$.

Glej tudi

• igra 15
• lema Zolotarjova

Viri

• Klavžar, Sandi (1988), »O igri petnajst in permutacijah« (PDF), Presek, 16 (3): 159–163, COBISS 3094020

Zunanje povezave

• Parnost permutacije Arhivirano 2011-06-04 na Wayback Machine. na PlanetMath (angleško)
• Weisstein, Eric Wolfgang. »Even Permutation«. MathWorld.