„Permutation“ – Versionsunterschied

Unter einer Permutation (von lateinisch permutare vertauschen) versteht man in der Kombinatorik eine Anordnung von Objekten in einer bestimmten Reihenfolge. Je nachdem, ob manche Objekte mehrfach auftreten dürfen oder nicht, spricht man von einer Permutation mit Wiederholung oder einer Permutation ohne Wiederholung. Die Anzahl der Permutationen ohne Wiederholung ergibt sich als Fakultät, während die Anzahl der Permutationen mit Wiederholung über Multinomialkoeffizienten angegeben wird.

In der Gruppentheorie ist eine Permutation ohne Wiederholung eine bijektive Selbstabbildung einer in der Regel endlichen Menge, wobei als Referenzmengen meist die ersten natürlichen Zahlen verwendet werden. Die Menge der Permutationen der ersten ${\displaystyle n}$ natürlichen Zahlen bildet mit der Hintereinanderausführung als Verknüpfung die symmetrische Gruppe vom Grad ${\displaystyle n}$. Das neutrale Element dieser Gruppe stellt die identische Permutation dar, während das inverse Element die inverse Permutation ist. Die Untergruppen der symmetrischen Gruppe sind die Permutationsgruppen. Wichtige Kennzahlen von Permutationen sind ihr Typ, ihre Ordnung und ihr Vorzeichen.

Permutationen besitzen vielfältige Einsatzbereiche innerhalb und außerhalb der Mathematik, beispielsweise in der linearen Algebra (Leibniz-Formel), der Analysis (Umordnung von Reihen), der Graphentheorie und Spieltheorie, der Kryptographie (Verschlüsselungsverfahren), der Informatik (Sortierverfahren) und der Quantenmechanik (Pauli-Prinzip).

Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Beispiele für Permutationen sind:

• Ein Anagramm ist eine Permutation der Buchstaben eines Wortes, wie beispielsweise ENKEL und NELKE.
• Das Mischen der Karten eines Kartenspiels ist (im Idealfall) eine zufällige Permutation der Karten.
• Im Volleyball ist der Stellungswechsel nach Eroberung des Aufschlagsrechts eine zyklische Permutation der Spieler.
• Viele Sortierverfahren arbeiten mit sukzessiven Transpositionen, also Permutationen, die genau zwei Objekte vertauschen.

Werden in einer solchen Anordnung nicht alle Objekte ausgewählt, spricht man statt von einer Permutation von einer Variation, spielt die Reihenfolge bei der Auswahl keine Bedeutung von einer Kombination. In der abzählenden Kombinatorik stellt sich nun die Frage nach der Anzahl möglicher Permutationen. Hierbei unterscheidet man den Fall, dass alle Objekte verschieden sind, von dem Fall, dass manche der Objekte identisch sind.

Eine Permutation ohne Wiederholung ist eine Anordnung von ${\displaystyle n}$ Objekten, die alle unterscheidbar sind. Nachdem es für das erste Objekt ${\displaystyle n}$ Platzierungsmöglichkeiten gibt, kommen für das zweite Objekt nur noch ${\displaystyle n-1}$ Möglichkeiten in Betracht, für das dritte Objekt nur mehr ${\displaystyle n-2}$ und so weiter bis zum letzten Objekt, dem nur noch ein freier Platz bleibt. Die Anzahl der möglichen Permutationen von ${\displaystyle n}$ Objekten wird demnach durch die Fakultät

${\displaystyle n!=n\cdot (n-1)\cdot \ldots \cdot 1}$

angegeben.

Beispielsweise gibt es ${\displaystyle 4!=4\cdot 3\cdot 2\cdot 1=24}$ mögliche Anordnungen von vier verschiedenfarbigen Kugeln in einer Reihe.

Eine Permutation mit Wiederholung ist eine Anordnung von ${\displaystyle n}$ Objekten, von denen manche nicht unterscheidbar sind. Sind genau ${\displaystyle k}$ Objekte identisch, dann sind diese auf ihren Plätzen vertauschbar, ohne dass sich dabei eine neue Reihenfolge ergibt. Auf diese Weise sind genau ${\displaystyle k!}$ Anordnungen gleich. Die Anzahl der Permutationen von ${\displaystyle n}$ Objekten, von denen ${\displaystyle k}$ identisch sind, ist demnach durch die fallende Faktorielle

