Permutation

Alle sechs Permutationen dreier verschiedenfarbiger Kugeln

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 $n$ natürlichen Zahlen bildet mit der Hintereinanderausführung als Verknüpfung die symmetrische Gruppe vom Grad $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 von Permutationen sind ihr Zykeltyp, ihre Ordnung und ihr Vorzeichen. Mit Hilfe der Fehlstände einer Permutation lässt sich auf der Menge der Permutationen fester Länge eine partielle Ordnung definieren. Über ihre Inversionstafel kann zudem jeder Permutation eine eindeutige Nummer in einem fakultätsbasierten Zahlensystem zugeordnet werden. Wichtige Klassen von Permutationen sind zyklische, fixpunktfreie, selbstinverse und alternierende Permutationen.

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

Kombinatorische Grundlagen

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

Problemstellung

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 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 $n$ Objekten, die alle unterscheidbar sind. 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 (n-2)\cdot \ldots \cdot 1

angegeben.

Beispielsweise gibt es $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 $n$ Objekten, von denen manche nicht unterscheidbar sind. 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 $(n\!-\!k)$ -te 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 Multinomialkoeffizienten

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

angeben.

Beispielsweise gibt es ${\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 ${\tfrac {4!}{2!\,2!}}={\tfrac {24}{4}}=6$ mögliche Anordnungen, wenn jeweils zwei Kugeln gleichfarbig sind.

Algorithmen

Zur systematischen Erzeugung aller Permutationen von n Elementen existieren eine Reihe von Algorithmen, die sich oft gut rekursiv formulieren lassen. Dazu gehören unter anderem der Steinhaus-Johnson-Trotter-Algorithmus und der Heap-Algorithmus.

Definition

Sei $X=\{x_{1},x_{2},\ldots ,x_{n}\}$ eine Menge mit $n$ Elementen, dann ist eine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stellige Permutation (ohne Wiederholung) eine bijektive Abbildung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \colon X \rightarrow X} ,

die jedem Element der Menge ein Element der gleichen Menge zuordnet. Anschaulich nimmt durch die Permutation jedes Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i=1, \ldots , n} den Platz des ihm zugeordneten Elements Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(x_i)} ein. Aufgrund der Bijektivität der Abbildung werden dabei zwei verschiedene Elemente niemals auf das gleiche Element abgebildet. Der Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=0} ist ebenfalls zugelassen und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} natürlichen Zahlen als Referenzmenge beschränken. Eine Permutation ist dann eine bijektive Abbildung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \colon \{ 1, 2, \ldots , n \} \rightarrow \{ 1, 2, \ldots , n \}} ,

die jeder natürlichen Zahl zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} genau eine Zahl im gleichen Bereich zuordnet.^[1] Stellt man sich alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Zahlen in einer Liste aneinandergereiht vor, dann nimmt die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j \in \{ 1, \ldots , n \}} durch die Permutation den Platz mit der Nummer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(j)} ein.

Notation

Zweizeilenform

In der ausführlichen Darstellung einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stelligen Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} schreibt man diese als Matrix mit zwei Zeilen und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Spalten. In der oberen Zeile stehen die Zahlen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} (in beliebiger Reihenfolge). Unter jeder Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j \in \{ 1, \ldots , n \}} steht dann in der zweiten Zeile der Funktionswert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(j)} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} genau einmal.

Beispiel

Die Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \colon \{1, 2, 3, 4 \} \rightarrow \{1, 2, 3, 4 \}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(1)=2, \pi(2)=4, \pi(3)=3} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(4)=1} wird in der Zweizeilenform durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(j)} in eine Zeile:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} , die auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 die obige Beispielpermutation erhält man die Tupelschreibweise

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi = (2, ~ 4, ~ 3, ~ 1)} .

Zyklenschreibweise

Die Zyklenschreibweise benötigt ebenfalls nur eine Zeile. Man beginnt mit einer beliebigen Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\in \{ 1, \ldots , n \}} und schreibt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(a \; \pi(a) \; \pi^2(a) \; \cdots \; \pi^{\ell_a-1}(a)\right)} ,

wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^k} die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -fache Hintereinanderausführung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} bezeichnet und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ell_a} die kleinste natürliche Zahl mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{\ell_a}(a) = a} ist. Eine solche Klammer heißt Zyklus und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \ell_a} ist seine Länge. Gibt es weitere Zahlen, die noch nicht notiert wurden, so wählt man eine solche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} und schreibt einen weiteren Zyklus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (b \; \pi(b) \; \cdots \; \pi^{\ell_b-1}(b))} der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 obige Beispielpermutation verwendet man die folgenden Zyklenschreibweisen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi = (1 ~ 2 ~ 4)(3) = (1 ~ 2 ~ 4) = (2 ~ 4 ~ 1) = (4 ~ 1 ~ 2)}

Weitere Darstellungen

Graphdarstellung

Graph der Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (1 ~ 2 ~ 4 ~ 3)(5)(6 ~ 7)}

Der Graph einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stelligen Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} ist ein gerichteter Graph Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (V,E)} mit Knotenmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V = \{ 1, 2, \ldots , n \}} und Kantenmenge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} besteht.

Permutationsmatrizen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\\ \end{pmatrix}}

Permutationsmatrix der Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (2,4,3,1)}

Die Permutationsmatrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_\pi \in \{0,1\}^{n\times n}} einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stelligen Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} wird durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta_{ij}} das Kronecker-Delta bezeichne. Wird durch eine Permutation die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} auf die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(i)} abgebildet, dann besitzt die zugehörige Permutationsmatrix in der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -ten Zeile eine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} in der Spalte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(i)} . Die Elemente eines Spaltenvektors Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x_1, \dotsc, x_n)^T} werden in der linearen Algebra dadurch permutiert, dass der Vektor von links mit der Permutationsmatrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P_\pi} multipliziert wird:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{ 1, 2, \dotsc, n \}} bilden mit der Hintereinanderausführung als Verknüpfung eine Gruppe, die symmetrische Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 in der (klassischen) Galoistheorie ist solch eine Untergruppe der symmetrischen Gruppe: Permutiert werden dabei die Nullstellen von Polynomen. Die Eigenschaften der Galoisgruppe geben Aufschluss über die Auflösbarkeit einer Polynomgleichung durch Radikale, d. h. durch Wurzelausdrücke. Damit lässt sich zum Beispiel beweisen, dass die allgemeine Polynomgleichung fünften oder höheren Grades nicht durch Radikale auflösbar ist (Satz von Abel-Ruffini).

Komposition

Zwei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stellige Permutationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau \circ \pi} ,

wobei erst Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} und dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau} angewandt wird. Diese Hintereinanderausführung wird auch Komposition, Verknüpfung oder Produkt zweier Permutationen genannt und das Ergebnis ist wieder eine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stellige Permutation. Die Komposition von Permutationen ist nicht kommutativ, das heißt im Allgemeinen liefern Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau \circ \pi} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \circ \tau} verschiedene Resultate. Die symmetrische Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} ist demnach für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n > 2} nicht abelsch. Allerdings ist die Komposition assoziativ, das heißt für alle Permutationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi, \tau, \sigma \in S_n} gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma \circ (\tau \circ \pi) = (\sigma \circ \tau) \circ \pi} .

Beispiele

Es ist beispielsweise

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} wird in der zweiten Permutation auf sich selbst abgebildet und in der ersten Permutation dann auf die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3} , das heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \mapsto 1 \mapsto 3} , insgesamt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \mapsto 3} . Der Weg der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2} ist entsprechend Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 \mapsto 3 \mapsto 2} , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 \mapsto 2} . Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3} geht schließlich den Weg Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3 \mapsto 2 \mapsto 1} , im Ergebnis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3 \mapsto 1} .

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \mapsto 1 \mapsto 2} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 \mapsto 3 \mapsto 1} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3 \mapsto 4 \mapsto 4} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4 \mapsto 2 \mapsto 3} .

Identische Permutation

Das neutrale Element der symmetrischen Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} ist die identische Permutation

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} gilt damit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{id} \circ \, \pi = \pi \circ \operatorname{id} = \pi} .

