Permutation

Jede der sechs Reihen ist eine andere Permutation von drei verschiedenen Kugeln ⓘ

In der Mathematik ist eine Permutation einer Menge, grob gesagt, eine Anordnung ihrer Mitglieder in einer Sequenz oder linearen Reihenfolge oder, wenn die Menge bereits geordnet ist, eine Neuanordnung ihrer Elemente. Das Wort "Permutation" bezieht sich auch auf den Vorgang, die lineare Ordnung einer geordneten Menge zu ändern. ⓘ

Permutationen unterscheiden sich von Kombinationen, bei denen einige Elemente einer Menge unabhängig von ihrer Reihenfolge ausgewählt werden. Als Tupel geschrieben gibt es beispielsweise sechs Permutationen der Menge {1, 2, 3}, nämlich (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) und (3, 2, 1). Dies sind alle möglichen Anordnungen dieser Drei-Elemente-Menge. Anagramme von Wörtern, deren Buchstaben unterschiedlich sind, sind ebenfalls Permutationen: Die Buchstaben sind bereits im ursprünglichen Wort angeordnet, und das Anagramm ist eine Neuanordnung der Buchstaben. Die Untersuchung von Permutationen endlicher Mengen ist ein wichtiges Thema in den Bereichen Kombinatorik und Gruppentheorie. ⓘ

Permutationen werden in fast jedem Zweig der Mathematik und in vielen anderen Bereichen der Wissenschaft verwendet. In der Informatik werden sie zur Analyse von Sortieralgorithmen verwendet, in der Quantenphysik zur Beschreibung von Teilchenzuständen und in der Biologie zur Beschreibung von RNA-Sequenzen. ⓘ

Die Anzahl der Permutationen von n verschiedenen Objekten ist n faktoriell, gewöhnlich als n! geschrieben, was das Produkt aller positiven ganzen Zahlen kleiner oder gleich n bedeutet. ⓘ

Technisch gesehen ist eine Permutation einer Menge S definiert als eine Bijektion von S auf sich selbst. Das heißt, sie ist eine Funktion von S nach S, bei der jedes Element genau einmal als Bildwert auftritt. Dies ist verwandt mit der Umordnung der Elemente von S, bei der jedes Element s durch das entsprechende f(s) ersetzt wird. Zum Beispiel wird die oben erwähnte Permutation (3, 1, 2) durch die Funktion $\alpha$ definiert als ⓘ

$\alpha (1)=3,\quad \alpha (2)=1,\quad \alpha (3)=2$. ⓘ

Die Gesamtheit aller Permutationen einer Menge bildet eine Gruppe, die symmetrische Gruppe der Menge. Die Gruppenoperation ist die Komposition (Durchführung zweier gegebener Umstellungen nacheinander), die zu einer weiteren Umstellung führt. Da die Eigenschaften von Permutationen nicht von der Art der Elemente der Menge abhängen, werden häufig die Permutationen der Menge $\{1,2,\ldots ,n\}$ die für die Untersuchung von Permutationen betrachtet werden. ⓘ

In der elementaren Kombinatorik sind die k-Permutationen oder partiellen Permutationen die geordneten Anordnungen von k verschiedenen Elementen aus einer Menge. Wenn k gleich der Größe der Menge ist, handelt es sich um die Permutationen der Menge. ⓘ

Bei dem beliebten Puzzle Rubik's Cube, das 1974 von Ernő Rubik erfunden wurde, erzeugt jede Drehung der Puzzleflächen eine Permutation der Oberflächenfarben. ⓘ

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

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

Geschichte

Permutationen, Hexagramme genannt, wurden in China bereits 1000 v. Chr. im I Ging (Pinyin: Yi Jing) verwendet. ⓘ

Al-Khalil (717-786), ein arabischer Mathematiker und Kryptograph, schrieb das Buch der kryptographischen Botschaften. Es enthält die erste Verwendung von Permutationen und Kombinationen, um alle möglichen arabischen Wörter mit und ohne Vokale aufzulisten. ⓘ

Die Regel zur Bestimmung der Anzahl der Permutationen von n Objekten war in der indischen Kultur um 1150 bekannt. Das Lilavati des indischen Mathematikers Bhaskara II. enthält eine Passage, die übersetzt lautet:

Das Produkt der Multiplikation der arithmetischen Reihe, die mit der Einheit beginnt und sich bis zur Anzahl der Stellen fortsetzt, wird die Variationen der Zahl mit bestimmten Zahlen sein. ⓘ

Im Jahr 1677 beschrieb Fabian Stedman Faktoren, als er die Anzahl der Permutationen von Glocken im Wechselgeläut erläuterte. Er geht von zwei Glocken aus: "Zuerst muss man zugeben, dass zwei auf zwei Arten variiert werden können", was er durch die Darstellung von 1 2 und 2 1 veranschaulicht. Dann erklärt er, dass bei drei Glocken "dreimal zwei Figuren aus drei zu erzeugen sind", was wiederum illustriert wird. Seine Erklärung lautet: "Wirf 3 weg, und es bleibt 1,2; wirf 2 weg, und es bleibt 1,3; wirf 1 weg, und es bleibt 2,3". Dann geht er zu vier Glocken über und wiederholt das Argument des Wegwerfens, um zu zeigen, dass es vier verschiedene Dreiergruppen geben wird. Es handelt sich also um einen rekursiven Prozess. Er fährt mit fünf Glocken fort, wobei er die Methode des "Wegwerfens" anwendet und die daraus resultierenden 120 Kombinationen tabellarisch auflistet. An diesem Punkt gibt er auf und merkt an:

Nun ist die Natur dieser Methoden so, dass die Veränderungen auf einer Zahl die Veränderungen auf allen kleineren Zahlen umfasst, ... so dass ein komplettes Geläut von Veränderungen auf einer Zahl durch die Vereinigung der kompletten Geläute auf allen kleineren Zahlen zu einem Gesamtkörper gebildet zu werden scheint;

Stedman weitet die Betrachtung der Permutationen aus; er geht dazu über, die Anzahl der Permutationen der Buchstaben des Alphabets und der Pferde aus einem Stall von 20 zu betrachten. ⓘ

Ein erster Fall, in dem scheinbar nicht zusammenhängende mathematische Fragen mit Hilfe von Permutationen untersucht wurden, ereignete sich um 1770, als Joseph Louis Lagrange bei der Untersuchung von Polynomgleichungen feststellte, dass die Eigenschaften der Permutationen der Wurzeln einer Gleichung mit den Möglichkeiten, sie zu lösen, zusammenhängen. Diese Arbeit führte schließlich durch die Arbeit von Évariste Galois zur Galoistheorie, die eine vollständige Beschreibung der Möglichkeiten und Unmöglichkeiten bei der Lösung von Polynomgleichungen (in einer Unbekannten) durch Radikale liefert. In der modernen Mathematik gibt es viele ähnliche Situationen, in denen das Verständnis eines Problems die Untersuchung bestimmter Permutationen erfordert, die mit dem Problem zusammenhängen. ⓘ

Permutationen ohne Wiederholungen

Das einfachste Beispiel für Permutationen sind Permutationen ohne Wiederholungen, bei denen man die Anzahl der möglichen Anordnungen von n Gegenständen auf n Plätzen betrachtet. Die Fakultät findet besondere Anwendung bei der Bestimmung der Anzahl der Permutationen in einer Menge, die keine Wiederholungen enthält. Die Zahl n!, also die "n-Faktorielle", ist genau die Anzahl der Möglichkeiten, wie wir n Dinge in eine neue Reihenfolge bringen können. Wenn wir z. B. drei Früchte haben: eine Orange, einen Apfel und eine Birne, können wir sie in der genannten Reihenfolge essen, oder wir können sie vertauschen (z. B. einen Apfel, eine Birne und dann eine Orange). Die genaue Anzahl der Permutationen ist dann $3!=1\cdot 2\cdot 3=6$. Die Zahl wird extrem groß, wenn die Anzahl der Gegenstände (n) steigt. ⓘ

In ähnlicher Weise wird die Anzahl der Anordnungen von k Gegenständen aus n Objekten manchmal als partielle Permutation oder k-Permutation bezeichnet. Sie kann geschrieben werden als $nPk$ (was "n permutieren k" bedeutet), und ist gleich der Zahl $n(n-1)\cdots (n-k+1)$ (auch geschrieben als $n!/(n-k)!$). ⓘ