${\displaystyle {\frac {n!}{k!}}=n\cdot (n-1)\cdot \ldots \cdot (k+1)=n^{\underline {n-k}}}$

gegeben. Gibt es nicht nur eine, sondern ${\displaystyle s}$ Gruppen mit jeweils ${\displaystyle k_{1},\ldots ,k_{s}}$ identischen Objekten, so können all diese Objekte auf ihren Plätzen vertauscht werden, ohne dass sich neue Anordnungen ergeben. Zählt man auch die Objekte, die nur einmal vorkommen, mit Vielfachheit ${\displaystyle 1}$, dann gilt ${\displaystyle k_{1}+\ldots +k_{s}=n}$ und die Anzahl der möglichen Permutationen wird durch den Multinomialkoeffizient

${\displaystyle {\frac {n!}{k_{1}!\cdot \ldots \cdot k_{s}!}}={\binom {n}{k_{1},\ldots ,k_{s}}}}$

angeben.

Beispielsweise gibt es ${\displaystyle {\tfrac {4!}{2!\,1!\,1!}}={\tfrac {24}{2}}=12}$ mögliche Anordnungen von vier farbigen Kugeln in einer Reihe, wenn genau zwei der Kugeln die gleiche Farbe aufweisen, und ${\displaystyle {\tfrac {4!}{2!\,2!}}={\tfrac {24}{4}}=6}$ mögliche Anordnungen, wenn jeweils zwei Kugeln gleichfarbig sind.

Sei ${\displaystyle X=\{x_{1},x_{2},\ldots ,x_{n}\}}$ eine Menge mit ${\displaystyle n}$ Elementen, dann ist eine ${\displaystyle n}$-stellige Permutation (ohne Wiederholung) eine bijektive Abbildung

${\displaystyle \sigma \colon X\rightarrow X}$,

die jedem Element der Menge ein Element der gleichen Menge zuordnet. Anschaulich nimmt durch die Permutation jedes Element ${\displaystyle x_{i}}$ für ${\displaystyle i=1,\ldots ,n}$ den Platz des ihm zugeordneten Elements ${\displaystyle \sigma (x_{i})}$ ein. Aufgrund der Bijektivität der Abbildung werden dabei zwei verschiedene Elemente niemals auf das gleiche Element abgebildet.

Da auf jeder endlichen Menge eine lineare Ordnung festgelegt werden kann (beispielsweise die durch die Indizierung der Elemente gegebene), kann man sich bei der mathematischen Betrachtung von Permutationen stets auf die ersten ${\displaystyle n}$ natürlichen Zahlen als Referenzmenge beschränken. Eine Permutation ist dann eine bijektive Abbildung

${\displaystyle \sigma \colon \{1,2,\ldots ,n\}\rightarrow \{1,2,\ldots ,n\}}$,

die jeder natürlichen Zahl zwischen ${\displaystyle 1}$ und ${\displaystyle n}$ genau eine Zahl im gleichen Bereich zuordnet. Stellt man sich alle ${\displaystyle n}$ Zahlen in einer Liste aneinandergereiht vor, dann nimmt die Zahl ${\displaystyle j\in \{1,\ldots ,n\}}$ durch die Permutation den Platz mit der Nummer ${\displaystyle \sigma (j)}$ ein.

Es gibt im Wesentlichen drei Arten zur Notation von Permutationen: die Matrixdarstellung, die Tupelschreibweise und die Zykelschreibweise.

In der ausführlichen Darstellung einer ${\displaystyle n}$-stelligen Permutation ${\displaystyle \sigma }$ schreibt man diese als Matrix mit zwei Zeilen und ${\displaystyle n}$ Spalten. In der oberen Zeile stehen die Zahlen von ${\displaystyle 1}$ bis ${\displaystyle n}$ (in beliebiger Reihenfolge). Unter jeder Zahl ${\displaystyle j\in \{1,\ldots ,n\}}$ steht dann in der zweiten Zeile der Funktionswert ${\displaystyle \sigma (j)}$:

${\displaystyle \sigma ={\begin{pmatrix}1&2&\cdots &n\\\sigma \left(1\right)&\sigma \left(2\right)&\cdots &\sigma \left(n\right)\end{pmatrix}}}$

Auch in der zweiten Zeile steht somit jede Zahl von ${\displaystyle 1}$ bis ${\displaystyle n}$ genau einmal.