Die identische Permutation notiert man auch als leere Klammer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ()} , als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (1)} oder als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} gibt es genau ein inverses Element, die inverse Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^{-1}} , mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \circ \pi^{-1} = \pi^{-1} \circ \pi = \operatorname{id}} .

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 der Zyklenschreibweise erhält man die inverse Permutation, indem man in jedem Zyklus die Zahlen in der umgekehrten Reihenfolge schreibt. In der Graphdarstellung der inversen Permutation werden lediglich die Richtungen aller Kanten umgedreht. Die Permutationsmatrix der inversen Permutation ist die transponierte Matrix der Ausgangspermutation.

Beispiel

Die inverse Permutation zu

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 5 & 1 & 3 \end{pmatrix} = (1 ~ 2 ~ 4)(3 ~ 5)}

ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma, \pi \in S_n} heißen zueinander konjugiert, wenn eine Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau \in S_n} existiert, sodass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma = \tau \circ \pi \circ \tau^{-1}} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma \circ \tau = \tau \circ \pi}

gilt. Wird durch die Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} auf die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} abgebildet, dann bildet die Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma} die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau(i)} auf die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau(j)} ab. Die Konjugation stellt eine Äquivalenzrelation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sim} auf der Menge der Permutationen fester Länge dar, das heißt, sie ist reflexiv (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \sim \pi} ), symmetrisch (aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \sim \sigma} folgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma \sim \pi} ) und transitiv (aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \sim \sigma} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma \sim \tau} folgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \sim \tau} ). Die Menge aller zu einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} konjugierten Permutationen bilden eine Äquivalenzklasse (die Konjugationsklasse), die durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left[ \pi \right]} notiert wird.

Beispiel

Die symmetrische Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3} besitzt die drei Konjugationsklassen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [ \operatorname{id} ] = \{ \operatorname{id} \}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [ ( 1 ~ 2 ) ] = \{ (1 ~ 2),(1 ~ 3),(2 ~ 3) \}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [ ( 1 ~ 2 ~ 3 ) ] = \{ (1 ~ 2 ~ 3),(1 ~ 3 ~ 2) \}}

Kenngrößen

Zykeltyp

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n}	Zykeltyp	Zykelstruktur	Anzahl
1	1¹	( • )	1
2	1²	( • ) ( • )	1
2	2¹	( • • )	1
3	1³	( • ) ( • ) ( • )	1
	1¹ 2¹	( • • ) ( • )	3
	3¹	( • • • )	2
4	1⁴	( • ) ( • ) ( • ) ( • )	1
	1² 2¹	( • • ) ( • ) ( • )	6
	2²	( • • ) ( • • )	3
	1¹ 3¹	( • • • ) ( • )	8
	4¹	( • • • • )	6

Bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j=1, \ldots , n} die Anzahl der Zyklen der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} in einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} , dann ist der Zykeltyp dieser Permutation der formale Ausdruck

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{typ}(\pi) = 1^{b_1} 2^{b_2} \ldots n^{b_n}} ,

wobei die Terme mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stelliger Permutationen entspricht gerade der Anzahl der Partitionen der Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} . Die Permutationen mit gleicher Zyklenzahl werden durch die Stirling-Zahlen erster Art gezählt.

Ordnung

Die Ordnung einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} ist die kleinste natürliche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} derart, dass die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -malige Hintereinanderausführung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} die identische Permutation ergibt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{ord}(\pi) = \min \{k \in \N \mid \pi^k = \operatorname{id} \}} .

Die Ordnung einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} ist damit die Elementordnung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (1 2 4)(3 5)} das kleinste gemeinsame Vielfache von drei und zwei, also sechs.

Fehlstände

Fehlstände der Permutationen in S₃
Nr.	Permutation	Fehlstände	Anzahl
0	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}}	–	0
1	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}}	(2,3)	1
2	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3\end{pmatrix}}	(1,2)	1
3	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix}}	(1,3),(2,3)	2
4	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2\end{pmatrix}}	(1,2),(1,3)	2
5	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix}}	(1,2),(1,3),(2,3)	3

Man nennt ein Zahlenpaar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (i,j)} Fehlstand oder Inversion einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} , falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i < j} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} ist damit durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Das Vorzeichen oder Signum einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} ist die Zahl

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{sgn}(\pi) = \left(-1\right)^{|\operatorname{inv}(\pi)|}} .