Definition

In mathematischen Texten ist es üblich, Permutationen mit griechischen Kleinbuchstaben zu bezeichnen. Üblicherweise werden entweder $\alpha$ und $\beta$, oder $\sigma ,\tau$ und $\pi$ verwendet. ⓘ

Permutationen können als Bijektionen von einer Menge S auf sich selbst definiert werden. Alle Permutationen einer Menge mit n Elementen bilden eine symmetrische Gruppe, bezeichnet als $S_{n}$, wobei die Gruppenoperation die Komposition der Funktionen ist. Für zwei Permutationen, $\pi$ und $\sigma$ in der Gruppe $S_{n}$gelten die vier Gruppenaxiome: ⓘ

1. Schließung: Wenn $\pi$ und $\sigma$ sind in $S_{n}$ sind, dann ist auch $\pi \sigma .$
2. Assoziativität: Für drei beliebige Permutationen $\pi ,\sigma ,\tau \in S_{n}$, $(\pi \sigma )\tau =\pi (\sigma \tau ).$
3. Identität: Es gibt eine Identitätspermutation, bezeichnet als $\operatorname {id}$ und definiert durch $\operatorname {id} (x)=x$ für alle $x\in S$. Für jede $\sigma \in S_{n}$, $\operatorname {id} \sigma =\sigma \operatorname {id} =\sigma .$
4. Invertierbarkeit: Für jede Permutation $\pi \in S_{n}$gibt es $\pi ^{-1}\in S_{n}$ so dass $\pi \pi ^{-1}=\pi ^{-1}\pi =\operatorname {id} .$

Im Allgemeinen ist die Komposition von zwei Permutationen nicht kommutativ, d. h., $\pi \sigma \neq \sigma \pi .$ ⓘ

Als Bijektion von einer Menge auf sich selbst ist eine Permutation eine Funktion, die eine Umordnung einer Menge vornimmt, und nicht selbst eine Umordnung ist. Ein älterer und elementarerer Standpunkt ist, dass Permutationen die Umordnungen selbst sind. Zur Unterscheidung werden dem Begriff Permutation manchmal die Bezeichnungen aktiv und passiv vorangestellt, während in der älteren Terminologie Substitutionen und Permutationen verwendet werden. ⓘ

Eine Permutation kann in einen oder mehrere disjunkte Zyklen, d. h. Orbits, zerlegt werden, die durch wiederholte Anwendung der Permutation auf einige Elemente gefunden werden. Zum Beispiel ist die Permutation $\sigma$ definiert durch $\sigma (7)=7$ hat einen 1-Zyklus, $(\,7\,)$ während die Permutation $\pi$ definiert durch $\pi (2)=3$ und $\pi (3)=2$ einen 2-Zyklus hat $(\,2\,3\,)$ (Einzelheiten zur Syntax siehe § Zyklusnotation unten). Im Allgemeinen wird ein Zyklus der Länge k, d. h. bestehend aus k Elementen, als k-Zyklus bezeichnet. ⓘ

Ein Element in einem 1-Zyklus $(\,x\,)$ wird als Fixpunkt der Permutation bezeichnet. Eine Permutation, die keine Fixpunkte hat, nennt man eine Derangement. 2-Zyklen werden Transpositionen genannt; bei solchen Permutationen werden lediglich zwei Elemente ausgetauscht, die anderen bleiben fest. ⓘ

Notationen

Da es umständlich ist, Permutationen elementweise, d. h. als stückweise Funktionen, zu schreiben, wurden mehrere Notationen erfunden, um sie kompakter darzustellen. Die Zyklusnotation ist bei vielen Mathematikern beliebt, weil sie kompakt ist und die Struktur einer Permutation transparent macht. Sofern nicht anders angegeben, wird diese Notation in diesem Artikel verwendet, aber andere Notationen sind immer noch weit verbreitet, insbesondere in Anwendungsbereichen. ⓘ

Zweizeilige Notation

In der zweizeiligen Notation von Cauchy werden die Elemente von S in der ersten Zeile aufgelistet, und für jedes Element wird in der zweiten Zeile sein Bild darunter angegeben. Zum Beispiel kann eine bestimmte Permutation der Menge S = {1, 2, 3, 4, 5} wie folgt geschrieben werden

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

Dies bedeutet, dass σ die Bedingungen σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3 und σ(5) = 1 erfüllt. Die Elemente von S können in beliebiger Reihenfolge in der ersten Zeile erscheinen. Diese Permutation kann auch wie folgt geschrieben werden:

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

oder

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

Einzeilige Notation

Wenn es eine "natürliche" Reihenfolge für die Elemente von S gibt, zum Beispiel $x_{1},x_{2},\ldots ,x_{n}$, dann verwendet man diese für die erste Zeile der zweizeiligen Schreibweise:

$\sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.$ ⓘ

Unter dieser Annahme kann man die erste Zeile weglassen und die Permutation in einzeiliger Schreibweise schreiben als

$(\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n}))$,

d. h. als eine geordnete Anordnung der Elemente von S. Es ist darauf zu achten, dass die Einzeilennotation von der unten beschriebenen Zyklusnotation unterschieden wird. In der mathematischen Literatur ist es üblich, die Klammern bei der Einzeilennotation wegzulassen, während sie bei der Zyklusnotation verwendet werden. Die Einzeilennotation wird auch als die Wortdarstellung einer Permutation bezeichnet. Das obige Beispiel würde dann 2 5 4 3 1 lauten, da die natürliche Reihenfolge 1 2 3 4 5 für die erste Zeile angenommen wird. (Üblicherweise werden diese Einträge nur dann durch Kommas getrennt, wenn sie zwei oder mehr Ziffern haben). Diese Form ist kompakter und wird häufig in der elementaren Kombinatorik und der Informatik verwendet. Sie ist besonders nützlich in Anwendungen, bei denen die Elemente von S oder die Permutationen als größer oder kleiner verglichen werden sollen. ⓘ

Zyklus-Schreibweise

Die Zyklusschreibweise beschreibt die Wirkung der wiederholten Anwendung der Permutation auf die Elemente der Menge. Sie drückt die Permutation als ein Produkt von Zyklen aus; da unterschiedliche Zyklen disjunkt sind, spricht man von "Zerlegung in disjunkte Zyklen". ⓘ

Zur Niederschrift der Permutation $\sigma$ in Zyklusnotation zu schreiben, geht man wie folgt vor:

1. Man schreibt eine öffnende Klammer, wählt dann ein beliebiges Element x von $S$ und schreibe es auf: $(\,x$
2. Dann verfolgt man den Orbit von x, d.h. man notiert seine Werte bei aufeinanderfolgenden Anwendungen von $\sigma$: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots$
3. Wiederholen Sie den Vorgang, bis der Wert zu x zurückkehrt, und notieren Sie eine schließende Klammer anstelle von x: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)$
4. Fahren Sie nun mit einem noch nicht notierten Element y von S fort und verfahren Sie auf dieselbe Weise: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)$
5. Wiederholen Sie, bis alle Elemente von S in Zyklen geschrieben sind. ⓘ

Die Permutation 2 5 4 3 1 (in einzeiliger Schreibweise) könnte also als (125)(34) in Zyklusschreibweise geschrieben werden. ⓘ

Während Permutationen im Allgemeinen nicht kommutieren, tun dies disjunkte Zyklen; zum Beispiel,

$$(\,1\,2\,5\,)(\,3\,4\,)=(\,3\,4\,)(\,1\,2\,5\,).$$

Darüber hinaus kann jeder Zyklus auf verschiedene Arten geschrieben werden, indem man verschiedene Ausgangspunkte wählt, zum Beispiel,

$$(\,1\,2\,5\,)(\,3\,4\,)=(\,5\,1\,2\,)(\,3\,4\,)=(\,2\,5\,1\,)(\,4\,3\,).$$

Man kann diese Gleichungen kombinieren, um die disjunkten Zyklen einer gegebenen Permutation auf viele verschiedene Arten zu schreiben. ⓘ

1-Zyklen werden oft in der Zyklusschreibweise weggelassen, sofern der Kontext klar ist; für jedes Element x in S, das in keinem Zyklus vorkommt, nimmt man implizit an $\sigma (x)=x$. Die Identitätspermutation, die nur aus 1-Zyklen besteht, kann durch einen einzigen 1-Zyklus (x), durch die Zahl 1 oder durch id bezeichnet werden. ⓘ