Bei der kompakteren Tupelschreibweise schreibt man lediglich die Funktionswerte ${\displaystyle \sigma (j)}$ in eine Zeile:

${\displaystyle \sigma =\left(\sigma \left(1\right),\sigma \left(2\right),\dotsc ,\sigma \left(n\right)\right)}$

Diese Schreibweise verwendet somit lediglich die zweite Zeile der Matrixdarstellung. Da so die Information über die Zahl ${\displaystyle j}$, die auf ${\displaystyle \sigma (j)}$ abgebildet wird, verloren geht, kann die Tupelschreibweise nur verwendet werden, wenn die Reihenfolge der Zahlen in der ersten Zeile festgelegt wurde. In der Regel ist dies die natürliche Reihenfolge. Die Tupelschreibweise kann leicht mit der folgenden Zykelschreibweise verwechselt werden, besonders da manche Autoren die Kommata weglassen.

Die Zykelschreibweise benötigt ebenfalls nur eine Zeile. Man beginnt mit einer beliebigen Zahl ${\displaystyle a\in \{1,\ldots ,n\}}$ und schreibt

${\displaystyle \left(a\;\sigma (a)\;\sigma ^{2}(a)\;\cdots \;\sigma ^{\ell _{a}-1}(a)\right)}$,

wobei ${\displaystyle \sigma ^{k}}$ die ${\displaystyle k}$-fache Hintereinanderausführung von ${\displaystyle \sigma }$ bezeichnet und ${\displaystyle \ell _{a}}$ die kleinste natürliche Zahl mit ${\displaystyle \sigma ^{\ell _{a}}(a)=a}$ ist. Eine solche Klammer heißt Zyklus und ${\displaystyle \ell _{a}}$ ist seine Länge. Gibt es weitere Zahlen, die noch nicht notiert wurden, so wählt man eine solche Zahl ${\displaystyle b}$ und schreibt einen weiteren Zyklus ${\displaystyle (b\;\sigma (b)\;\cdots \;\sigma ^{\ell _{b}-1}(b))}$ der Länge ${\displaystyle \ell _{b}}$ dahinter. Man fährt so lange fort, bis jede Zahl genau einmal notiert wurde. Klammern, in denen nur eine Zahl steht, können anschließend wieder gestrichen werden. Diese Darstellung ist nicht eindeutig, denn die Reihenfolge der Zyklen ist beliebig wählbar und in jedem Zyklus dürfen die Zahlen zyklisch vertauscht werden.

Beispiel

Für die Permutation ${\displaystyle \sigma \colon \{1,2,3,4\}\rightarrow \{1,2,3,4\}}$, die durch ${\displaystyle \sigma (1)=2,\sigma (2)=4,\sigma (3)=3}$ und ${\displaystyle \sigma (4)=1}$ definiert ist, verwendet man die folgenden Schreibweisen:

• Matrixdarstellung:

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

• Tupelschreibweise:

${\displaystyle \sigma =(2,4,3,1)}$

• Zykelschreibweise:

${\displaystyle \sigma =(1~2~4)(3)=(1~2~4)=(2~4~1)=(4~1~2)}$

Der Graph einer ${\displaystyle n}$-stelligen Permutation ${\displaystyle \sigma }$ ist ein gerichteter Graph ${\displaystyle (V,E)}$ mit Knotenmenge ${\displaystyle V=\{1,2,\ldots ,n\}}$ und Kantenmenge

${\displaystyle E=\{(i,\sigma (i))\mid i=1,\ldots ,n\}}$.

In einem solchen Graphen besitzt jeder Knoten genau eine ausgehende und genau eine eingehende Kante. Die Zyklen des Graphen sind gerade die Zyklen der Permutation, wobei diejenigen Zahlen, die durch die Permutation festgehalten werden, Schleifen an den zugehörigen Knoten erzeugen. Der Graph einer Permutation ist nur dann zusammenhängend, wenn die Permutation aus einem einzelnen Zyklus der Länge ${\displaystyle n}$ besteht.

${\displaystyle {\begin{pmatrix}0&1&0&0\\0&0&0&1\\0&0&1&0\\1&0&0&0\\\end{pmatrix}}}$ Permutationsmatrix der Permutation ${\displaystyle \scriptstyle (1~2~4)(3)}$

