Permutation

Unter e​iner Permutation (von lateinisch permutare ‚vertauschen‘) versteht m​an in d​er Kombinatorik e​ine Anordnung v​on Objekten i​n einer bestimmten Reihenfolge. Je nachdem, o​b manche Objekte mehrfach auftreten dürfen o​der nicht, spricht m​an von e​iner Permutation m​it Wiederholung o​der einer Permutation o​hne Wiederholung. Die Anzahl d​er Permutationen o​hne Wiederholung ergibt s​ich als Fakultät, während d​ie Anzahl d​er Permutationen m​it Wiederholung über Multinomialkoeffizienten angegeben wird.

Alle sechs Permutationen dreier farbiger Kugeln

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 Kenngrößen v​on Permutationen s​ind ihr Zykeltyp, i​hre Ordnung u​nd ihr Vorzeichen. Mit Hilfe d​er Fehlstände e​iner Permutation lässt s​ich auf d​er Menge d​er Permutationen fester Länge e​ine partielle Ordnung definieren. Über i​hre Inversionstafel k​ann zudem j​eder Permutation e​ine eindeutige Nummer i​n einem fakultätsbasierten Zahlensystem zugeordnet werden. Wichtige Klassen v​on Permutationen s​ind zyklische, fixpunktfreie, selbstinverse u​nd alternierende Permutationen.

Permutationen besitzen vielfältige Einsatzbereiche innerhalb u​nd außerhalb d​er Mathematik, beispielsweise i​n der linearen Algebra (Leibniz-Formel), d​er Analysis (Umordnung v​on Reihen), d​er Graphentheorie u​nd Spieltheorie, d​er Kryptographie (Verschlüsselungsverfahren), d​er Informatik (Sortierverfahren) u​nd der Quantenmechanik (Pauli-Prinzip).

Kombinatorische Grundlagen

Permutationen vier farbiger Kugeln ohne Wiederholung (links) und mit Wiederholung (mitte und rechts).

Problemstellung

Eine Permutation i​st eine Anordnung v​on Objekten i​n einer bestimmten Reihenfolge o​der eine Umordnung v​on Objekten a​us 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 ergibt eine (im Idealfall) zufällige Permutation der Karten.
• Im Volleyball ist der Stellungswechsel nach Eroberung des Aufschlagrechts 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 Rolle, 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.

Permutation ohne Wiederholung

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 (n-2)\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.

Permutation mit Wiederholung

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 Multinomialkoeffizienten

${\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.

Algorithmen

Zur systematischen Erzeugung a​ller Permutationen v​on n Elementen existieren e​ine Reihe v​on Algorithmen, d​ie sich o​ft gut rekursiv formulieren lassen. Dazu gehören u​nter anderem d​er Steinhaus-Johnson-Trotter-Algorithmus u​nd der Heap-Algorithmus.

Definition

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 \pi \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 \pi (x_{i})}$ ein. Aufgrund der Bijektivität der Abbildung werden dabei zwei verschiedene Elemente niemals auf das gleiche Element abgebildet. Der Fall ${\displaystyle n=0}$ ist ebenfalls zugelassen und ${\displaystyle X}$ ist dann die leere Menge.

Da per Definition jede endliche Menge zu einer Menge der Form {1, 2, ..., n} gleichmächtig ist, 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 \pi \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.[1] 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 \pi (j)}$ ein.

Notation

Zweizeilenform

In der ausführlichen Darstellung einer ${\displaystyle n}$-stelligen Permutation ${\displaystyle \pi }$ 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 \pi (j)}$:

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

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

Beispiel

Die Permutation ${\displaystyle \pi \colon \{1,2,3,4\}\rightarrow \{1,2,3,4\}}$ mit ${\displaystyle \pi (1)=2,\pi (2)=4,\pi (3)=3}$ und ${\displaystyle \pi (4)=1}$ wird in der Zweizeilenform durch

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

notiert.

Tupelschreibweise

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

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

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

Beispiel

Für d​ie obige Beispielpermutation erhält m​an die Tupelschreibweise

${\displaystyle \pi =(2,~4,~3,~1)}$.