Ein praktisches Merkmal der Zyklusnotation ist, dass die Zyklusnotation der Inversen einer Permutation durch Umkehrung der Reihenfolge der Elemente in den Zyklen der Permutation gegeben ist. Zum Beispiel,

$$[(\,1\,2\,5\,)(\,3\,4\,)]^{-1}=(\,5\,2\,1\,)(\,4\,3\,).$$

ⓘ

Für die obige Beispielpermutation verwendet man die folgenden Zyklenschreibweisen:

$\pi =(1~2~4)(3)=(1~2~4)=(2~4~1)=(4~1~2)$ ⓘ

Kanonische Zyklusschreibweise

In einigen kombinatorischen Zusammenhängen ist es nützlich, eine bestimmte Reihenfolge für die Elemente in den Zyklen und die (disjunkten) Zyklen selbst festzulegen. Miklós Bóna nennt die folgenden Ordnungsentscheidungen die kanonische Zyklusnotation:

• in jedem Zyklus wird das größte Element zuerst aufgeführt
• die Zyklen sind in aufsteigender Reihenfolge ihres ersten Elements geordnet ⓘ

Zum Beispiel ist (312)(54)(8)(976) eine Permutation in kanonischer Zyklusschreibweise. Die kanonische Zyklusschreibweise lässt keine Ein-Zyklen aus. ⓘ

Richard P. Stanley nennt die gleiche Wahl der Darstellung die "Standarddarstellung" einer Permutation, und Martin Aigner verwendet den Begriff "Standardform" für den gleichen Begriff. Sergey Kitaev verwendet ebenfalls die Terminologie der "Standardform", kehrt aber beide Möglichkeiten um, d. h. jeder Zyklus listet sein kleinstes Element zuerst auf, und die Zyklen werden in abnehmender Reihenfolge ihrer kleinsten, d. h. ersten Elemente sortiert. ⓘ

Komposition von Permutationen

Es gibt zwei Möglichkeiten, die Zusammensetzung von zwei Permutationen zu bezeichnen. $\sigma \cdot \pi$ ist die Funktion, die jedes Element x der Menge auf $\sigma (\pi (x))$. Die ganz rechte Permutation wird zuerst auf das Argument angewendet, aufgrund der Schreibweise der Funktionsanwendung. ⓘ

Da die Funktionskomposition assoziativ ist, gilt dies auch für die Kompositionsoperation von Permutationen: $(\sigma \pi )\tau =\sigma (\pi \tau )$. Daher werden Produkte von mehr als zwei Permutationen normalerweise ohne Klammern geschrieben, um die Gruppierung auszudrücken; sie werden auch normalerweise ohne Punkt oder ein anderes Zeichen geschrieben, um die Komposition anzuzeigen. ⓘ

Einige Autoren ziehen es vor, dass der Faktor ganz links zuerst wirkt, aber dazu müssen Permutationen rechts von ihrem Argument geschrieben werden, oft als Exponent, wobei σ, das auf x wirkt, mit x^σ geschrieben wird; dann ist das Produkt definiert durch xσ-π = (x^σ)^π. Daraus ergibt sich jedoch eine andere Regel für die Multiplikation von Permutationen; in diesem Artikel wird die Definition verwendet, bei der die ganz rechte Permutation zuerst angewendet wird. ⓘ

Andere Verwendungen des Begriffs Permutation

Das Konzept einer Permutation als geordnete Anordnung lässt mehrere Verallgemeinerungen zu, die keine Permutationen sind, aber in der Literatur als Permutationen bezeichnet wurden. ⓘ

k-Permutationen von n

Eine schwächere Bedeutung des Begriffs Permutation, die manchmal in Texten der elementaren Kombinatorik verwendet wird, bezeichnet diejenigen geordneten Anordnungen, in denen kein Element mehr als einmal vorkommt, ohne dass jedoch alle Elemente einer bestimmten Menge verwendet werden müssen. Außer in speziellen Fällen handelt es sich dabei nicht um Permutationen, sondern um natürliche Verallgemeinerungen des Konzepts der geordneten Anordnung. Bei dieser Verwendung werden häufig Anordnungen einer festen Länge k von Elementen aus einer gegebenen Menge der Größe n betrachtet, mit anderen Worten, diese k-Permutationen von n sind die verschiedenen geordneten Anordnungen einer k-Elemente-Teilmenge einer n-Menge (in der älteren Literatur manchmal als Variationen oder Anordnungen bezeichnet). Diese Objekte werden auch als partielle Permutationen oder als Sequenzen ohne Wiederholung bezeichnet, Begriffe, die eine Verwechslung mit der anderen, gebräuchlicheren Bedeutung von "Permutation" vermeiden. Die Anzahl solcher $k$-Permutationen von $n$ wird mit verschiedenen Symbolen bezeichnet, z. B. $P_{k}^{n}$, $_{n}P_{k}$, $^{n}P_{k}$, $P_{n,k}$, oder $P(n,k)$bezeichnet, und ihr Wert wird durch das Produkt

$P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} }$, ⓘ

gegeben, das 0 ist, wenn k > n, und ansonsten gleich ist

${\frac {n!}{(n-k)!}}.$ ⓘ

Das Produkt ist gut definiert, ohne die Annahme, dass $n$ eine nichtnegative ganze Zahl ist, und ist auch außerhalb der Kombinatorik von Bedeutung; es ist bekannt als das Pochhammer-Symbol $(n)_{k}$ oder als die $k$-te fallende faktorielle Potenz $n^{\underline {k}}$ von $n$. ⓘ

Diese Verwendung des Begriffs Permutation ist eng verwandt mit dem Begriff Kombination. Eine k-elementige Kombination einer n-Menge S ist eine k-elementige Teilmenge von S, deren Elemente nicht geordnet sind. Nimmt man alle k-Element-Teilmengen von S und ordnet jede von ihnen auf alle möglichen Arten, erhält man alle k-Permutationen von S. Die Anzahl der k-Kombinationen einer n-Menge, C(n,k), ist daher mit der Anzahl der k-Permutationen von n durch verwandt:

$C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {\tfrac {n!}{(n-k)!}}{\tfrac {k!}{0!}}}={\frac {n!}{(n-k)!\,k!}}.$ ⓘ

Diese Zahlen sind auch als Binomialkoeffizienten bekannt und werden bezeichnet durch ${\binom {n}{k}}$. ⓘ

Permutationen mit Wiederholungen

Geordnete Anordnungen von k Elementen einer Menge S, bei denen Wiederholungen erlaubt sind, werden als k-Tupel bezeichnet. Sie werden manchmal auch als Permutationen mit Wiederholung bezeichnet, obwohl sie keine Permutationen im Allgemeinen sind. In manchen Zusammenhängen werden sie auch als Wörter über das Alphabet S bezeichnet. Wenn die Menge S n Elemente hat, ist die Anzahl der k-Tupel über S $n^{k}.$ Es gibt keine Einschränkung, wie oft ein Element in einem k-Tupel vorkommen kann, aber wenn man die Häufigkeit des Vorkommens eines Elements einschränkt, ist diese Formel nicht mehr gültig. ⓘ

Permutationen von Multisets

Permutationen von Multisets ⓘ

Wenn M eine endliche Multimenge ist, dann ist eine Multimengen-Permutation eine geordnete Anordnung der Elemente von M, in der jedes Element genau so oft vorkommt wie seine Vielfachheit in M. Ein Anagramm eines Wortes mit einigen sich wiederholenden Buchstaben ist ein Beispiel für eine Multimengen-Permutation. Wenn die Multiplizitäten der Elemente von M (in einer bestimmten Reihenfolge) gleich $m_{1}$, $m_{2}$, ..., $m_{l}$ und ihre Summe (d. h. die Größe von M) n ist, dann ist die Anzahl der Multiset-Permutationen von M durch den Multinomialkoeffizienten gegeben,

${n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {\left(\sum _{i=1}^{l}{m_{i}}\right)!}{\prod _{i=1}^{l}{m_{i}!}}}.$ ⓘ

Zum Beispiel ist die Anzahl der verschiedenen Anagramme des Wortes MISSISSIPPI:

${\frac {11!}{1!\,4!\,4!\,2!}}=34650$. ⓘ

Eine k-Permutation einer Multimenge M ist eine Folge der Länge k von Elementen von M, in der jedes Element so oft vorkommt, dass seine Vielfachheit in M (die Wiederholungszahl eines Elements) kleiner oder gleich ist. ⓘ

Zirkuläre Permutationen

Permutationen, die als Anordnungen betrachtet werden, werden manchmal auch als linear geordnete Anordnungen bezeichnet. In diesen Anordnungen gibt es ein erstes Element, ein zweites Element und so weiter. Wenn die Objekte jedoch kreisförmig angeordnet sind, gibt es diese Unterscheidung nicht mehr, d. h. es gibt kein "erstes Element" in der Anordnung, sondern jedes beliebige Element kann als Beginn der Anordnung betrachtet werden. Die Anordnungen von Objekten auf kreisförmige Weise werden als kreisförmige Permutationen bezeichnet. Sie können formal als Äquivalenzklassen gewöhnlicher Permutationen der Objekte definiert werden, wobei die Äquivalenzrelation durch das Verschieben des letzten Elements der linearen Anordnung nach vorne entsteht. ⓘ

Zwei kreisförmige Permutationen sind äquivalent, wenn die eine in die andere gedreht werden kann (d. h. ohne Änderung der relativen Positionen der Elemente). Die folgenden vier kreisförmigen Permutationen auf vier Buchstaben werden als gleichwertig betrachtet. ⓘ

     1           4           2           3
   4   3       2   1       3   4       1   2
     2           3           1           4 <span title="Aus: Englische Wikipedia, Abschnitt "Circular permutations"" class="plainlinks">[https://en.wikipedia.org/wiki/Permutation#Circular_permutations <span style="color:#dddddd">ⓘ</span>]</span>

Die kreisförmigen Anordnungen sind gegen den Uhrzeigersinn zu lesen, so dass die beiden folgenden nicht gleichwertig sind, da keine Drehung die eine in die andere bringen kann.

     1          1
   4   3      3   4
     2          2 <span title="Aus: Englische Wikipedia, Abschnitt "Circular permutations"" class="plainlinks">[https://en.wikipedia.org/wiki/Permutation#Circular_permutations <span style="color:#dddddd">ⓘ</span>]</span>

Die Anzahl der kreisförmigen Permutationen einer Menge S mit n Elementen ist (n - 1)! ⓘ

Eigenschaften

Die Anzahl der Permutationen von n verschiedenen Objekten ist n! ⓘ

Die Anzahl der n-Permutationen mit k disjunkten Zyklen ist die vorzeichenlose Stirlingzahl der ersten Art, bezeichnet mit c(n, k). ⓘ

Art der Permutation

Die Zyklen (einschließlich der Fixpunkte) einer Permutation $\sigma$ einer Menge mit n Elementen partitionieren diese Menge; die Längen dieser Zyklen bilden also eine Partition von n, die als Zyklustyp von $\sigma$. Der Zyklustyp enthält eine "1" für jeden Fixpunkt von $\sigma$, eine "2" für jede Transposition und so weiter. Der Zyklustyp von $\beta =(1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)$ ist . $(3,2,2,1).$ ⓘ

Dies kann auch in einer kompakteren Form als [1¹2²3¹] geschrieben werden. Genauer gesagt, lautet die allgemeine Form $[1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]$, wobei $\alpha _{1},\ldots ,\alpha _{n}$ die Anzahl der Zyklen der jeweiligen Länge sind. Die Anzahl der Permutationen eines bestimmten Typs ist

${\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}$. ⓘ

Konjugieren von Permutationen

Im Allgemeinen folgt das Zusammensetzen von Permutationen, die in Zyklusschreibweise geschrieben sind, keinem einfach zu beschreibenden Muster - die Zyklen der Komposition können sich von denen unterscheiden, die zusammengesetzt werden. Die Zyklusstruktur bleibt jedoch in dem speziellen Fall der Konjugation einer Permutation $\sigma$ durch eine andere Permutation $\pi$erhalten, d. h. es wird das Produkt $\pi \sigma \pi ^{-1}$. Hier, $\pi \sigma \pi ^{-1}$ die Konjugierte von $\sigma$ durch $\pi$ und seine Zyklusschreibweise erhält man, indem man die Zyklusschreibweise für $\sigma$ und Anwendung von $\pi$ auf alle Einträge anwendet. Daraus folgt, dass zwei Permutationen genau dann konjugiert sind, wenn sie den gleichen Typ haben. ⓘ

Ordnung

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

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

Die Ordnung einer Permutation $\pi$ ist damit die Elementordnung von $\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 $(124)(35)$ das kleinste gemeinsame Vielfache von drei und zwei, also sechs. ⓘ

Parität einer Permutation

Jede Permutation einer endlichen Menge kann als das Produkt von Transpositionen ausgedrückt werden. Obwohl es viele solcher Ausdrücke für eine gegebene Permutation geben kann, enthalten sie entweder alle eine gerade oder eine ungerade Anzahl von Transpositionen. Somit können alle Permutationen in Abhängigkeit von dieser Zahl als gerade oder ungerade klassifiziert werden. ⓘ

Dieses Ergebnis kann dahingehend erweitert werden, dass jeder Permutation ein Vorzeichen zugeordnet wird, geschrieben $\operatorname {sgn} \sigma$geschrieben, jeder Permutation zuzuordnen. $\operatorname {sgn} \sigma =+1$ wenn $\sigma$ gerade ist und $\operatorname {sgn} \sigma =-1$ wenn $\sigma$ ungerade ist. Dann gilt für zwei Permutationen $\sigma$ und $\pi$ ⓘ

$\operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .$ ⓘ

Daraus folgt, dass $\operatorname {sgn} \left(\sigma \sigma ^{-1}\right)=+1.$ ⓘ

Matrix-Darstellung

Eine Permutationsmatrix ist eine n × n-Matrix, die in jeder Spalte und in jeder Zeile genau einen Eintrag 1 hat, während alle anderen Einträge 0 sind. Es gibt mehrere verschiedene Konventionen, die man verwenden kann, um eine Permutationsmatrix einer Permutation von {1, 2, ..., n} zuzuordnen. Ein natürlicher Ansatz ist, der Permutation σ die Matrix zuzuordnen $M_{\sigma }$ zuzuordnen, deren (i, j)-Eintrag 1 ist, wenn i = σ(j), und ansonsten 0 ist. Diese Konvention hat zwei attraktive Eigenschaften: Erstens ist das Produkt von Matrizen und Permutationen in der gleichen Reihenfolge, d. h, $M_{\sigma }M_{\pi }=M_{\sigma \circ \pi }$ für alle Permutationen σ und π. Zweitens, wenn ${\bf {e}}_{i}$ den Standard $n\times 1$ Spaltenvektor darstellt (der Vektor, bei dem der i-te Eintrag gleich 1 und alle anderen Einträge gleich 0 sind), dann $M_{\sigma }{\bf {e}}_{i}={\bf {e}}_{\sigma (i)}$. ⓘ

Mit dieser Konvention kann beispielsweise die Matrix, die der Permutation $\sigma (1,2,3)=(2,1,3)$ ist . ${\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}$ und die Matrix, die der Permutation $\pi (1,2,3)=(2,3,1)$ ist . ${\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$. Die Komposition von Permutationen ist dann $(\sigma \circ \pi )(1,2,3)=\sigma (2,3,1)=(1,3,2)$und das entsprechende Matrixprodukt ist

$$M_{(2,1,3)}M_{(2,3,1)}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}={\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix}}=M_{(1,3,2)}.$$

ⓘ

Die Komposition von Permutationen entspricht einer Multiplikation von Permutationsmatrizen. ⓘ

In der Literatur ist es auch üblich, die inverse Konvention zu finden, bei der eine Permutation σ mit der Matrix verbunden ist $P_{\sigma }=(M_{\sigma })^{-1}=(M_{\sigma })^{T}$ zugeordnet ist, deren (i, j)-Eintrag 1 ist, wenn j = σ(i), und ansonsten 0 ist. Bei dieser Konvention multiplizieren die Permutationsmatrizen in der umgekehrten Reihenfolge der Permutationen, d. h, $P_{\sigma }P_{\pi }=P_{\pi \circ \sigma }$ für alle Permutationen σ und π. In dieser Korrespondenz wirken Permutationsmatrizen durch Permutation der Indizes von Standard $1\times n$ Zeilenvektoren $({\bf {e}}_{i})^{T}$: man hat $({\bf {e}}_{i})^{T}P_{\sigma }=({\bf {e}}_{\sigma (i)})^{T}$. ⓘ

Die Cayley-Tabelle auf der rechten Seite zeigt diese Matrizen für Permutationen von 3 Elementen. ⓘ

Foatas Übergangslemma

Es besteht eine Beziehung zwischen der einzeiligen und der kanonischen Zyklusschreibweise. Betrachten wir die Permutation $(\,2\,)(\,3\,1\,)$in kanonischer Zyklusschreibweise, so erhält man, wenn man die Klammern des Zyklus löscht, die Permutation $(2,3,1)$ in einzeiliger Notation. Das Übergangslemma von Foata legt die Natur dieser Korrespondenz als Bijektion auf die Menge der n-Permutationen (auf sich selbst) fest. Richard P. Stanley nennt diese Korrespondenz die fundamentale Bijektion. ⓘ

Sei $f$ sei die klammerlöschende Transformation. Die Umkehrung von $q=f(p)$ ist ein bisschen weniger intuitiv. Ausgehend von der einzeiligen Notation $q=q_{1}q_{2}\cdots q_{n}$muss der erste Zyklus in kanonischer Zyklusschreibweise beginnen mit $q_{1}$. Solange die nachfolgenden Elemente kleiner sind als $q_{1}$sind, befinden wir uns im selben Zyklus. Der zweite Zyklus beginnt mit dem kleinsten Index $j$ so dass $q_{j}>q_{1}$. Mit anderen Worten, $q_{j}$ ist größer als alles, was links von ihm liegt, und wird daher als Maximum von links nach rechts bezeichnet. Jeder Zyklus in der kanonischen Zyklusnotation beginnt mit einem Maximum von links nach rechts. ⓘ

Zum Beispiel ist in der einzeiligen Notation $(3,1,2,5,4,8,9,7,6)$ist 5 das erste Element, das größer als 3 ist, also muss der erste Zyklus sein $(\,3\,1\,2\,)$. Dann ist 8 das nächste Element, das größer als 5 ist, also ist der zweite Zyklus $(\,5\,4\,)$. Da 9 größer ist als 8, $(\,8\,)$ ist selbst ein Zyklus. Schließlich ist 9 größer als alle verbleibenden Elemente zu seiner Rechten, also ist der letzte Zyklus $(\,9\,7\,6\,)$. ⓘ

Die sechs Permutationen von $123$ mit ihren kanonischen Zyklusabbildungen sind:

$$123(1)(2)(3),132(1)(32),213(21)(3),231(312),312(321),321(2)(31).$$

ⓘ

Als erste Folgerung ist die Anzahl der n-Permutationen mit genau k Maxima von links nach rechts ebenfalls gleich der vorzeichenlosen Stirlingzahl erster Art, $c(n,k)$. Außerdem führt die Abbildung von Foata eine n-Permutation mit k-schwachen Exzessen zu einer n-Permutation mit k - 1 Aufstiegen. Zum Beispiel hat (2)(31) = 321 zwei schwache Exzedanzen (bei Index 1 und 2), während f(321) = 231 einen Aufstieg hat (bei Index 1, also von 2 nach 3). ⓘ

Permutationen von total geordneten Mengen

In einigen Anwendungen werden die Elemente der zu permutierenden Menge miteinander verglichen. Dies setzt voraus, dass die Menge S eine totale Ordnung hat, so dass zwei beliebige Elemente miteinander verglichen werden können. Die Menge {1, 2, ..., n} ist durch die übliche "≤"-Relation total geordnet und ist daher die am häufigsten verwendete Menge in diesen Anwendungen, aber im Allgemeinen ist jede total geordnete Menge geeignet. In diesen Anwendungen wird die Ansicht der geordneten Anordnung einer Permutation benötigt, um über die Positionen in einer Permutation zu sprechen. ⓘ

Es gibt eine Reihe von Eigenschaften, die direkt mit der vollständigen Ordnung von S zusammenhängen. ⓘ

Aufstiege, Abstiege, Durchläufe und Überschreitungen

Ein Aufstieg einer Permutation σ von n ist jede Position i < n, bei der der folgende Wert größer ist als der aktuelle. Das heißt, wenn σ = σ₁σ₂...σn, dann ist i ein Aufstieg, wenn σi < σ_i+1. ⓘ

Zum Beispiel hat die Permutation 3452167 Aufstiege (an den Positionen) 1, 2, 5 und 6. ⓘ

In ähnlicher Weise ist ein Abstieg eine Position i < n mit σi > σ_i+1, so dass jedes i mit $1\leq i<n$ entweder ein Aufstieg oder ein Abstieg von σ ist. ⓘ

Ein aufsteigender Lauf einer Permutation ist eine nicht leere, ansteigende, zusammenhängende Teilfolge der Permutation, die an beiden Enden nicht erweitert werden kann; sie entspricht einer maximalen Folge von aufeinanderfolgenden Aufstiegen (letztere kann leer sein: zwischen zwei aufeinanderfolgenden Abstiegen gibt es noch einen aufsteigenden Lauf der Länge 1). Im Gegensatz dazu ist eine aufsteigende Teilfolge einer Permutation nicht notwendigerweise zusammenhängend: Sie ist eine aufsteigende Folge von Elementen, die man aus der Permutation erhält, indem man die Werte an einigen Stellen weglässt. Zum Beispiel hat die Permutation 2453167 die aufsteigenden Läufe 245, 3 und 167, während sie eine aufsteigende Teilfolge 2367 hat. ⓘ

Wenn eine Permutation k - 1 Abstiege hat, dann muss sie die Vereinigung von k aufsteigenden Läufen sein. ⓘ

Die Anzahl der Permutationen von n mit k Aufstiegen ist (per Definition) die Eulersche Zahl $\textstyle \left\langle {n \atop k}\right\rangle$; dies ist auch die Anzahl der Permutationen von n mit k Abfahrten. Einige Autoren definieren die Eulersche Zahl jedoch $\textstyle \left\langle {n \atop k}\right\rangle$ als die Anzahl der Permutationen mit k Aufstiegen, was k - 1 Abstiegen entspricht. ⓘ

Eine Exzedanz einer Permutation σ₁σ₂...σn ist ein Index j, so dass σ_j > j ist. Ist die Ungleichung nicht strikt (d. h. σ_j ≥ j), so wird j als schwache Exzedanz bezeichnet. Die Anzahl der n-Permutationen mit k Exzedanzen stimmt mit der Anzahl der n-Permutationen mit k Deszendenzen überein. ⓘ

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

$(\pi (i),\pi (i+1),\ldots ,\pi (i+l))$ ⓘ

Umkehrungen

Beim 15er-Rätsel ist es das Ziel, die Quadrate in aufsteigender Reihenfolge zu erhalten. Ausgangsstellungen, die eine ungerade Anzahl von Invertierungen aufweisen, sind nicht lösbar. ⓘ

Eine Inversion einer Permutation σ ist ein Paar (i, j) von Positionen, in denen die Einträge einer Permutation in umgekehrter Reihenfolge stehen: $i<j$ und $\sigma _{i}>\sigma _{j}$. Ein Abstieg ist also nur eine Inversion an zwei benachbarten Stellen. Zum Beispiel hat die Permutation σ = 23154 drei Invertierungen: (1, 3), (2, 3) und (4, 5), für die Paare der Einträge (2, 1), (3, 1) und (5, 4). ⓘ

Manchmal wird eine Inversion als das Wertepaar (σi,σj) definiert, dessen Reihenfolge umgekehrt ist; dies macht keinen Unterschied für die Anzahl der Inversionen, und dieses (umgekehrte) Wertepaar ist auch eine Inversion im obigen Sinne für die inverse Permutation σ-1. Die Anzahl der Invertierungen ist ein wichtiges Maß für den Grad, in dem die Einträge einer Permutation durcheinander sind; sie ist für σ und für σ-1 gleich groß. Eine Permutation mit k Invertierungen in Ordnung zu bringen (d. h. in die Identitätspermutation umzuwandeln), indem man nacheinander (Rechtsmultiplikation mit) benachbarte Transpositionen anwendet, ist immer möglich und erfordert eine Folge von k solchen Operationen. Außerdem funktioniert jede vernünftige Wahl für die benachbarten Transpositionen: Es genügt, bei jedem Schritt eine Transposition von i und i + 1 zu wählen, wobei i ein Deszendent der bisher modifizierten Permutation ist (so dass die Transposition dieses spezielle Deszendent entfernt, obwohl sie andere Deszendenten erzeugen könnte). Dies ist so, weil die Anwendung einer solchen Transposition die Anzahl der Invertierungen um 1 reduziert; solange diese Anzahl nicht Null ist, ist die Permutation nicht die Identität, so dass sie mindestens ein Descendent hat. Bubble-Sort und Insertion-Sort können als besondere Ausprägungen dieses Verfahrens zum Ordnen einer Folge interpretiert werden. Übrigens beweist dieses Verfahren, dass jede Permutation σ als Produkt benachbarter Transpositionen geschrieben werden kann; dazu kann man einfach jede Folge solcher Transpositionen umkehren, die σ in die Identität verwandelt. In der Tat erhält man durch Aufzählung aller Folgen benachbarter Transpositionen, die σ in die Identität umwandeln würden, (nach Umkehrung) eine vollständige Liste aller Ausdrücke minimaler Länge, die σ als ein Produkt benachbarter Transpositionen schreiben. ⓘ

Die Anzahl der Permutationen von n mit k Umkehrungen wird durch eine Mahonsche Zahl ausgedrückt, es ist der Koeffizient von Xk in der Expansion des Produkts

$$\prod _{m=1}^{n}\sum _{i=0}^{m-1}X^{i}=1\left(1+X\right)\left(1+X+X^{2}\right)\cdots \left(1+X+X^{2}+\cdots +X^{n-1}\right),$$

das auch (mit q anstelle von X) als q-Faktorial [n]_q! bekannt ist. . Die Erweiterung des Produkts erscheint in Necklace (Kombinatorik). ⓘ

Sei $\sigma \in S_{n},i,j\in \{1,2,\dots ,n\}$ so dass $i<j$ und $\sigma (i)>\sigma (j)$. In diesem Fall sagen wir, das Gewicht der Inversion $(i,j)$ ist . $\sigma (i)-\sigma (j)$. Kobayashi (2011) bewies die Aufzählungsformel

$$\sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}$$