Die Permutationsmatrix ${\displaystyle P_{\sigma }\in \mathbb {N} ^{n\times n}}$ einer ${\displaystyle n}$-stelligen Permutation ${\displaystyle \sigma }$ ist durch

${\displaystyle P_{\sigma }={\begin{pmatrix}p_{11}&\dots &p_{1n}\\\vdots &\ddots &\vdots \\p_{n1}&\dots &p_{nn}\end{pmatrix}}\quad {\text{ mit }}\quad p_{ij}={\begin{cases}1,&{\text{falls }}\sigma (i)=j\\0,&{\text{falls }}\sigma (i)\neq j\end{cases}}}$

definiert. Die Elemente eines Vektors ${\displaystyle x=(x_{1},x_{2},\dotsc ,x_{n})}$ werden in der linearen Algebra dadurch permutiert, dass der Vektor als Spaltenvektor von links mit der Permutationsmatrix ${\displaystyle P_{\sigma }}$ multipliziert wird:

${\displaystyle (x_{\sigma (1)},x_{\sigma (2)},\ldots ,x_{\sigma (n)})^{T}=P_{\sigma }\cdot x^{T}}$

Die Permutationen der Menge ${\displaystyle \{1,2,\dotsc ,n\}}$ bilden mit der Hintereinanderausführung als Verknüpfung eine Gruppe, die symmetrische Gruppe ${\displaystyle S_{n}}$. Die symmetrischen Gruppen spielen in der Mathematik eine bedeutende Rolle. Beispielsweise ist nach dem Satz von Cayley jede endliche Gruppe zu einer Untergruppe einer symmetrischen Gruppe isomorph. Die Untergruppen der symmetrischen Gruppe heißen Permutationsgruppen.

Zwei ${\displaystyle n}$-stellige Permutationen ${\displaystyle \sigma ,\tau \in S_{n}}$ lassen sich hintereinander ausführen, indem man zunächst die erste Permutation anwendet und auf das Resultat dann die zweite Permutation. Man schreibt die Hintereinderausführung als

${\displaystyle \tau \circ \sigma }$,

wobei erst ${\displaystyle \sigma }$ und dann ${\displaystyle \tau }$ angewandt wird. Diese Hintereinanderausführung wird auch Komposition, Verknüpfung oder Produkt zweier Permutationen genannt und ist selbst wieder eine ${\displaystyle n}$-stellige Permutation. Die Komposition von Permutationen ist allerdings nicht kommutativ, das heißt im Allgemeinen liefern ${\displaystyle \tau \circ \sigma }$ und ${\displaystyle \sigma \circ \tau }$ verschiedene Resultate. Die symmetrische Gruppe ${\displaystyle S_{n}}$ ist demnach für ${\displaystyle n>2}$ nicht abelsch. Allerdings ist die Komposition immer assoziativ, das heißt für alle Permutationen ${\displaystyle \sigma ,\tau ,\pi \in S_{n}}$ gilt

${\displaystyle \pi \circ (\tau \circ \sigma )=(\pi \circ \tau )\circ \sigma }$.

Beispiele

Es ist beispielsweise

${\displaystyle {\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}\circ {\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}}={\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}}$.

Um das Ergebnis zu erhalten wendet man die Permutationen von rechts nach links an und verfolgt den Weg der einzelnen Zahlen. Die ${\displaystyle 1}$ wird in der zweiten Permutation auf sich selbst abgebildet und in der ersten Permutation dann auf die ${\displaystyle 3}$, das heißt ${\displaystyle 1\mapsto 1\mapsto 3}$, insgesamt ${\displaystyle 1\mapsto 3}$. Der Weg der ${\displaystyle 2}$ ist entsprechend ${\displaystyle 2\mapsto 3\mapsto 2}$, also ${\displaystyle 2\mapsto 2}$. Die ${\displaystyle 3}$ geht schließlich den Weg ${\displaystyle 3\mapsto 2\mapsto 1}$, im Ergebnis ${\displaystyle 3\mapsto 1}$.

In der Zykeldarstellung geht man analog vor, wobei Zahlen, die nicht in einem Zyklus vorkommen, festgehalten werden. Beispielsweise ist

${\displaystyle (123)\circ (234)={\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}}=(12)(34)}$.

Hier ermittelt man die Wege ${\displaystyle 1\mapsto 1\mapsto 2}$, ${\displaystyle 2\mapsto 3\mapsto 1}$, ${\displaystyle 3\mapsto 4\mapsto 4}$ und ${\displaystyle 4\mapsto 2\mapsto 3}$.