Eine Permutation hat damit das Vorzeichen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle +1} , falls ihre Fehlstandszahl gerade ist, ansonsten das Vorzeichen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} , die alternierende Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_n} .

Anstiege und Abstiege

Ein Anstieg in einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} ist eine Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} , für die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(i+1) > \pi(i)} gilt. Die Menge der Anstiege in einer Permutation ist damit durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(i+1) < \pi(i)} . Die Anzahl der Permutationen in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} mit genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Anstiegen bzw. Abstiegen wird durch die Euler-Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textstyle \left\langle\! {n \atop k} \!\right\rangle} angegeben. Eine maximale, das heißt beidseitig nicht mehr verlängerbare Folge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l+1} genannt. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l=0} kann eine solche Folge auch nur aus einer Zahl bestehen. Weist eine Permutation insgesamt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Anstiege bzw. Abstiege auf, so ist sie aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k+1} absteigenden bzw. ansteigenden Läufen zusammengesetzt. Demnach ist die Anzahl der Permutationen in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} mit genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} ansteigenden bzw. absteigenden Läufen durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -stelligen Permutationen eine partielle Ordnung durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \leq \tau \Leftrightarrow \operatorname{inv}(\pi) \subseteq \operatorname{inv}(\tau)} ,

definieren, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -dimensionalen Raum, das daraus entsteht, dass die Permutationen der Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} ordnet jeder Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \leq j \leq n} die Anzahl der Fehlstände zu, die sie erzeugt. Bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j} die Anzahl der Zahlen, die in der Tupeldarstellung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} links von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} stehen und größer als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} sind, dann ist der Inversionsvektor einer Permutation durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I(\pi) = (b_1, b_2, \ldots , b_n )}

gegeben. Aus dem Inversionsvektor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I(\pi)} lässt sich umgekehrt die zugrundeliegende Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} eindeutig ermitteln. Fasst man die Inversionsvektor als Zahl in einem fakultätsbasierten Zahlensystem auf, lässt sich jeder Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} eine eindeutige Nummer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z(\pi) \in \{ 0 , \ldots , n!-1 \}} durch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z(\pi) = \sum_{i=1}^n b_i \cdot (n-i)!}

zuweisen. Statt des Inversionsvektors wird auch der Lehmer-Code zur Nummerierung von Permutationen verwendet.

Symmetrien

Die zu einer Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \in S_n} komplementäre Permutation ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^- = (n-\pi(1)+1, \ldots , n-\pi(n)+1)} .

Die komplementäre Permutation entsteht durch horizontale Spiegelung der Permutationsmatrix. Die reverse Permutation ist entsprechend

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi' = (\pi(n), \pi(n-1), \ldots , \pi(1))}

und entsteht durch vertikale Spiegelung. Komplementäre und reverse Permutationen besitzen den gleichen Zykeltyp und die gleiche Ordnung wie die Ausgangspermutation. Die Zahl der An- und Abstiege wird allerdings bei komplementären und reversen Permutationen vertauscht. Außerdem kehrt sich das Vorzeichen bei komplementären Permutationen und bei reversen Permutationen mit Länge 2 modulo 4 oder Länge 3 modulo 4 um. Die Inverse der komplementären Permutation ist gleich der revertierten Inversen und die Inverse der reversen Permutation ist gleich der komplementären Inversen.

Spezielle Permutationen

Zyklische Permutationen

Graph einer zyklischen Permutation der Länge 6

Eine Permutation, die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} Zahlen zyklisch vertauscht und die übrigen Zahlen fest lässt, heißt zyklische Permutation oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Zyklus und wird als ein einzelner Zyklus der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} geschrieben. Ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} . Eine fixpunktfreie Permutation hält keine der Zahlen fest und wird auch Derangement genannt. Die Anzahl der fixpunktfreien Permutationen der Zahlen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} kann durch die Subfakultät Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {!}n} berechnet werden. Für wachsendes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} strebt der Anteil der fixpunktfreien Permutationen sehr schnell gegen den Kehrwert der eulerschen Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Graph einer selbstinversen Permutation der Zahlen von 1 bis 8