ⓘ

wobei $\leq$ die Bruhat-Ordnung in den symmetrischen Gruppen bezeichnet. Diese abgestufte partielle Ordnung erscheint oft im Zusammenhang mit Coxeter-Gruppen. ⓘ

Permutationen im Rechnen

Nummerierung von Permutationen

Eine Möglichkeit, Permutationen von n Dingen darzustellen, ist eine ganze Zahl N mit 0 ≤ N < n!, vorausgesetzt, es gibt bequeme Methoden zur Umrechnung zwischen der Zahl und der Darstellung einer Permutation als geordnete Anordnung (Sequenz). Dies ergibt die kompakteste Darstellung beliebiger Permutationen und ist in der Informatik besonders attraktiv, wenn n so klein ist, dass N in einem Maschinenwort untergebracht werden kann; für 32-Bit-Wörter bedeutet dies n ≤ 12 und für 64-Bit-Wörter n ≤ 20. Die Umwandlung kann über die Zwischenform einer Folge von Zahlen dn, dn-1, ..., d₂, d₁ erfolgen, wobei di eine nichtnegative ganze Zahl kleiner als i ist (man kann d₁ weglassen, da es immer 0 ist, aber sein Vorhandensein macht die anschließende Umwandlung in eine Permutation einfacher zu beschreiben). Der erste Schritt besteht dann darin, N einfach im faktoriellen Zahlensystem auszudrücken, das nur eine besondere gemischte Radix-Darstellung ist, bei der für Zahlen kleiner als n! die Basen (Stellenwerte oder Multiplikationsfaktoren) für aufeinanderfolgende Ziffern (n - 1)!, (n - 2)!, ..., 2!, 1! sind. Im zweiten Schritt wird diese Folge als Lehmer-Code oder (fast gleichwertig) als Inversionstabelle interpretiert. ⓘ