Das neutrale Element der symmetrischen Gruppe ${\displaystyle S_{n}}$ ist die identische Permutation

${\displaystyle \operatorname {id} ={\begin{pmatrix}1&2&3&\ldots &n\\1&2&3&\ldots &n\end{pmatrix}}\in S_{n}}$,

also diejenige Permutation, die alle Zahlen an ihrem Platz belässt. Für jede Permutation ${\displaystyle \sigma \in S_{n}}$ gilt damit

${\displaystyle \operatorname {id} \circ \,\sigma =\sigma \circ \operatorname {id} =\sigma }$.

Die identische Permutation notiert man auch als leere Klammer ${\displaystyle ()}$, als ${\displaystyle (1)}$ oder als ${\displaystyle \epsilon }$.

Zu jeder Permutation ${\displaystyle \sigma \in S_{n}}$ gibt es genau ein inverses Element, die inverse Permutation ${\displaystyle \sigma ^{-1}}$, mit

${\displaystyle \sigma \circ \sigma ^{-1}=\sigma ^{-1}\circ \sigma =\operatorname {id} }$.

Die inverse Permutation erhält man, indem man in der Matrixschreibweise die obere mit der unteren Zeile vertauscht:

${\displaystyle \sigma ^{-1}={\begin{pmatrix}\sigma \left(1\right)&\sigma \left(2\right)&\cdots &\sigma \left(n\right)\\1&2&\cdots &n\end{pmatrix}}}$

In der Zykelschreibweise erhält man die inverse Permutation, indem man in jedem Zyklus die Zahlen in der umgekehrten Reihenfolge schreibt.

Beispiel

Die inverse Permutation zu

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5\\2&4&5&1&3\end{pmatrix}}=(124)(35)}$

ist

${\displaystyle \sigma ^{-1}={\begin{pmatrix}2&4&5&1&3\\1&2&3&4&5\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\4&1&5&2&3\end{pmatrix}}=(421)(53)}$.

${\displaystyle n}$	Typ	Zykelstruktur	Anzahl
${\displaystyle 1}$	${\displaystyle 1^{1}}$	${\displaystyle (\cdot )}$	${\displaystyle 1}$
${\displaystyle 2}$	${\displaystyle 1^{2}}$	${\displaystyle (\cdot )(\cdot )}$	${\displaystyle 1}$
	${\displaystyle 2^{1}}$	${\displaystyle (\cdot \;\,\cdot )}$	${\displaystyle 1}$
${\displaystyle 3}$	${\displaystyle 1^{3}}$	${\displaystyle (\cdot )(\cdot )(\cdot )}$	${\displaystyle 1}$
	${\displaystyle 1^{1}2^{1}}$	${\displaystyle (\cdot \;\,\cdot )(\cdot )}$	${\displaystyle 3}$
	${\displaystyle 3^{1}}$	${\displaystyle (\cdot \,\cdot \,\cdot )}$	${\displaystyle 2}$
${\displaystyle 4}$	${\displaystyle 1^{4}}$	${\displaystyle (\cdot )(\cdot )(\cdot )(\cdot )}$	${\displaystyle 1}$
	${\displaystyle 1^{2}2^{1}}$	${\displaystyle (\cdot \;\,\cdot )(\cdot )(\cdot )}$	${\displaystyle 6}$
	${\displaystyle 2^{2}}$	${\displaystyle (\cdot \;\,\cdot )(\cdot \;\,\cdot )}$	${\displaystyle 3}$
	${\displaystyle 1^{1}3^{1}}$	${\displaystyle (\cdot \;\cdot \;\cdot )(\cdot )}$	${\displaystyle 8}$
	${\displaystyle 4^{1}}$	${\displaystyle (\cdot \;\cdot \;\cdot \;\,\cdot )}$	${\displaystyle 6}$

Bezeichnet ${\displaystyle b_{j}}$ für ${\displaystyle j=1,\ldots ,n}$ die Anzahl der Zyklen der Länge ${\displaystyle j}$ in einer Permutation, dann ist der Typ dieser Permutation der formale Ausdruck

${\displaystyle 1^{b_{1}}2^{b_{2}}\ldots n^{b_{n}}}$,

