Permutation

Alle 6 Permutationen dreier Kugeln

Unter einer Permutation (von lateinisch permutare vertauschen) versteht man in der abzählenden 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 Referenzmenge meist die ersten natürlichen Zahlen verwendet werden. Die Menge der Permutationen der ersten $n$ natürlichen Zahlen bildet mit der Hintereinanderausführung als Verknüpfung eine Gruppe, die symmetrische Gruppe $S_{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).

Grundlagen

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

Problemstellung

Eine Permutation ist eine Anordnung von $n$ Objekten in einer bestimmten Reihenfolge. Alternativ kann eine Permutation auch als Umordnung der Objekte aus einer vorgegebenen Reihung angesehen werden. 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 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.

Sollen in der Anordnung weniger als $n$ Objekte ausgewählt werden, spricht man statt von einer Permutation von einer Variation, spielt die Reihenfolge bei der Auswahl keine Bedeutung von einer Kombination. Nun stellt sich die Frage nach der Anzahl möglicher Permutationen. Hierbei unterscheidet man den Fall, dass alle $n$ Objekte verschieden sind, von dem Fall, dass manche der Objekte identisch sind.

Permutationen ohne Wiederholung

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

$n!=n\cdot (n-1)\cdot \ldots \cdot 1$

angegeben.

Permutationen mit Wiederholung

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

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

gegeben. Gibt es nicht nur eine, sondern $s$ Gruppen mit jeweils $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 $1$, dann gilt $k_{1}+\ldots +k_{s}=n$ und die Anzahl der möglichen Permutationen wird durch den Multinomialkoeffizient

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

angeben.

Definition

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

$\sigma \colon X\rightarrow X$,

durch die jedem Element der Menge ein Element der gleichen Menge zugeordnet wird. Aufgrund der Bijektivität 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 $n$ natürlichen Zahlen als Referenzmenge beschränken. Eine Permutation ist dann eine bijektive Abbildung

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

die jeder natürlichen Zahl zwischen $1$ und $n$ eine Zahl im gleichen Bereich zuordnet, wobei verschiedene Zahlen auf verschiedene Zahlen abgebildet werden.

Notation

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

Matrixdarstellung

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

$\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 $1$ bis $n$ genau einmal.

Tupelschreibweise

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

$\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 $j$, die auf $\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.

Zykelschreibweise

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

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

wobei $\sigma ^{k}$ die $k$-fache Hintereinanderausführung von $\sigma$ bezeichnet und $\ell _{a}$ die kleinste natürliche Zahl mit $\sigma ^{\ell _{a}}(a)=a$ ist. Eine solche Klammer heißt Zyklus und $\ell _{a}$ ist seine Länge. Gibt es weitere Zahlen, die noch nicht notiert wurden, so wählt man eine solche Zahl $b$ und schreibt einen weiteren Zyklus $(b\;\sigma (b)\;\cdots \;\sigma ^{\ell _{b}-1}(b))$ der Länge $\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 $\sigma \colon \{1,2,3,4\}\rightarrow \{1,2,3,4\}$, die durch $\sigma (1)=2,\sigma (2)=4,\sigma (3)=3$ und $\sigma (4)=1$ definiert ist, verwendet man die folgenden Schreibweisen:

• Matrixdarstellung:

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

• Tupelschreibweise:

$\sigma =(2,4,3,1)$

• Zykelschreibweise:

$\sigma =(1~2~4)(3)=(1~2~4)=(2~4~1)=(4~1~2)$

Weitere Darstellungen

Graphdarstellung

Graph der Permutation $\scriptstyle (1~4~6~8~3~7)(2)(5)$

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

$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 $n$ besteht.

Permutationsmatrizen

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

→ Hauptartikel: Permutationsmatrix

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

$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 $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 $P_{\sigma }$ multipliziert wird:

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

Permutationen als Gruppe

Die Permutationen der Menge $\{1,2,\dotsc ,n\}$ bilden mit der Hintereinanderausführung als Verknüpfung eine Gruppe, die symmetrische Gruppe $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.

Komposition

Zwei $n$-stellige Permutationen $\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

$\tau \circ \sigma$,

