Permutation

Alle 6 Permutationen dreier Kugeln

Unter einer Permutation (von lateinisch permutare vertauschen) versteht man in der abzählenden Kombinatorik eine Anordnung von Elementen einer Menge in einer bestimmten Reihenfolge. Je nachdem, ob die Elemente 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 wichtigsten Notationsvarianten für Permutationen sind die Matrixdarstellung, die Zykelschreibweise, die Tupelschreibweise und die Darstellung als Permutationsmatrizen. 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 ihre Ordnung, ihr Typ 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 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$ Elementen in einer bestimmten Reihenfolge. Sollen dabei weniger als $n$ Elemente ausgewählt werden, spricht man statt von einer Permutation von einer Variation, spielt die Reihenfolge bei der Auswahl keine Bedeutung von einer Kombination. 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 Elemente vertauschen.

Nun stellt sich die Frage nach der Anzahl möglicher Permutationen. Hierbei unterscheidet man den Fall, dass alle $n$ Elemente verschieden sind, von dem Fall, dass manche der Elemente gleich sind.

Permutationen ohne Wiederholung

Bei einer Permutation ohne Wiederholung sind alle $n$ Elemente unterscheidbar. Nachdem es für das erste Element $n$ Platzierungsmöglichkeiten gibt, kommen für das zweite Element nur noch $n-1$ Möglichkeiten in Betracht, für das dritte Element nur mehr $n-2$ und so weiter bis zum letzten Element, dem nur noch ein freier Platz bleibt. Die Anzahl der möglichen Permutationen von $n$ Elementen 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$ Elemente nicht unterscheidbar. Sind genau $k$ Elemente 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$ Elementen, von denen $k$ identisch sind, ist demnach durch

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

gegeben. Gibt es nicht nur eine, sondern $s$ Gruppen mit jeweils $k_{1},\ldots ,k_{s}$ identischen Elementen, so können all diese Elemente auf ihren Plätzen vertauscht werden, ohne dass sich neue Anordnungen ergeben. Zählt man auch die Elemente, 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

${\binom {n}{k_{1},\ldots ,k_{s}}}={\frac {n!}{k_{1}!\cdot \ldots \cdot 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 vier Arten zur Notation von Permutationen: die Matrixdarstellung, die Zykelschreibweise, die Tupelschreibweise und Permutationsmatrizen.

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.

Zykelschreibweise

Die Zykelschreibweise ist kompakter und benötigt 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 ein Zykel 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 Zykel $(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 Zykel ist beliebig wählbar und in jedem Zykel dürfen die Zahlen zyklisch vertauscht werden.

Tupelschreibweise

Bei der 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)$

Sie enthält somit nur noch die zweite Zeile der Matrixdarstellung. Da dadurch 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 wird leicht mit der Zykelschreibweise verwechselt, besonders da manche Autoren die Kommata weglassen.

Permutationsmatrix

→ Hauptartikel: Permutationsmatrix

Diese Darstellung ist nicht zu verwechseln mit der Matrixdarstellung. Bei dieser Darstellung wird der Vektor $(1,\dotsc ,n)$ von links mit einer Permutationsmatrix multipliziert, wodurch die Elemente des Vektors permutiert werden. Die Permutationsmatrix $P_{\sigma }\in \mathbb {N} ^{n\times n}$ zu einer Permutation $\sigma$ ist gegeben durch:

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

Der Vektor ${\bar {x}}={\begin{pmatrix}1\\\vdots \\n\\\end{pmatrix}}$ wird permutiert, indem man ihn von links mit $P_{\sigma }$ multipliziert: $P_{\sigma }\cdot {\begin{pmatrix}1\\\vdots \\n\\\end{pmatrix}}={\begin{pmatrix}\sigma (1)\\\vdots \\\sigma (n)\\\end{pmatrix}}$

Beispiel

Es sei $\sigma \colon \{1,2,3,4\}\rightarrow \{1,2,3,4\}$ durch $\sigma (1)=2,\sigma (2)=4,\sigma (3)=3$ und $\sigma (4)=1$ gegeben. Dann schreibt man

Matrixdarstellung:	$\sigma ={\begin{pmatrix}1&2&3&4\\2&4&3&1\end{pmatrix}}$
Zykelschreibweise:	$\sigma =(1~2~4)(3)=(1~2~4)=(2~4~1)=(4~1~2)$
Tupelschreibweise:	$\sigma =(2,4,3,1)$
Permutationsmatrix:	$P_{\sigma }\cdot {\overline {x}}={\begin{pmatrix}0&1&0&0\\0&0&0&1\\0&0&1&0\\1&0&0&0\\\end{pmatrix}}\cdot {\begin{pmatrix}1\\2\\3\\4\\\end{pmatrix}}={\begin{pmatrix}2\\4\\3\\1\\\end{pmatrix}}$

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 ist

$\tau \circ \sigma \neq \sigma \circ \tau$.

Die symmetrische Gruppe $S_{n}$ ist demnach für $n>2$ nicht abelsch. Die Reihenfolge kann nur unbeachtet bleiben, wenn zwei miteinander verknüpfte Zykel disjunkt sind, wenn also jede Zahl nur in einem Zykel vorkommt.

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 Zykel 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 Zykel 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

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 Zykeln von $\sigma$. Beispielsweise ist die Ordnung der Permutation $(124)(35)$ das kgV von $3$ und $2$, also $6$.

Typ

Sei mit $b_{i}$ die Anzahl der Zykel von $\sigma$ bezeichnet, welche die Länge $i$ haben. Dann ist der Typ einer Permutation der formale Ausdruck

$1^{b_{1}}2^{b_{2}}3^{b_{3}}\dotsm n^{b_{n}}.$

Formal bedeutet hierbei, dass das Produkt und die Potenzen nicht tatsächlich ausgerechnet werden. Die $n$-stelligen Permutationen gleichen Typs bilden Konjugationsklassen der symmetrischen Gruppe $S_{n}$.

Parität

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.

LR-Maximum

Bei einer Permutation in Wortschreibweise $a=a_{1}\dotso a_{i}\dotso a_{n}$ nennt man $a_{i}$ genau dann ein Links-Rechts-Maximum, kurz LR-Maximum, wenn $a_{i}>a_{j}$ mit $1\leq j\leq i-1$. Diese Eigenschaft ist von Nutzen, wenn man die normalisierte Zykeldarstellung ohne Klammern schreiben möchte. Man kann unter Ausnutzung der LR-Maxima zeigen, dass dann eine Bijektion zwischen der normalisierten Zykeldarstellung in eine Permutation existiert. Bemerkung: $a_{1}$ ist immer ein LR-Maximum.

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 Zykel der Länge $k$ geschrieben und $k$-Zykel genannt. Ein 2-Zykel, also eine Vertauschung zweier Zahlen, heißt auch Transposition. Jeder Zykel 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 Zykel 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

• Albrecht Beutelspacher: Lineare Algebra. 6. durchgesehene und ergänzte Auflage. Vieweg, Wiesbaden 2003, ISBN 3-528-56508-X, Kapitel 7.2 Permutationen. 
• Michael Artin: Algebra. Birkhäuser, Basel 1993, ISBN 3-7643-2927-0, Kapitel 1.4 Permutationsmatrizen. 

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