Rothe-Diagramm für $\sigma =(6,3,8,1,4,9,7,2,5)$ ⓘ

σi i	1	2	3	4	5	6	7	8	9	Lehmer-Code
1	×	×	×	×	×	•				d9 = 5
2	×	×	•							d8 = 2
3	×	×		×	×		×	•		d7 = 5
4	•									d6 = 0
5		×		•						d5 = 1
6		×			×		×		•	d4 = 3
7		×			×		•			d3 = 2
8		•								d2 = 0
9					•					d1 = 0
Umkehrungstabelle	3	6	1	2	4	0	2	0	0

Im Lehmer-Code für eine Permutation σ steht die Zahl dn für die Wahl des ersten Terms σ₁, die Zahl dn-1 für die Wahl des zweiten Terms σ₂ aus den verbleibenden n - 1 Elementen der Menge und so weiter. Genauer gesagt, gibt jedes dn+1-i die Anzahl der verbleibenden Elemente an, die streng genommen kleiner sind als der Term σi. Da diese verbleibenden Elemente zwangsläufig als ein späterer Term σj auftauchen, zählt die Ziffer dn+1-i die Inversionen (i,j), die i als kleineren Index enthalten (die Anzahl der Werte j, für die i < j und σi > σj). Die Inversionstabelle für σ ist ganz ähnlich, aber hier zählt dn+1-k die Anzahl der Inversionen (i,j), bei denen k = σj als der kleinere der beiden Werte auftritt, die in invertierter Reihenfolge erscheinen. Beide Kodierungen lassen sich durch ein n-mal-n-Rothe-Diagramm (benannt nach Heinrich August Rothe) veranschaulichen, in dem Punkte bei (i,σi) die Einträge der Permutation und ein Kreuz bei (i,σj) die Inversion (i,j) markieren; gemäß der Definition von Inversionen erscheint ein Kreuz in jedem Quadrat, das sowohl vor dem Punkt (j,σj) in seiner Spalte als auch vor dem Punkt (i,σi) in seiner Zeile steht. Der Lehmer-Code listet die Anzahl der Kreuze in den aufeinanderfolgenden Zeilen auf, während die Inversionstabelle die Anzahl der Kreuze in den aufeinanderfolgenden Spalten auflistet; sie ist einfach der Lehmer-Code für die inverse Permutation und umgekehrt. ⓘ

Um einen Lehmer-Code dn, dn-1, ..., d₂, d₁ effektiv in eine Permutation einer geordneten Menge S umzuwandeln, kann man mit einer Liste der Elemente von S in aufsteigender Reihenfolge beginnen und für i aufsteigend von 1 bis n σi auf das Element in der Liste setzen, dem dn+1-i andere Elemente vorausgehen, und dieses Element aus der Liste entfernen. Um eine Inversionstabelle dn, dn-1, ..., d₂, d₁ in die entsprechende Permutation umzuwandeln, kann man die Zahlen von d₁ bis dn durchlaufen und dabei die Elemente von S von der größten bis zur kleinsten Zahl in eine zunächst leere Folge einfügen; bei dem Schritt, bei dem die Zahl d aus der Inversionstabelle verwendet wird, wird das Element von S an der Stelle in die Folge eingefügt, an der ihm d bereits vorhandene Elemente vorausgehen. Alternativ könnte man die Zahlen aus der Inversionstabelle und die Elemente von S in umgekehrter Reihenfolge verarbeiten, wobei man mit einer Reihe von n leeren Feldern beginnt und bei jedem Schritt das Element aus S in das leere Feld einfügt, dem d andere leere Felder vorausgehen. ⓘ