Zyklenschreibweise

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

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

wobei ${\displaystyle \pi ^{k}}$ die ${\displaystyle k}$-fache Hintereinanderausführung von ${\displaystyle \pi }$ bezeichnet und ${\displaystyle \ell _{a}}$ die kleinste natürliche Zahl mit ${\displaystyle \pi ^{\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\;\pi (b)\;\cdots \;\pi ^{\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 d​ie obige Beispielpermutation verwendet m​an die folgenden Zyklenschreibweisen:

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

Weitere Darstellungen

Graphdarstellung

Graph der Permutation ${\displaystyle (1~2~4~3)(5)(6~7)}$

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

${\displaystyle E=\{(i,\pi (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.

Permutationsmatrizen

${\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 (2,4,3,1)}$

→ Hauptartikel: Permutationsmatrix

Die Permutationsmatrix ${\displaystyle P_{\pi }\in \{0,1\}^{n\times n}}$ einer ${\displaystyle n}$-stelligen Permutation ${\displaystyle \pi }$ wird durch

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

definiert, wobei ${\displaystyle \delta _{ij}}$ das Kronecker-Delta bezeichne. Wird durch eine Permutation die Zahl ${\displaystyle i}$ auf die Zahl ${\displaystyle \pi (i)}$ abgebildet, dann besitzt die zugehörige Permutationsmatrix in der ${\displaystyle i}$-ten Zeile eine ${\displaystyle 1}$ in der Spalte ${\displaystyle \pi (i)}$. Die Elemente eines Spaltenvektors ${\displaystyle (x_{1},\dotsc ,x_{n})^{T}}$ werden in der linearen Algebra dadurch permutiert, dass der Vektor von links mit der Permutationsmatrix ${\displaystyle P_{\pi }}$ multipliziert wird:

${\displaystyle (x_{\pi (1)},\ldots ,x_{\pi (n)})^{T}=P_{\pi }\cdot (x_{1},\dotsc ,x_{n})^{T}}$.

Permutationen als Gruppe

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.

Die Galoisgruppe i​n der (klassischen) Galoistheorie i​st solch e​ine Untergruppe d​er symmetrischen Gruppe: Permutiert werden d​abei die Nullstellen v​on Polynomen. Die Eigenschaften d​er Galoisgruppe g​eben Aufschluss über d​ie Auflösbarkeit e​iner Polynomgleichung d​urch Radikale, d. h. d​urch Wurzelausdrücke. Damit lässt s​ich zum Beispiel beweisen, d​ass die allgemeine Polynomgleichung fünften o​der höheren Grades n​icht durch Radikale auflösbar i​st (Satz v​on Abel-Ruffini).

Komposition

Zwei ${\displaystyle n}$-stellige Permutationen ${\displaystyle \pi ,\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 Hintereinanderausführung als

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

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

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

Beispiele

Es i​st 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 d​er Zyklendarstellung g​eht man analog vor, w​obei Zahlen, d​ie nicht i​n einem Zyklus vorkommen, festgehalten werden. Beispielsweise ist

${\displaystyle (1~2~3)\circ (2~3~4)={\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}}=(1~2)(3~4)}$.

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}$.

Identische Permutation

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 \pi \in S_{n}}$ gilt damit

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

Die identische Permutation notiert man auch als leere Klammer ${\displaystyle ()}$, als ${\displaystyle (1)}$ oder als ${\displaystyle \epsilon }$. Die Permutationsmatrix der identischen Permutation ist die Einheitsmatrix. Der Graph der identischen Permutation weist lediglich eine Schleife an jedem Knoten auf. Die identische Permutation der Länge eins wird auch als triviale Permutation bezeichnet.

Inverse Permutation

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

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

Die inverse Permutation erhält man, i​ndem man i​n der Zweizeilenform d​ie obere m​it der unteren Zeile vertauscht:

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

In d​er Zyklenschreibweise erhält m​an die inverse Permutation, i​ndem man i​n jedem Zyklus d​ie Zahlen i​n der umgekehrten Reihenfolge schreibt. In d​er Graphdarstellung d​er inversen Permutation werden lediglich d​ie Richtungen a​ller Kanten umgedreht. Die Permutationsmatrix d​er inversen Permutation i​st die transponierte Matrix d​er Ausgangspermutation.

Beispiel

Die inverse Permutation zu

${\displaystyle \pi ={\begin{pmatrix}1&2&3&4&5\\2&4&5&1&3\end{pmatrix}}=(1~2~4)(3~5)}$

ist

${\displaystyle \pi ^{-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}}=(4~2~1)(5~3)}$.

Konjugation

Zwei Permutationen ${\displaystyle \sigma ,\pi \in S_{n}}$ heißen zueinander konjugiert, wenn eine Permutation ${\displaystyle \tau \in S_{n}}$ existiert, sodass

${\displaystyle \sigma =\tau \circ \pi \circ \tau ^{-1}}$   bzw.   ${\displaystyle \sigma \circ \tau =\tau \circ \pi }$

gilt. Wird durch die Permutation ${\displaystyle \pi }$ die Zahl ${\displaystyle i}$ auf die Zahl ${\displaystyle j}$ abgebildet, dann bildet die Permutation ${\displaystyle \sigma }$ die Zahl ${\displaystyle \tau (i)}$ auf die Zahl ${\displaystyle \tau (j)}$ ab. Die Konjugation stellt eine Äquivalenzrelation ${\displaystyle \sim }$ auf der Menge der Permutationen fester Länge dar, das heißt, sie ist reflexiv (${\displaystyle \pi \sim \pi }$), symmetrisch (aus ${\displaystyle \pi \sim \sigma }$ folgt ${\displaystyle \sigma \sim \pi }$) und transitiv (aus ${\displaystyle \pi \sim \sigma }$ und ${\displaystyle \sigma \sim \tau }$ folgt ${\displaystyle \pi \sim \tau }$). Die Menge aller zu einer Permutation ${\displaystyle \pi \in S_{n}}$ konjugierten Permutationen bilden eine Äquivalenzklasse (die Konjugationsklasse), die durch ${\displaystyle \left[\pi \right]}$ notiert wird.

Beispiel

Die symmetrische Gruppe ${\displaystyle S_{3}}$ besitzt die drei Konjugationsklassen:

${\displaystyle [\operatorname {id} ]=\{\operatorname {id} \}}$

${\displaystyle [(1~2)]=\{(1~2),(1~3),(2~3)\}}$

${\displaystyle [(1~2~3)]=\{(1~2~3),(1~3~2)\}}$

Kenngrößen

Zykeltyp

${\displaystyle n}$	Zykeltyp	Zykelstruktur	Anzahl
1	1^1	( • )	1
2	1^2	( • ) ( • )	1
	2^1	( • • )	1
3	1^3	( • ) ( • ) ( • )	1
	1^1 2^1	( • • ) ( • )	3
	3^1	( • • • )	2
4	1^4	( • ) ( • ) ( • ) ( • )	1
	1^2 2^1	( • • ) ( • ) ( • )	6
	2^2	( • • ) ( • • )	3
	1^1 3^1	( • • • ) ( • )	8
	4^1	( • • • • )	6

→ Hauptartikel: Zykeltyp

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

${\displaystyle \operatorname {typ} (\pi )=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 Zykeltypen ${\displaystyle n}$-stelliger Permutationen entspricht gerade der Anzahl der Partitionen der Zahl ${\displaystyle n}$. Die Anzahl der Permutationen pro Zykeltyp kann aus der Typbeschreibung errechnet werden. Die inverse Permutation weist immer den gleichen Zykeltyp wie die Ausgangspermutation auf. Zudem hat das Resultat der Komposition zweier Permutationen unabhängig von der Reihenfolge der Operanden ebenfalls den gleichen Zykeltyp. Zwei Permutationen sind demnach genau dann zueinander konjugiert, wenn sie vom gleichen Zykeltyp sind. Die Permutationen gleichen Zykeltyps bilden daher die Konjugationsklassen der symmetrischen Gruppe ${\displaystyle S_{n}}$. Die Permutationen mit gleicher Zyklenzahl werden durch die Stirling-Zahlen erster Art gezählt.

Ordnung

→ Hauptartikel: Elementordnung

Die Ordnung einer Permutation ${\displaystyle \pi }$ ist die kleinste natürliche Zahl ${\displaystyle k}$ derart, dass die ${\displaystyle k}$-malige Hintereinanderausführung von ${\displaystyle \pi }$ die identische Permutation ergibt:

${\displaystyle \operatorname {ord} (\pi )=\min\{k\in \mathbb {N} \mid \pi ^{k}=\operatorname {id} \}}$.

Die Ordnung einer Permutation ${\displaystyle \pi }$ ist damit die Elementordnung von ${\displaystyle \pi }$ als Gruppenelement der symmetrischen Gruppe. Aus der Zyklendarstellung einer Permutation lässt sich die Ordnung als das kleinste gemeinsame Vielfache der Längen der disjunkten Zyklen ermitteln. Beispielsweise ist die Ordnung der Permutation ${\displaystyle (124)(35)}$ das kleinste gemeinsame Vielfache von drei und zwei, also sechs.

Fehlstände

Fehlstände der Permutationen in S₃

Nr.	Permutation	Fehlstände	Anzahl
0	(1,2,3)	–	0
1	(1,3,2)	(2,3)	1
2	(2,1,3)	(1,2)	1
3	(2,3,1)	(1,2),(1,3)	2
4	(3,1,2)	(1,3),(2,3)	2
5	(3,2,1)	(1,2),(1,3),(2,3)	3

→ Hauptartikel: Fehlstand

Man nennt ein Zahlenpaar ${\displaystyle (i,j)}$ Fehlstand oder Inversion einer Permutation ${\displaystyle \pi }$, falls ${\displaystyle i<j}$ und ${\displaystyle \pi (i)>\pi (j)}$ gilt. Zwei Zahlen bilden also genau dann einen Fehlstand, wenn nach Anwenden der Permutation die größere vor der kleineren steht. Die Menge der Fehlstände einer Permutation ${\displaystyle \pi \in S_{n}}$ ist damit durch

${\displaystyle \operatorname {inv} (\pi )=\left\{(i,j)\in \{1,\ldots ,n\}^{2}\mid i<j~{\text{und}}~\pi (i)>\pi (j)\right\}}$

gegeben. Die Anzahl der Fehlstände ${\displaystyle |\operatorname {inv} (\pi )|}$ einer Permutation heißt Fehlstandszahl oder Inversionszahl der Permutation. Die Fehlstandszahl kann als Maß für die Unordnung der durch die Permutation vertauschten Zahlen angesehen werden.

Vorzeichen

→ Hauptartikel: Vorzeichen (Permutation)

Das Vorzeichen oder Signum einer Permutation ${\displaystyle \pi \in S_{n}}$ ist die Zahl

${\displaystyle \operatorname {sgn} (\pi )=\left(-1\right)^{|\operatorname {inv} (\pi )|}}$.

Eine Permutation hat damit das Vorzeichen ${\displaystyle +1}$, falls ihre Fehlstandszahl gerade ist, ansonsten das Vorzeichen ${\displaystyle -1}$. Im ersten Fall spricht man von einer geraden und im zweiten Fall von einer ungeraden Permutation. Die Menge der geraden Permutationen bildet eine Untergruppe der symmetrischen Gruppe ${\displaystyle S_{n}}$, die alternierende Gruppe ${\displaystyle A_{n}}$.

Anstiege und Abstiege

Ein Anstieg in einer Permutation ${\displaystyle \pi \in S_{n}}$ ist eine Zahl ${\displaystyle i}$, für die ${\displaystyle \pi (i+1)>\pi (i)}$ gilt. Die Menge der Anstiege in einer Permutation ist damit durch

${\displaystyle \operatorname {asc} (\pi )=\left\{i\in \{1,\ldots ,n-1\}\mid \pi (i+1)>\pi (i)\right\}}$

gegeben. Entsprechend dazu gilt für einen Abstieg ${\displaystyle \pi (i+1)<\pi (i)}$. Die Anzahl der Permutationen in ${\displaystyle S_{n}}$ mit genau ${\displaystyle k}$ Anstiegen bzw. Abstiegen wird durch die Euler-Zahlen ${\displaystyle \textstyle \left\langle \!{n \atop k}\!\right\rangle }$ angegeben. Eine maximale, das heißt beidseitig nicht mehr verlängerbare Folge

${\displaystyle (\pi (i),\pi (i+1),\ldots ,\pi (i+l))}$

sukzessive steigender bzw. fallender Zahlen in einer Permutation wird ansteigender bzw. absteigender Lauf der Länge ${\displaystyle l+1}$ genannt. Für ${\displaystyle l=0}$ kann eine solche Folge auch nur aus einer Zahl bestehen. Weist eine Permutation insgesamt ${\displaystyle k}$ Anstiege bzw. Abstiege auf, so ist sie aus ${\displaystyle k+1}$ absteigenden bzw. ansteigenden Läufen zusammengesetzt. Demnach ist die Anzahl der Permutationen in ${\displaystyle S_{n}}$ mit genau ${\displaystyle k}$ ansteigenden bzw. absteigenden Läufen durch ${\displaystyle \textstyle \left\langle \!{n \atop k-1}\!\right\rangle }$ gegeben.

Ordnungseigenschaften

Anordnung

Hasse-Diagramm der Permutationen in S₄. Blaue, grüne und rote Kanten entsprechen den Nachbarvertauschungen (1 2), (2 3) und (3 4), die von unten nach oben gesehen immer genau einen Fehlstand erzeugen.

Mit Hilfe der Fehlstände lässt sich auf der Menge der ${\displaystyle n}$-stelligen Permutationen eine partielle Ordnung durch

${\displaystyle \pi \leq \tau \Leftrightarrow \operatorname {inv} (\pi )\subseteq \operatorname {inv} (\tau )}$,

definieren, wobei ${\displaystyle \pi ,\tau \in S_{n}}$ sind. Das minimale Element bezüglich dieser Ordnung ist die identische Permutation, während das maximale Element diejenige Permutation ist, die die Reihenfolge aller Zahlen umkehrt. In dem zugehörigen Hasse-Diagramm sind zwei Permutationen durch eine Kante verbunden, wenn sie durch eine Nachbarvertauschung auseinander hervorgehen. Die Knoten und Kanten des Hasse-Diagramms bilden einen Cayley-Graphen, der isomorph zum Kantengraphen des entsprechenden Permutaeders ist. Der Permutaeder ist ein konvexes Polytop im ${\displaystyle n}$-dimensionalen Raum, das daraus entsteht, dass die Permutationen der Menge ${\displaystyle \{1,\ldots ,n\}}$ als Koordinatenvektoren interpretiert werden und dann die konvexe Hülle dieser Punkte gebildet wird.

Aufzählung

Die Inversionstafel oder der Inversionsvektor einer Permutation ${\displaystyle \pi \in S_{n}}$ ordnet jeder Zahl ${\displaystyle 1\leq j\leq n}$ die Anzahl der Fehlstände zu, die sie erzeugt. Bezeichnet ${\displaystyle b_{j}}$ die Anzahl der Zahlen, die in der Tupeldarstellung von ${\displaystyle \pi }$ links von ${\displaystyle j}$ stehen und größer als ${\displaystyle j}$ sind, dann ist der Inversionsvektor einer Permutation durch

${\displaystyle I(\pi )=(b_{1},b_{2},\ldots ,b_{n})}$

gegeben. Aus dem Inversionsvektor ${\displaystyle I(\pi )}$ lässt sich umgekehrt die zugrundeliegende Permutation ${\displaystyle \pi }$ eindeutig ermitteln. Fasst man die Inversionsvektor als Zahl in einem fakultätsbasierten Zahlensystem auf, lässt sich jeder Permutation ${\displaystyle \pi \in S_{n}}$ eine eindeutige Nummer ${\displaystyle z(\pi )\in \{0,\ldots ,n!-1\}}$ durch

${\displaystyle z(\pi )=\sum _{i=1}^{n}b_{i}\cdot (n-i)!}$

zuweisen. Statt d​es Inversionsvektors w​ird auch d​er Lehmer-Code z​ur Nummerierung v​on Permutationen verwendet.

Symmetrien

Die zu einer Permutation ${\displaystyle \pi \in S_{n}}$ komplementäre Permutation ist

${\displaystyle \pi ^{-}=(n-\pi (1)+1,\ldots ,n-\pi (n)+1)}$.

Die komplementäre Permutation entsteht d​urch horizontale Spiegelung d​er Permutationsmatrix. Die reverse Permutation i​st entsprechend

${\displaystyle \pi '=(\pi (n),\pi (n-1),\ldots ,\pi (1))}$

und entsteht d​urch vertikale Spiegelung. Komplementäre u​nd reverse Permutationen besitzen s​ie den gleichen Zykeltyp u​nd die gleiche Ordnung w​ie die Ausgangspermutation. Die Zahl d​er An- u​nd Abstiege w​ird allerdings b​ei komplementären u​nd reversen Permutationen vertauscht. Außerdem k​ehrt sich d​as Vorzeichen b​ei komplementären Permutationen u​nd bei reversen Permutationen m​it Länge 2 modulo 4 o​der Länge 3 modulo 4 um. Die Inverse d​er komplementären Permutation i​st gleich d​er revertierten Inversen u​nd die Inverse d​er reversen Permutation i​st gleich d​er komplementären Inversen.

Spezielle Permutationen

Zyklische Permutationen

→ Hauptartikel: Zyklische Permutation

Graph einer zyklischen Permutation der Länge 6

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 (nicht disjunkte) Transpositionen zerlegt werden und weist genau dann ein gerades Vorzeichen auf, wenn ihre Länge ungerade ist.

Fixpunktfreie Permutationen

→ Hauptartikel: Fixpunktfreie Permutation

Graph einer fixpunktfreien Permutation der Zahlen von 1 bis 8

Zahlen, die durch eine Permutation festgehalten werden, nennt man Fixpunkte der Permutation. In der Zweizeilenform erkennt man Fixpunkte daran, dass der obere und untere Eintrag der jeweiligen Spalte gleich ist. In der Zyklenschreibweise 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.

Selbstinverse Permutationen

→ Hauptartikel: Selbstinverse Permutation

Graph einer selbstinversen Permutation der Zahlen von 1 bis 8

Eine Permutation ${\displaystyle \pi }$ mit ${\displaystyle \pi ^{2}={\mbox{id}}}$ oder äquivalent dazu ${\displaystyle \pi ^{-1}=\pi }$ heißt Involution oder selbstinvers. Die Involutionen sind genau die Permutationen der Ordnung zwei sowie die Identität selbst (die einzige Permutation der Ordnung eins). Eine Permutation ist genau dann eine Involution, wenn ihre Zyklendarstellung maximal Zyklen der Länge zwei, also Transpositionen, enthält. Die Permutationsmatrix einer selbstinversen Permutation ist immer symmetrisch. Selbstinverse Permutationen spielen in der Kryptographie eine wichtige Rolle, wird nämlich eine Nachricht mit Hilfe einer selbstinversen Permutation verschlüsselt, dann lässt sich die Nachricht mittels der gleichen Permutation auch wieder entschlüsseln.

Ein Beispiel für e​ine selbstinverse Permutation i​st die Spiegelung

${\displaystyle \sigma _{n}={\begin{pmatrix}1&2&\cdots &n\\n&n-1&\cdots &1\end{pmatrix}}=(1~n)(2~(n-1))(3~(n-2))\cdots }$,

siehe a​uch Wort (Theoretische Informatik) §Spiegelung u​nd Palindrom.

Alternierende Permutationen

→ Hauptartikel: Alternierende Permutation

Man nennt eine Permutation alternierend, wenn in ihrer Tupeldarstellung keine Zahl ${\displaystyle \pi (j)}$ von ihrer Größe her zwischen der vorangehenden Zahl ${\displaystyle \pi (j-1)}$ und der nachfolgenden Zahl ${\displaystyle \pi (j+1)}$ steht. In einer alternierenden Permutation sind demnach die durch die Permutation vertauschten Zahlen immer abwechselnd größer und kleiner als die jeweils vorangegangene Zahl. Beginnt die Folge der Zahlen mit einem Anstieg, so spricht man von einer Up-Down-Permutation, beginnt sie mit einem Abstieg von einer Down-Up-Permutation. Jede alternierende Permutation ungerader Länge entspricht einem vollen partiell geordneten Binärbaum und jede alternierende Permutation gerader Länge einem fast vollen solchen Baum. Die Anzahlen der alternierenden Permutationen fester Länge treten als Koeffizienten in der Maclaurin-Reihe der Sekans- und der Tangensfunktion auf und stehen in engem Zusammenhang mit den Euler- und den Bernoulli-Zahlen.

Separable Permutationen

→ Hauptartikel: Separable Permutation

Separable Permutationen s​ind Permutationen, d​ie sich a​ls direkte o​der schiefe Summe trivialer Permutationen darstellen lassen. Eine solche Summe zweier Permutationen ergibt e​ine neue Permutation, d​eren Länge d​ie Summe d​er Längen d​er beiden Ausgangspermutationen ist. Bei e​iner direkten Summe w​ird dabei d​ie zweite Permutation verschoben a​n die e​rste angehängt, b​ei einer schiefen Summe d​ie erste Permutation verschoben d​er zweiten vorangestellt. Die Anzahl separabler Permutationen fester Länge w​ird durch d​ie Schröder-Zahlen angegeben. Separable Permutationen zeichnen s​ich durch e​ine spezielle rekursive Blockstruktur d​er zugehörigen Permutationsmatrizen aus. Sie werden u​nter anderem i​n der Sortierungstheorie untersucht.

Zufällige Permutationen

→ Hauptartikel: Zufällige Permutation

Eine zufällige Permutation ist eine aus der Menge der Permutationen ${\displaystyle S_{n}}$ zufällig ausgewählte Permutation. In der Stochastik werden zufällige Permutationen als Zufallsvariablen aus einem diskreten Wahrscheinlichkeitsraum angesehen. So können auch Kennzahlen zufälliger Permutationen, wie die Anzahl der Fixpunkte, Fehlstände oder Zyklen, als diskrete Zufallsvariablen angesehen werden, deren Wahrscheinlichkeitsverteilungen dann untersucht werden. Im Computer können zufällige Permutationen effizient mit dem Fisher-Yates-Verfahren generiert werden. Zufällige Permutationen werden unter anderem bei der Analyse von Sortierverfahren, in der Kryptographie und Kodierungstheorie sowie im Rahmen randomisierter Algorithmen untersucht. Das Problem der 100 Gefangenen ist ein mathematisches Rätsel, das auf zufälligen Permutationen basiert.

Permutation in der Musik

Permutationen der Lulu-Reihe (Alban Berg)

Über Permutation i​n der Fugenkomposition s​iehe unter Fuge.

In d​er Zwölftontechnik bezeichnet m​an als Permutation d​ie Ableitung weiterer Reihen a​us einer Zwölftonreihe dadurch, d​ass nach e​inem bestimmten numerischen Auswahlmodus nacheinander einzelne Töne herausgenommen werden s​o lange, b​is jeweils e​ine neue vollständige Zwölftonreihe entstanden ist.[2] So verfährt Alban Berg i​n seiner Oper Lulu.

Anmerkungen

1. Als bijektive Abbildung gelegentlich auch

   ${\displaystyle \pi \colon \{1,2,\ldots ,n\}\operatorname {\twoheadrightarrow \!\!\!\!\!\!\!\!\!\!\;\;\rightarrowtail } \;\{1,2,\ldots ,n\}}$

   geschrieben, siehe Funktion (Mathematik) §Symbolik.
2. Horst Weber: Artikel Permutation, in: Das große Lexikon der Musik, herausgegeben von Marc Honnegger und Günter Massenkeil, Herder Verlag Freiburg/Brsg. 1978 / 1987, Band 6, ISBN 3-451-20948-9, S. 243f

Literatur

• 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.

Weblinks

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