wobei erst $\sigma$ und dann $\tau$ angewandt wird. Diese Hintereinanderausführung wird auch Komposition, Verknüpfung oder Produkt zweier Permutationen genannt und ist selbst wieder eine $n$-stellige Permutation. Die Komposition von Permutationen ist allerdings nicht kommutativ, das heißt im Allgemeinen liefern $\tau \circ \sigma$ und $\sigma \circ \tau$ verschiedene Resultate. Die symmetrische Gruppe $S_{n}$ ist demnach für $n>2$ nicht abelsch. Die Reihenfolge kann bei der Hintereinanderausführung nur unbeachtet bleiben, wenn zwei miteinander verknüpfte Zyklen disjunkt sind, wenn also jede Zahl nur in einem Zyklus vorkommt. Allerdings ist die Komposition immer assoziativ, das heißt für alle Permutationen $\sigma ,\tau ,\pi \in S_{n}$ gilt

$\pi \circ (\tau \circ \sigma )=(\pi \circ \tau )\circ \sigma$.

Beispiele

Es ist beispielsweise

${\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 $1$ wird in der zweiten Permutation auf sich selbst abgebildet und in der ersten Permutation dann auf die $3$, das heißt $1\mapsto 1\mapsto 3$, insgesamt $1\mapsto 3$. Der Weg der $2$ ist entsprechend $2\mapsto 3\mapsto 2$, also $2\mapsto 2$. Die $3$ geht schließlich den Weg $3\mapsto 2\mapsto 1$, im Ergebnis $3\mapsto 1$.

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

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

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

Identische Permutation

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

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

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

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

Inverse Permutation

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

$\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:

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

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

ist

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

Eigenschaften

Typ

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

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

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

wobei die Terme mit $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 $n$-stelliger Permutationen entspricht gerade der Anzahl der Partitionen der Zahl $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 $S_{n}$.

Ordnung

Für jede Permutation $\sigma$ gibt es eine kleinste natürliche Zahl $k$ derart, dass die $k$-malige Hintereinanderausführung von $\sigma$ die Identität ergibt: $\sigma ^{k}={\mbox{id}}$. Diese Zahl wird Ordnung von $\sigma$ genannt. Sie ist die Elementordnung von $\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 $\sigma$. Beispielsweise ist die Ordnung der Permutation $(124)(35)$ das kgV von $3$ und $2$, also $6$.

Vorzeichen

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

$i<j$ und $\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 $\sigma \in S_{n}$ eine eindeutige Nummer in der Menge $\{0,\ldots ,n!-1\}$ zuweisen. Sei mit $i\left(\sigma \right)$ die Anzahl der Fehlstände von $\sigma$ bezeichnet, dann ist das Signum von $\sigma$ gegeben durch

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

Geometrie

Interpretiert man die Permutationen der Menge $\{1,\ldots ,n\}$ als Koordinatenvektoren im $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.

Spezielle Permutationen

Zyklische Permutationen

→ Hauptartikel: Zyklische Permutation

Eine Permutation, die $k$ Zahlen zyklisch vertauscht und die übrigen Zahlen fest lässt, wird als ein einzelner Zyklus der Länge $k$ geschrieben und $k$-Zyklus genannt. Ein 2-Zyklus, also eine Vertauschung zweier Zahlen, heißt auch Transposition. Jeder Zyklus und damit auch jede Permutation lässt sich als Komposition von Transpositionen schreiben.

Fixpunktfreie Permutationen

→ Hauptartikel: Fixpunktfreie Permutation

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 bzw. die Zahlen, die nicht erscheinen. In der Permutationsmatrix sind die den Fixpunkten zugewiesenen Einträge der Hauptdiagonale 1.

Bei einer fixpunktfreien Permutation (auch Derangement genannt) bleibt keine Zahl auf ihrem Platz. Die Anzahl der fixpunktfreien Permutationen einer Menge mit $n$ Elementen kann durch die Subfakultät ${!}n$ berechnet werden. Allgemeiner lässt sich die Anzahl der Permutationen mit einer gegebenen Anzahl von Fixpunkten (sog. partielle Derangements) mit Hilfe der Rencontres-Zahlen bestimmen.

Selbstinverse Permutationen

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

Alternierende Permutationen

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 $j\in \{2,\ldots ,n-1\}$ entweder $\sigma (j-1)<\sigma (j)>\sigma (j+1)$ oder $\sigma (j-1)>\sigma (j)<\sigma (j+1)$ gilt.

Siehe auch

• Permutiertes Register

Literatur

• Martin Aigner: Diskrete Mathematik. Vieweg, 2006, ISBN 3-8348-9039-1. 
• Albrecht Beutelspacher: Lineare Algebra. 6. durchgesehene und ergänzte Auflage. Vieweg, 2003, ISBN 3-528-56508-X. 
• Michael Artin: Algebra. Birkhäuser, 1998, ISBN 3-7643-5938-2. 
• 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

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

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