Die Umwandlung aufeinanderfolgender natürlicher Zahlen in das faktorielle Zahlensystem erzeugt diese Folgen in lexikografischer Reihenfolge (wie bei jedem gemischten Radix-Zahlensystem), und bei der weiteren Umwandlung in Permutationen bleibt die lexikografische Ordnung erhalten, sofern die Lehmer-Code-Interpretation verwendet wird (bei Verwendung von Inversionstabellen erhält man eine andere Ordnung, bei der man Permutationen zunächst nach der Stelle ihrer Einträge 1 vergleicht und nicht nach dem Wert ihrer ersten Einträge). Die Summe der Zahlen in der Darstellung des faktoriellen Zahlensystems ergibt die Anzahl der Invertierungen der Permutation, und die Parität dieser Summe ergibt die Signatur der Permutation. Außerdem geben die Positionen der Nullen in der Inversionstabelle die Werte der von links nach rechts verlaufenden Maxima der Permutation an (im Beispiel 6, 8, 9), während die Positionen der Nullen im Lehmer-Code die Positionen der von rechts nach links verlaufenden Minima sind (im Beispiel die Positionen 4, 8, 9 der Werte 1, 2, 5); dies ermöglicht die Berechnung der Verteilung solcher Extrema unter allen Permutationen. Eine Permutation mit dem Lehmer-Code dn, dn-1, ..., d₂, d₁ hat einen Aufstieg n - i, wenn und nur wenn di ≥ d_i+1. ⓘ

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

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

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

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

Algorithmen zur Erzeugung von Permutationen

Beim Rechnen kann es erforderlich sein, Permutationen einer gegebenen Folge von Werten zu erzeugen. Welche Methoden dafür am besten geeignet sind, hängt davon ab, ob man einige zufällig ausgewählte Permutationen oder alle Permutationen haben möchte, und im letzteren Fall, ob eine bestimmte Reihenfolge erforderlich ist. Eine weitere Frage ist, ob eine mögliche Gleichheit zwischen den Einträgen in der gegebenen Folge berücksichtigt werden soll; wenn dies der Fall ist, sollte man nur eindeutige Multiset-Permutationen der Folge erzeugen. ⓘ

Eine offensichtliche Möglichkeit, Permutationen von n zu erzeugen, besteht darin, Werte für den Lehmer-Code zu erzeugen (möglicherweise unter Verwendung der faktoriellen Zahlendarstellung ganzer Zahlen bis zu n!) und diese in die entsprechenden Permutationen umzuwandeln. Der letztgenannte Schritt ist zwar einfach, aber schwer effizient zu implementieren, da er jeweils n Operationen zur Auswahl aus einer Sequenz und zur Löschung aus dieser an einer beliebigen Position erfordert; von den offensichtlichen Darstellungen der Sequenz als Array oder verknüpfte Liste erfordern beide (aus unterschiedlichen Gründen) etwa n²/4 Operationen zur Durchführung der Umwandlung. Bei n, das wahrscheinlich eher klein ist (vor allem, wenn alle Permutationen erzeugt werden sollen), ist das kein allzu großes Problem, aber es stellt sich heraus, dass es sowohl für die zufällige als auch für die systematische Erzeugung einfache Alternativen gibt, die wesentlich besser funktionieren. Aus diesem Grund erscheint es nicht sinnvoll, obwohl es sicherlich möglich ist, eine spezielle Datenstruktur zu verwenden, die die Umwandlung von Lehmer-Code in Permutation in O(n log n)-Zeit ermöglicht. ⓘ

Zufallsgenerierung von Permutationen

Für die Erzeugung zufälliger Permutationen einer gegebenen Folge von n Werten macht es keinen Unterschied, ob man eine zufällig ausgewählte Permutation von n auf die Folge anwendet oder ein zufälliges Element aus der Menge der verschiedenen (Multiset-)Permutationen der Folge auswählt. Denn auch wenn es bei wiederholten Werten viele verschiedene Permutationen von n geben kann, die zur gleichen permutierten Folge führen, ist die Anzahl solcher Permutationen für jedes mögliche Ergebnis gleich. Anders als bei der systematischen Generierung, die für große n wegen des Wachstums der Zahl n! nicht mehr durchführbar ist, gibt es keinen Grund anzunehmen, dass n bei der Zufallsgenerierung klein sein wird. ⓘ

Die Grundidee zur Erzeugung einer zufälligen Permutation besteht darin, zufällig eine der n! Folgen ganzer Zahlen d₁,d₂,...,dn zu erzeugen, die 0 ≤ di < i erfüllen (da d₁ immer Null ist, kann es weggelassen werden), und sie durch eine bijektive Korrespondenz in eine Permutation umzuwandeln. Für die letztgenannte Korrespondenz könnte man die (umgekehrte) Sequenz als Lehmer-Code interpretieren, und dies ergibt eine Generierungsmethode, die erstmals 1938 von Ronald Fisher und Frank Yates veröffentlicht wurde. Obwohl die Computerimplementierung damals kein Problem darstellte, leidet diese Methode unter der oben skizzierten Schwierigkeit, Lehmer-Code effizient in Permutation umzuwandeln. Dies kann durch die Verwendung einer anderen bijektiven Korrespondenz behoben werden: Nachdem di verwendet wurde, um ein Element aus i verbleibenden Elementen der Folge auszuwählen (für abnehmende Werte von i), wird das Element nicht entfernt und die Folge verdichtet, indem weitere Elemente um einen Platz nach unten verschoben werden, sondern das Element wird mit dem letzten verbleibenden Element vertauscht. Auf diese Weise bilden die zur Auswahl stehenden Elemente zu jedem Zeitpunkt einen aufeinanderfolgenden Bereich, auch wenn sie nicht in der gleichen Reihenfolge wie in der ursprünglichen Folge auftreten. Die Abbildung von einer Folge ganzer Zahlen auf Permutationen ist etwas kompliziert, aber es ist ersichtlich, dass jede Permutation auf genau eine Weise entsteht, und zwar durch eine unmittelbare Induktion. Wenn das ausgewählte Element zufällig das letzte verbleibende Element ist, kann die Vertauschungsoperation entfallen. Dies kommt nicht oft genug vor, um das Testen der Bedingung zu rechtfertigen, aber das letzte Element muss unter den Kandidaten der Auswahl sein, um zu garantieren, dass alle Permutationen erzeugt werden können. ⓘ

Der resultierende Algorithmus zur Erzeugung einer zufälligen Permutation von a[0], a[1], ..., a[n - 1] lässt sich in Pseudocode wie folgt beschreiben:

for i from n downto 2 do
    di ← zufälliges Element aus { 0, ..., i - 1 }
    vertausche a[di] und a[i - 1] ⓘ

Dies kann mit der Initialisierung des Arrays a[i] = i wie folgt kombiniert werden ⓘ

for i von 0 bis n-1 do
    di+1 ← zufälliges Element aus { 0, ..., i }
    a[i] ← a[di+1]
    a[di+1] ← i ⓘ

Wenn d_i+1 = i ist, kopiert die erste Zuweisung einen nicht initialisierten Wert, aber die zweite überschreibt ihn mit dem richtigen Wert i. ⓘ

Fisher-Yates ist jedoch nicht der schnellste Algorithmus zur Erzeugung einer Permutation, da Fisher-Yates im Wesentlichen ein sequentieller Algorithmus ist und "divide and conquer"-Verfahren das gleiche Ergebnis parallel erzielen können. ⓘ

Erzeugung in lexikografischer Reihenfolge

Es gibt viele Möglichkeiten, systematisch alle Permutationen einer gegebenen Folge zu erzeugen. Ein klassischer, einfacher und flexibler Algorithmus basiert auf der Suche nach der nächsten Permutation in lexikografischer Reihenfolge, sofern sie existiert. Er kann mit wiederholten Werten umgehen und erzeugt in diesem Fall jede eindeutige Multiset-Permutation einmal. Selbst für gewöhnliche Permutationen ist es wesentlich effizienter als die Erzeugung von Werten für den Lehmer-Code in lexikografischer Reihenfolge (möglicherweise unter Verwendung des faktoriellen Zahlensystems) und deren Umwandlung in Permutationen. Es beginnt mit der Sortierung der Folge in (schwach) aufsteigender Reihenfolge (was die lexikografisch minimale Permutation ergibt) und geht dann immer weiter zur nächsten Permutation, solange eine gefunden wird. Die Methode geht auf Narayana Pandita im 14. Jahrhundert in Indien zurück und wurde häufig wiederentdeckt. ⓘ

Der folgende Algorithmus erzeugt die nächste Permutation lexikografisch nach einer gegebenen Permutation. Er ändert die gegebene Permutation an Ort und Stelle. ⓘ