wobei die Terme mit ${\displaystyle b_{j}=0}$ nicht aufgeführt werden müssen. Formal heißt hier, dass das Produkt und die Potenzen nicht tatsächlich ausgerechnet werden. Die Anzahl der möglichen Typen ${\displaystyle n}$-stelliger Permutationen entspricht gerade der Anzahl der Partitionen der Zahl ${\displaystyle n}$. Die Anzahl der Permutationen pro Typ kann aus der Typbeschreibung errechnet werden, wobei die Permutationen mit gleicher Zyklenzahl durch die Stirling-Zahlen erster Art gezählt werden. Die inverse Permutation weist immer den gleichen Typ wie die Ausgangspermutation auf. Zudem hat das Resultat der Komposition zweier Permutationen unabhängig von der Reihenfolge der Operanden ebenfalls den gleichen Typ. Zwei Permutationen sind demnach genau dann zueinander konjugiert, wenn sie vom gleichen Typ sind. Die Permutationen gleichen Typs bilden daher die Konjugationsklassen der symmetrischen Gruppe ${\displaystyle S_{n}}$.

Für jede Permutation ${\displaystyle \sigma }$ gibt es eine kleinste natürliche Zahl ${\displaystyle k}$ derart, dass die ${\displaystyle k}$-malige Hintereinanderausführung von ${\displaystyle \sigma }$ die Identität ergibt: ${\displaystyle \sigma ^{k}={\mbox{id}}}$. Diese Zahl wird Ordnung von ${\displaystyle \sigma }$ genannt. Sie ist die Elementordnung von ${\displaystyle \sigma }$ als Gruppenelement der symmetrischen Gruppe. Die Ordnung einer Permutation lässt sich leicht aus der Zykeldarstellung bestimmen: Sie ist das kleinste gemeinsame Vielfache (kgV) der Längen der disjunkten Zyklen von ${\displaystyle \sigma }$. Beispielsweise ist die Ordnung der Permutation ${\displaystyle (124)(35)}$ das kgV von ${\displaystyle 3}$ und ${\displaystyle 2}$, also ${\displaystyle 6}$.

Man nennt ein Paar ${\displaystyle (i,j)}$ von Zahlen Fehlstand oder Inversion bzgl. ${\displaystyle \sigma }$, falls gilt

${\displaystyle i<j}$ und ${\displaystyle \sigma \left(i\right)>\sigma \left(j\right)}$.

Zwei Zahlen bilden also genau dann einen Fehlstand, wenn nach Anwenden der Permutation die größere vor der kleineren steht. Ordnet man in einer Tabelle jeder Zahl die Anzahl derjenigen Zahlen zu, die nach der Permutation links von ihr stehen, obwohl sie größer sind, so erhält man die sogenannte Inversionstafel der Permutation. Umgekehrt kann man aus jeder solchen Tafel die Permutation eindeutig bestimmen. Fasst man die Einträge der Inversionstafel als Zahl in einem fakultätsbasierten Zahlensystem auf, lässt sich jeder Permutation ${\displaystyle \sigma \in S_{n}}$ eine eindeutige Nummer in der Menge ${\displaystyle \{0,\ldots ,n!-1\}}$ zuweisen. Sei mit ${\displaystyle i\left(\sigma \right)}$ die Anzahl der Fehlstände von ${\displaystyle \sigma }$ bezeichnet, dann ist das Signum von ${\displaystyle \sigma }$ gegeben durch

${\displaystyle \mathrm {sgn} \left(\sigma \right)=\left(-1\right)^{i\left(\sigma \right)}}$.

Eine Permutation hat also Signum 1, falls die Anzahl ihrer Fehlstände gerade ist, ansonsten Signum −1.

Interpretiert man die Permutationen der Menge ${\displaystyle \{1,\ldots ,n\}}$ als Koordinatenvektoren im ${\displaystyle n}$-dimensionalen Raum, dann bildet die konvexe Hülle dieser Punkte ein konvexes Polytop, das Permutaeder genannt wird. Zwei Permutationen sind dabei genau dann durch eine Kante des Permutaeders verbunden, wenn sie sich durch eine Transposition benachbarter Zahlen ineinander überführen lassen.

