Parnost permutacije

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

• parne permutacije
• neparne permutacije

Parnost permutacije se določi kot parnost ali neparnost š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 dano permutacijo prevedemo v identično permutacijo. Če potrebujemo liho število permutacij, da pridemo do identične permutacije, rečemo, da 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 \,$ paren (sodo število), in -1, če ima $\sigma \,$ neparno vrednost (liho število). Permutacija je parna, če je zanjo potrebno parno število permutacij, in je neparna, če je zanjo zanjo potrebno neparno število permutacij.

$\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 ostali 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 zapišemo v obliki ciklov. Število elementov, ki nastopajo v ciklu, imenujemo dolžino cikla. Od dolžine cikla odštejemo 1 in nato seštejemo vse vrednosti, ki smo jih dobili. Če je vsota sodo število, je tudi permutacija soda in obratno. Transpozicija je neparna 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 moramo sešteti $2 \,$ in $1 \,$, ter dobimo $3 \,$. To pomeni, da je permutacija liha. To permutacijo lahko zapišemo kot kompozitum transpozicij

$\sigma=(2 3) (1 2) (2 4) (3 5) (4 5) \;$.

Zunanje povezave

• Parnost permutacije na PlanetMath (v angleščini)