1. Finde den größten Index k, so dass a[k] < a[k + 1] ist. Wenn kein solcher Index existiert, ist die Permutation die letzte Permutation.
2. Finde den größten Index l größer als k, so dass a[k] < a[l] ist.
3. Vertausche den Wert von a[k] mit dem von a[l].
4. Umkehrung der Folge von a[k + 1] bis einschließlich des letzten Elements a[n].

Bei der Sequenz [1, 2, 3, 4] (in aufsteigender Reihenfolge) und einem Index, der auf Null basiert, sind die Schritte zum Beispiel wie folgt:

1. Index k = 2, weil 3 an einem Index steht, der die Bedingung erfüllt, der größte Index zu sein, der immer noch kleiner ist als a[k + 1], was 4 ist.
2. Index l = 3, weil 4 der einzige Wert in der Folge ist, der größer als 3 ist, um die Bedingung a[k] < a[l] zu erfüllen.
3. Die Werte von a[2] und a[3] werden vertauscht, um die neue Folge [1, 2, 4, 3] zu bilden.
4. Die Folge nach dem k-Index a[2] bis zum letzten Element wird umgedreht. Da nach diesem Index nur ein Wert liegt (die 3), bleibt die Folge in diesem Fall unverändert. Der lexikographische Nachfolger des Anfangszustandes ist also permutiert: [1, 2, 4, 3].

Nach diesem Algorithmus ist die nächste lexikografische Permutation [1, 3, 2, 4], und die 24. Permutation ist [4, 3, 2, 1], wobei a[k] < a[k + 1] nicht existiert, was bedeutet, dass dies die letzte Permutation ist. ⓘ

Bei dieser Methode werden etwa 3 Vergleiche und 1,5 Vertauschungen pro Permutation benötigt, die sich über die gesamte Folge amortisieren, wobei die anfängliche Sortierung nicht mitgerechnet wird. ⓘ

Generierung mit minimalen Änderungen

Eine Alternative zum obigen Algorithmus, der Steinhaus-Johnson-Trotter-Algorithmus, erzeugt eine Ordnung für alle Permutationen einer gegebenen Folge mit der Eigenschaft, dass sich zwei aufeinanderfolgende Permutationen in der Ausgabe durch Vertauschen zweier benachbarter Werte unterscheiden. Diese Permutationsordnung war den englischen Glockengießern des 17. Jahrhunderts bekannt, die sie als "plain changes" bezeichneten. Ein Vorteil dieser Methode besteht darin, dass die geringe Änderung von einer Permutation zur nächsten es ermöglicht, die Methode in konstanter Zeit pro Permutation zu implementieren. Auch die Teilmenge der geraden Permutationen lässt sich mit dieser Methode leicht erzeugen, ebenfalls in konstanter Zeit pro Permutation, indem jede andere Ausgangs-Permutation übersprungen wird. ⓘ

Eine Alternative zu Steinhaus-Johnson-Trotter ist der Heap-Algorithmus, der von Robert Sedgewick 1977 als der schnellste Algorithmus zur Erzeugung von Permutationen in Anwendungen bezeichnet wurde. ⓘ

Die folgende Abbildung zeigt die Ausgabe aller drei oben genannten Algorithmen zur Erzeugung aller Permutationen der Länge $n=4$und von sechs weiteren in der Literatur beschriebenen Algorithmen. ⓘ

Anordnung aller Permutationen der Länge $n=4$ die von verschiedenen Algorithmen erzeugt wurden. Die Permutationen sind farbcodiert, wobei 1, 2, 3, 4. ⓘ

1. Lexikographische Ordnung;
2. Steinhaus-Johnson-Trotter-Algorithmus;
3. Heaps Algorithmus;
4. Ehrlich's star-transposition algorithm: in jedem Schritt wird der erste Eintrag der Permutation mit einem späteren Eintrag ausgetauscht;
5. Zaks' Algorithmus zur Umkehrung der Präfixe: In jedem Schritt wird ein Präfix der aktuellen Permutation umgekehrt, um die nächste Permutation zu erhalten;
6. Sawada-Williams-Algorithmus: Jede Permutation unterscheidet sich von der vorherigen entweder durch eine zyklische Linksverschiebung um eine Position oder durch den Austausch der ersten beiden Einträge;
7. Corbett-Algorithmus: jede Permutation unterscheidet sich von der vorhergehenden durch eine zyklische Linksverschiebung eines Präfixes um eine Position;
8. Einspurige Ordnung: jede Spalte ist eine zyklische Verschiebung der anderen Spalten;
9. Einspuriger Gray-Code: jede Spalte ist eine zyklische Verschiebung der anderen Spalten, und zwei aufeinanderfolgende Permutationen unterscheiden sich nur durch eine oder zwei Transpositionen. ⓘ

Mittelwertige Permutationen

Meandrische Systeme führen zu meandrischen Permutationen, einer speziellen Untermenge der alternierenden Permutationen. Eine alternative Permutation der Menge {1, 2, ..., 2n} ist eine zyklische Permutation (ohne Fixpunkte), bei der die Ziffern in der zyklischen Schreibweise abwechselnd ungerade und gerade Zahlen enthalten. Mittelwertige Permutationen sind bei der Analyse der RNA-Sekundärstruktur nützlich. Nicht alle alternierenden Permutationen sind meandrisch. Eine Abwandlung des Heap-Algorithmus wurde verwendet, um alle alternativen Permutationen der Ordnung n (d. h. der Länge 2n) zu erzeugen, ohne alle (2n)!-Permutationen zu erzeugen. Die Generierung dieser alternativen Permutationen ist erforderlich, bevor sie analysiert werden können, um festzustellen, ob sie meandrisch sind oder nicht. ⓘ

Der Algorithmus ist rekursiv. Die folgende Tabelle zeigt einen Schritt des Verfahrens. Im vorherigen Schritt wurden alle alternativen Permutationen der Länge 5 erzeugt. Drei Kopien von jeder dieser Permutationen werden mit einer "6" am rechten Ende versehen, und dann wird eine andere Transposition durchgeführt, die diesen letzten Eintrag und einen vorherigen Eintrag an gerader Stelle umfasst (einschließlich der Identität, d. h. keine Transposition). ⓘ

Vorherige Sätze	Transposition von Ziffern	Wechselnde Permutationen ⓘ
1-2-3-4-5-6		1-2-3-4-5-6
	4, 6	1-2-3-6-5-4
	2, 6	1-6-3-4-5-2
1-2-5-4-3-6		1-2-5-4-3-6
	4, 6	1-2-5-6-3-4
	2, 6	1-6-5-4-3-2
1-4-3-2-5-6		1-4-3-2-5-6
	2, 6	1-4-3-6-5-2
	4, 6	1-6-3-2-5-4
1-4-5-2-3-6		1-4-5-2-3-6
	2, 6	1-4-5-6-3-2
	4, 6	1-6-5-2-3-4

Anwendungen

Permutationen werden in der Interleaver-Komponente von Fehlererkennungs- und -korrekturalgorithmen wie Turbo-Codes verwendet, z. B. im 3GPP-Mobilfunkstandard Long Term Evolution (siehe 3GPP Technical Specification 36.212). Bei solchen Anwendungen stellt sich die Frage nach der schnellen Erzeugung von Permutationen, die bestimmte wünschenswerte Eigenschaften erfüllen. Eine der Methoden basiert auf den Permutationspolynomen. Auch als Grundlage für optimales Hashing in Unique Permutation Hashing. ⓘ

Kombinatorische Grundlagen

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

Weitere Darstellungen

Graphdarstellung

Graph der Permutation $(1~2~4~3)(5)(6~7)$ ⓘ

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

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

Permutationen als Gruppe

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

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

Kenngrößen

Fehlstände

Fehlstände der Permutationen in S_{3 ⓘ}

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

Man nennt ein Zahlenpaar $(i,j)$ Fehlstand oder Inversion einer Permutation $\pi$, falls $i<j$ und $\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 $\pi \in S_{n}$ ist damit durch ⓘ

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

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 $n$-stelligen Permutationen eine partielle Ordnung durch ⓘ

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

definieren, wobei $\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 $n$-dimensionalen Raum, das daraus entsteht, dass die Permutationen der Menge $\{1,\ldots ,n\}$ als Koordinatenvektoren interpretiert werden und dann die konvexe Hülle dieser Punkte gebildet wird. ⓘ

Symmetrien

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

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

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

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

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. So verfährt Alban Berg in seiner Oper Lulu. ⓘ