Eine Permutation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi^2 = \mbox{id}} oder äquivalent dazu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 eine selbstinverse Permutation ist die Spiegelung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 auch Wort (Theoretische Informatik) §Spiegelung und Palindrom.

Alternierende Permutationen

Man nennt eine Permutation alternierend, wenn in ihrer Tupeldarstellung keine Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(j)} von ihrer Größe her zwischen der vorangehenden Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi(j-1)} und der nachfolgenden Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Separable Permutationen sind Permutationen, die sich als direkte oder schiefe Summe trivialer Permutationen darstellen lassen. Eine solche Summe zweier Permutationen ergibt eine neue Permutation, deren Länge die Summe der Längen der beiden Ausgangspermutationen ist. Bei einer direkten Summe wird dabei die zweite Permutation verschoben an die erste angehängt, bei einer schiefen Summe die erste Permutation verschoben der zweiten vorangestellt. Die Anzahl separabler Permutationen fester Länge wird durch die Schröder-Zahlen angegeben. Separable Permutationen zeichnen sich durch eine spezielle rekursive Blockstruktur der zugehörigen Permutationsmatrizen aus. Sie werden unter anderem in der Sortierungstheorie untersucht.

Zufällige Permutationen

Eine zufällige Permutation ist eine aus der Menge der Permutationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Alle Permutationen von n Objekten

Heap-Algorithmus

Polardiagramm aller Permutationen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=4} erzeugt durch den Heap-Algorithmus, bei dem jede Permutation farbcodiert ist (1 = blau, 2 = grün, 3 = gelb, 4 = rot)

Der Heap-Algorithmus generiert alle möglichen Permutationen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Objekten. Es wurde erstmals 1963 von B.R. Heap vorgeschlagen.^[2] Der Algorithmus minimiert die Anzahl der Bewegungen der Elemente: Er generiert jede Permutation aus der vorherigen, indem er ein einzelnes Elementpaar austauscht. Die anderen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n - 2} Elemente werden nicht verändert. Bei einer Überprüfung von Algorithmen zur Erzeugung von Permutationen im Jahr 1977 kam Robert Sedgewick zu dem Schluss, dass dies zu dieser Zeit der effektivste Algorithmus zur Erzeugung von Permutationen per Computer war.^[3]

Die durch den Heap-Algorithmus erzeugte Folge von Permutationen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Objekten ist der Anfang der Folge von Permutationen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n + 1} Objekten. Es gibt also eine unendliche Folge von Permutationen, die vom Heap-Algorithmus erzeugt werden (Folge A280318 in OEIS).

Steinhaus-Johnson-Trotter-Algorithmus

Polardiagramm aller Permutationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 4} generiert durch den Steinhaus-Johnson-Trotter-Algorithmus, bei dem jede Permutation farbcodiert ist (1 = blau, 2 = grün, 3 = gelb, 4 = rot)

Der Steinhaus-Johnson-Trotter-Algorithmus ist ein Algorithmus, der nach Hugo Steinhaus, Selmer M. Johnson und Hale Trotter benannt ist und alle Permutationen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Elementen erzeugt. Jede Permutation in der von ihr erzeugten Sequenz unterscheidet sich von der vorherigen Permutation durch Vertauschen zweier benachbarter Elemente der Sequenz. Entsprechend findet dieser Algorithmus einen Hamiltonweg im Permutaeder.

Er ist nicht nur einfach und rechnerisch effizient, sondern hat auch den Vorteil, dass nachfolgende Berechnungen der von ihm erzeugten Permutationen beschleunigt werden können, da diese Permutationen einander so ähnlich sind.^[4]

Die Folge von Permutationen für eine gegebene Anzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} kann aus der Folge von Permutationen für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n - 1} gebildet werden, indem die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} an jeder möglichen Position in jeder der kürzeren Permutationen platziert wird. Wenn die Permutation für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n - 1} Elemente eine gerade Permutation ist, wie dies für die 1., 3., 5. usw. Permutationen in der Sequenz der Fall ist, wird die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} an allen möglichen Positionen in absteigender Reihenfolge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} bis 1 platziert. Wenn die Permutation für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n - 1} Elemente ungerade ist, wird die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} in aufsteigender Reihenfolge an allen möglichen Positionen platziert.^[5]

