Permutation

För den juridiska termen, se Permutation (juridik).

Inom matematiken används termen permutation i flera besläktade betydelser, nämligen som en funktion, en omordning, eller som ett urval.

Olika betydelser

Den vanligaste betydelsen är att en permutation av mängden M är en bijektiv funktion från M till sig själv. Mängden av permutationer på M bildar en grupp med operatorn funktionssammansättning, vilken kallas den symmetriska gruppen på M. Begreppet permutation används i denna betydelse allmänt inom de flesta grenar av matematiken, bland annat inom sannolikhetsteori, algebra och talteori.

Antalet olika permutationer av en mängd innehållande n stycken element är n!, där $n!=n(n-1)(n-2)...\cdot 2\cdot 1$ och utläses "n-fakultet". Detta kan förklaras med att det för det första elementet, finns n möjliga alternativ. För nästa element finns n-1 element kvar att välja mellan, för det tredje elementet n-2 element, och så vidare till och med det sista elementet, där således inga andra alternativ finns.

Mängden $C=\{a,b,c\}$ kan alltså permuteras på 3! = 6 sätt: abc, acb, bac, bca, cab, cba.

Om man ur en mängd med n element skulle välja ut r av dessa och sedan permutera urvalet, finns det ${\frac {n!}{(n-r)!}}$ permutationer av dessa. För detta har man infört skrivsätten P(n, r), $_{n}P_{r}$ och $P_{r}^{n}$ .

Detta gäller självklart också i specialfallet n = r, eftersom $P(n,n)={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$ , vilket gäller eftersom $0!$ är en tom produkt, som per definition är lika med 1.

Ibland används i stället termen permutation för att beteckna en omordning av en ordnad uppsättning element. Med detta synsätt är exempelvis (1,4,2,3) en permutation av (1,2,3,4). Detta ligger mycket nära uppfattningen av en permutation som en bijektion; exemplet motsvaras av

f:\{1,2,3,4\}\rightarrow \{1,2,3,4\}{\text{ givet av }}f(1)=1,\ f(2)=4,\ f(3)=2{\text{ och }}f(4)=3\,.

Den "naturliga" sammansättningen av omordningar är dock inte densamma som funktionssammansättningen. Uppfattar man permutationer som omordningar, så låter man därför oftast fg betyda g_°f i stället för f_°g.

Slutligen används också ibland permutation som synonym till ordnat urval utan upprepning av element i en mängd. Ofta kontrasteras då permutationer mot oordnade urval utan upprepning, som då kan kallas kombinationer. De förra tar alltså hänsyn till i vilken ordning elementen i urvalet kommer. abc och bca är således i denna mening inte samma permutation, men samma kombination, ur mängden {a,b,c,d,e}.

I resten av denna artikel kommer permutation främst att användas i den förstnämnda betydelsen.

Notation, produkter och inverser av permutationer

En permutation σ av en mängd X = {x₁, x₂, ..., x_n} kan representeras på en tvåradsform, där elementet x_k står på första raden och bilden, σ(x_k) på andra raden:

\sigma ={\begin{pmatrix}x_{1}&x_{2}&\dots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\dots &\sigma (x_{n})\end{pmatrix}}

Man kan även ange permutationer på enradsform, då man bara ger den nedre raden.

Inom gruppteori behandlas ofta permutationer av mängden X = {1, 2, ..., n} då man ofta använder cykelnotation, där man börjar med 1, sedan σ (1), σ(σ(1)), osv. Exempelvis kan permutationen av {1, 2, 3} som avbildar 1 på 3, 2 på 1 och 3 på 2 på tvåradsform, på enradsform respektive med cykelnotation anges som:

\sigma ={\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}\qquad \sigma ={\begin{pmatrix}3&1&2\end{pmatrix}}\qquad \sigma ={\begin{pmatrix}1&3&2\end{pmatrix}}

.

Dock är inte alla permutationer en stor cykel utan flera mindre, då man skriver (tvåradsform respektive cykelnotation):

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

σ består alltså av två cykler, den första cykeln består av σ (1) = 3, σ (3) = 2 och σ (2) = 1 och den andra av σ (4) = 5, σ(5) = 4.

En produkt av två permutationer σ och π kan definieras som funktionssammansättningen σ(π(x)). Eftersom funktionssammansättning är associativ är multiplikation av permutationer associativ. Vidare, eftersom bijektioner har inverser har permutationer inverser och även de är permutationer. Man har exempelvis:

\sigma ^{-1}={\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}^{-1}={\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}

Cykelstruktur, jämna och udda permutationer

En permutation σ på X = {1, 2, ..., n} kallas en r-cykel, eller en cykel av längd r om det finns heltal i₁, i₂, ..., i_r så att

\sigma (i_{1})=\sigma (i_{2}),\sigma (i_{2})=\sigma (i_{3}),\dots ,\sigma (i_{r-1})=\sigma (i_{r}),\sigma (i_{r})=\sigma (i_{1})

och resten av elementen i 1, 2, ..., n är fixpunkter till σ. En cykel av längd 2 kallas för en transposition.

Två permutationer är disjunkta om varje element som flyttas av den ena permutationen är fixpunkt till den andra. Disjunkta permutationer kommuterar och alla permutationer är en produkt av disjunkta cykler, cykler själva är en produkt med en faktor. En fullständig faktorisering av en permutation är en faktorisering av permutationen i disjunkta cykler, inklusive cykler av längd 1 för element som fixeras av permutationen.^[1].

Om en permutation σ faktoriseras fullständigt och cyklerna ordnas i avtagande ordning efter deras längder, fås permutationens cykelstruktur som är just följden (l₁, l₂, ..., l_k) av de disjunkta cyklernas längder.

Varje permutation kan även skrivas som en produkt av transpositioner (inte nödvändigtvis disjunkta). En permutation kallas jämn respektive udda om den är en produkt av ett jämnt respektive udda antal transpositioner.

Fixpunkter och banor

Låt σ vara en bestämd permutation på en mängd M. Varje x i M, som är sådant att σ(x) = x, kallas en fixpunkt (med avseende på permutationen σ). Mängden av fixpunkter betecknas ibland M^σ. Med denna beteckning är alltså

M^{\sigma }=\{x\in M:\sigma (x)=x\}\,.

Om σ saknar fixpunkter, det vill säga, om M^σ är den tomma mängden, så kallas σ ett derangemang.

Oavsett om x är en fixpunkt eller inte, så är ju σ(x) "bilden" av x (med avseende på σ). På liknande sätt är σ(σ(x)) "bilden av bilden av x", och så vidare. Man kan tolka detta som att x "genomlöper" σ(x), σ(σ(x)), och så vidare, och på samma sätt redan har "genomlöpt" σ^-1(x), σ^-1(σ^-1(x)), och så vidare. Därför definierar man banan för x som mängden