Eine Permutation, die ${\displaystyle k}$ Zahlen zyklisch vertauscht und die übrigen Zahlen fest lässt, heißt zyklische Permutation oder ${\displaystyle k}$-Zyklus und wird als ein einzelner Zyklus der Länge ${\displaystyle k}$ geschrieben. Ein ${\displaystyle 2}$-Zyklus, also eine Vertauschung zweier Zahlen, heißt auch Transposition. Die Verkettung zyklischer Permutationen ist kommutativ, wenn diese disjunkte Träger besitzen. Die Inverse einer zyklischen Permutation ist immer ebenfalls zyklisch, ebenso wie Potenzen einer zyklischen Permutation, deren Länge eine Primzahl ist. Jede zyklische Permutation kann in einzelne Transpositionen zerlegt werden und weist genau dann ein gerades Signum auf, wenn ihre Länge ungerade ist.

Zahlen, die durch eine Permutation festgehalten werden, nennt man Fixpunkte der Permutation. In der Matrixdarstellung erkennt man Fixpunkte daran, dass der obere und untere Eintrag der jeweiligen Spalte gleich ist. In der Zykelschreibweise sind Fixpunkte genau die Einerzyklen beziehungsweise die Zahlen, die nicht erscheinen. In der Permutationsmatrix sind die den Fixpunkten zugewiesenen Einträge der Hauptdiagonale ${\displaystyle 1}$. Eine fixpunktfreie Permutation hält keine der Zahlen fest und wird auch Derangement genannt. Die Anzahl der fixpunktfreien Permutationen der Zahlen von ${\displaystyle 1}$ bis ${\displaystyle n}$ kann durch die Subfakultät ${\displaystyle {!}n}$ berechnet werden. Für wachsendes ${\displaystyle n}$ strebt der Anteil der fixpunktfreien Permutationen sehr schnell gegen den Kehrwert der eulerschen Zahl ${\displaystyle e}$. Sollen in einer Permutation manche der Elemente an ihrem alten Platz verbleiben, spricht man von einem partiellen Derangement, deren Anzahl durch die Rencontres-Zahlen ermittelt werden kann.

Eine Permutation ${\displaystyle \sigma }$ mit ${\displaystyle \sigma ^{2}={\mbox{id}}}$ oder äquivalent dazu ${\displaystyle \sigma ^{-1}=\sigma }$ heißt Involution oder selbstinvers. Die Involutionen sind genau die Permutationen der Ordnung ${\displaystyle 2}$ sowie die Identität selbst (die einzige Permutation der Ordnung ${\displaystyle 1}$). Eine Permutation ist genau dann eine Involution, wenn ihre Zykeldarstellung maximal Zyklen der Länge ${\displaystyle 2}$, also Transpositionen, enthält.

Man nennt eine Permutation alternierend, wenn beim Durchlaufen dieser die Zahlen abwechselnd größer und kleiner als die jeweils vorangegangene Zahl sind. Formal heißt dies, dass für jede Zahl ${\displaystyle j\in \{2,\ldots ,n-1\}}$ entweder ${\displaystyle \sigma (j-1)<\sigma (j)>\sigma (j+1)}$ oder ${\displaystyle \sigma (j-1)>\sigma (j)<\sigma (j+1)}$ gilt.

• Permutiertes Register

• Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-9039-1. 
• Michael Artin: Algebra. Birkhäuser, 1998, ISBN 3-7643-5938-2. 
• Albrecht Beutelspacher: Lineare Algebra. 6. durchgesehene und ergänzte Auflage. Vieweg, 2003, ISBN 3-528-56508-X. 
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, ISBN 3-11-016727-1. 
• Hans Kurzweil, Bernd Stellmacher: Theorie der endlichen Gruppen: eine Einführung. Springer, 1998, ISBN 3-540-60331-X. 
• Kristina Reiss, Gernot Stroth: Endliche Strukturen. Springer, 2011, ISBN 3-642-17181-8. 

Wiktionary: Permutation – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Commons: Permutationen – Sammlung von Bildern, Videos und Audiodateien

• D.A. Suprunenko: Permutation of a set. In: Michiel Hazewinkel (Hrsg.): Encyclopedia of Mathematics. Springer-Verlag und EMS Press, Berlin 2002, ISBN 1-55608-010-7 (englisch, encyclopediaofmath.org). 
• alozano, Pedro Sanchez, Raymond Puzio, J. Pahikkala: Permutation. In: PlanetMath. (englisch)
• Eric W. Weisstein: Permutation. In: MathWorld (englisch).