Permutation in der Musik

Permutationen der Lulu-Reihe (Alban Berg)

Über Permutation in der Fugenkomposition siehe unter Fuge.

In der Zwölftontechnik bezeichnet man als Permutation die Ableitung weiterer Reihen aus einer Zwölftonreihe dadurch, dass nach einem bestimmten numerischen Auswahlmodus nacheinander einzelne Töne herausgenommen werden so lange, bis jeweils eine neue vollständige Zwölftonreihe entstanden ist.^[6] So verfährt Alban Berg in seiner Oper Lulu.

Anmerkungen

↑ Als bijektive Abbildung gelegentlich auch
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \colon \{ 1, 2, \ldots , n \} \operatorname{\twoheadrightarrow\!\!\!\!\!\!\!\!\!\!\;\;\rightarrowtail}\; \{ 1, 2, \ldots , n \}}
geschrieben, siehe Funktion (Mathematik) §Symbolik.
↑ B. R. Heap: Permutations by Interchanges. In: The Computer Journal. 6, Nr. 3, 1963, S. 293–4. doi:10.1093/comjnl/6.3.293.
↑ R. Sedgewick: Permutation Generation Methods. In: ACM Computing Surveys. 9, Nr. 2, 1977, S. 137–164. doi:10.1145/356689.356692.
↑ R. Sedgewick: Permutation Generation Methods. In: ACM Computing Surveys. 9, Nr. 2, 1977, S. 137–164. doi:10.1145/356689.356692.
↑ Carla Savage: A survey of combinatorial Gray codes. In: SIAM. 39, Nr. 4, 1997, S. 605–629. doi:10.1137/S0036144595295272.
↑ 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

Commons: Permutationen – Sammlung von Bildern, Videos und Audiodateien

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

[1] Als bijektive Abbildung gelegentlich auch
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi \colon \{ 1, 2, \ldots , n \} \operatorname{\twoheadrightarrow\!\!\!\!\!\!\!\!\!\!\;\;\rightarrowtail}\; \{ 1, 2, \ldots , n \}}
geschrieben, siehe Funktion (Mathematik) §Symbolik.

[Heap-2] B. R. Heap: Permutations by Interchanges. In: The Computer Journal. 6, Nr. 3, 1963, S. 293–4. doi:10.1093/comjnl/6.3.293.

[3] R. Sedgewick: Permutation Generation Methods. In: ACM Computing Surveys. 9, Nr. 2, 1977, S. 137–164. doi:10.1145/356689.356692.

[Sw77-4] R. Sedgewick: Permutation Generation Methods. In: ACM Computing Surveys. 9, Nr. 2, 1977, S. 137–164. doi:10.1145/356689.356692.

[Sav97-5] Carla Savage: A survey of combinatorial Gray codes. In: SIAM. 39, Nr. 4, 1997, S. 605–629. doi:10.1137/S0036144595295272.

[6] 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

[1]

[2]

[3]

[4]

[5]

[6]

Anonym

Suche

Permutation

Kombinatorische Grundlagen

Problemstellung

Permutation ohne Wiederholung

Permutation mit Wiederholung

Algorithmen

Definition

Notation

Zweizeilenform

Tupelschreibweise

Zyklenschreibweise

Weitere Darstellungen

Graphdarstellung

Permutationsmatrizen

Permutationen als Gruppe

Komposition

Identische Permutation

Inverse Permutation

Konjugation

Kenngrößen

Zykeltyp

Ordnung

Fehlstände

Vorzeichen

Anstiege und Abstiege

Ordnungseigenschaften

Anordnung

Aufzählung

Symmetrien

Spezielle Permutationen

Zyklische Permutationen

Fixpunktfreie Permutationen

Selbstinverse Permutationen

Alternierende Permutationen

Separable Permutationen

Zufällige Permutationen

Alle Permutationen von n Objekten

Heap-Algorithmus

Steinhaus-Johnson-Trotter-Algorithmus

Permutation in der Musik

Anmerkungen

Literatur

Weblinks

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien