Permutation

Grundidee und kombinatorische Zählung

Eine Permutation ist in der Kombinatorik eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung einer vorgegebenen Reihung. Sie ist wichtig, weil sich damit mögliche Reihenfolgen systematisch beschreiben und zählen lassen. Beispiele sind Anagramme wie ENKEL und NELKE, das Mischen eines Kartenspiels, der zyklische Stellungswechsel im Volleyball und Sortierverfahren, die sukzessive Vertauschungen von jeweils zwei Objekten verwenden.

Werden nicht alle vorhandenen Objekte ausgewählt, spricht man von einer Variation. Spielt die Reihenfolge bei der Auswahl keine Rolle, handelt es sich um eine Kombination.

Bei einer Permutation ohne Wiederholung sind alle n Objekte unterscheidbar. Für das erste Objekt gibt es n Möglichkeiten, für das zweite n−1, für das dritte n−2 und so weiter. Deshalb beträgt die Anzahl der Anordnungen n! = n · (n−1) · (n−2) · … · 1. Für vier verschiedenfarbige Kugeln gibt es beispielsweise 4! = 4 · 3 · 2 · 1 = 24 Anordnungen.

Bei einer Permutation mit Wiederholung sind manche Objekte nicht unterscheidbar. Sind genau k Objekte identisch, ergeben Vertauschungen dieser Objekte keine neue Anordnung; die Anzahl ist n!/k! = n · (n−1) · … · (k+1) = n hoch fallende Faktorielle n−k. Bei s Gruppen identischer Objekte mit Vielfachheiten k₁,…,kₛ und k₁+…+kₛ=n gilt die Anzahl n!/(k₁! · … · kₛ!) = (n über k₁,…,kₛ), also der Multinomialkoeffizient. Bei vier Kugeln mit genau zwei gleichfarbigen Kugeln gibt es 4!/(2!·1!·1!) = 12, bei je zwei Kugeln gleicher Farbe 4!/(2!·2!) = 6 Anordnungen.

Mathematische Definition und Darstellungen

Sei X = {x₁,x₂,…,xₙ} eine Menge mit n Elementen. Eine n-stellige Permutation ohne Wiederholung ist eine bijektive Abbildung π: X → X. Bijektiv bedeutet, dass jedes Element genau einem Element zugeordnet wird und zwei verschiedene Elemente niemals auf dasselbe Element abgebildet werden. Auch n=0 mit der leeren Menge ist zugelassen. Als Referenzmenge verwendet man meist {1,2,…,n}; dann ist π eine bijektive Abbildung dieser Menge auf sich selbst.

In der Zweizeilenform steht die Permutation als Matrix mit zwei Zeilen. Oben stehen 1 bis n, darunter die jeweiligen Funktionswerte: π = ((1 2 … n)/(π(1) π(2) … π(n))). Für π(1)=2, π(2)=4, π(3)=3 und π(4)=1 lautet die Darstellung ((1 2 3 4)/(2 4 3 1)). In der Tupelschreibweise werden nur die Funktionswerte notiert: π = (π(1),π(2),…,π(n)), im Beispiel also (2,4,3,1). Diese Schreibweise kann mit der Zyklenschreibweise verwechselt werden.

In der Zyklenschreibweise verfolgt man die Bilder eines Elements, bis man wieder beim Ausgangselement ankommt. Ein Zyklus (a π(a) π²(a) … π^(ℓₐ−1)(a)) hat die Länge ℓₐ, wobei ℓₐ die kleinste natürliche Zahl mit π^ℓₐ(a)=a ist. Danach werden noch nicht notierte Elemente in weiteren Zyklen erfasst. Einerzyklen dürfen weggelassen werden; die Darstellung ist nicht eindeutig, weil die Zyklen vertauscht und die Elemente innerhalb eines Zyklus zyklisch verschoben werden können. Das Beispiel wird als (1 2 4)(3) = (1 2 4) = (2 4 1) = (4 1 2) geschrieben.

Weitere Darstellungen sind der gerichtete Graph und die Permutationsmatrix. Im Graphen sind die Knoten 1,…,n und die Kanten (i,π(i)); jeder Knoten besitzt genau eine ein- und eine ausgehende Kante. Graphzyklen entsprechen den Zyklen der Permutation, Fixpunkte erzeugen Schleifen. Der Graph ist genau dann zusammenhängend, wenn die Permutation aus einem einzigen Zyklus der Länge n besteht. Die Permutationsmatrix Pπ hat in Zeile i genau dort eine 1, wo π(i) steht: pᵢⱼ = δπ(i),j. Für einen Spaltenvektor gilt (xπ(1),…,xπ(n))ᵀ = Pπ·(x₁,…,xₙ)ᵀ.

Permutationen als Gruppe

Die Permutationen von {1,2,…,n} bilden mit der Hintereinanderausführung als Verknüpfung die symmetrische Gruppe Sₙ. Ihre Untergruppen heißen Permutationsgruppen. Nach dem Satz von Cayley ist jede endliche Gruppe zu einer Untergruppe einer symmetrischen Gruppe isomorph. In der klassischen Galoistheorie permutiert die Galoisgruppe die Nullstellen von Polynomen; ihre Eigenschaften geben Aufschluss darüber, ob eine Polynomgleichung durch Radikale, also Wurzelausdrücke, lösbar ist. Damit lässt sich unter anderem der Satz von Abel-Ruffini über die allgemeine Polynomgleichung fünften oder höheren Grades beweisen.

Für zwei Permutationen π und τ bedeutet τ ∘ π, dass zuerst π und danach τ angewendet wird. Das Ergebnis ist wieder eine Permutation. Die Komposition ist assoziativ: σ ∘ (τ ∘ π) = (σ ∘ τ) ∘ π. Sie ist im Allgemeinen nicht kommutativ; für n>2 ist Sₙ daher nicht abelsch. Beim Rechnen wird von rechts nach links vorgegangen. Im Beispiel führt die Komposition der Abbildungen ((1 2 3)/(3 1 2)) und ((1 2 3)/(1 3 2)) zu ((1 2 3)/(3 2 1)); die Wege sind 1→1→3, 2→3→2 und 3→2→1.

Das neutrale Element ist die identische Permutation id, die jedes Element festhält: id = ((1 2 … n)/(1 2 … n)). Für jede Permutation π gilt id∘π = π∘id = π. Sie kann auch als (), (1) oder ε notiert werden. Ihre Permutationsmatrix ist die Einheitsmatrix, ihr Graph besteht aus einer Schleife an jedem Knoten.

Zu jeder Permutation gibt es genau eine inverse Permutation π⁻¹ mit π∘π⁻¹ = π⁻¹∘π = id. In der Zweizeilenform vertauscht man dazu obere und untere Zeile. In jedem Zyklus werden die Zahlen in umgekehrter Reihenfolge geschrieben; im Graphen werden alle Kantenrichtungen umgedreht. Die Matrix der inversen Permutation ist die transponierte Ausgangsmatrix. Zwei Permutationen σ und π heißen konjugiert, wenn σ = τ∘π∘τ⁻¹ für eine Permutation τ gilt. Dabei werden die von π abgebildeten Zahlen i→j entsprechend zu τ(i)→τ(j) umbenannt. Die Konjugation ist eine Äquivalenzrelation. In S₃ gibt es die drei Konjugationsklassen [id], [(1 2)] = {(1 2),(1 3),(2 3)} und [(1 2 3)] = {(1 2 3),(1 3 2)}.

Zykeltyp, Ordnung und Vorzeichen

Der Zykeltyp beschreibt, wie viele Zyklen jeder Länge eine Permutation besitzt. Sind bⱼ die Anzahl der Zyklen der Länge j, lautet er typ(π) = 1ᵇ¹2ᵇ²…nᵇⁿ; Terme mit bⱼ=0 können entfallen. Die möglichen Zykeltypen n-stelliger Permutationen entsprechen den Partitionen der Zahl n. Permutationen mit gleichem Zykeltyp sind genau dann konjugiert. Die inverse Permutation hat immer denselben Zykeltyp wie die Ausgangspermutation. Die Anzahl der Permutationen mit gleicher Zyklenzahl wird durch Stirling-Zahlen erster Art gezählt.

Die Ordnung ord(π) ist die kleinste natürliche Zahl k mit πᵏ=id. Aus den disjunkten Zyklen erhält man sie als kleinstes gemeinsames Vielfaches ihrer Längen. Die Permutation (1 2 4)(3 5) hat deshalb die Ordnung kgV(3,2)=6.

Ein Fehlstand oder eine Inversion ist ein Zahlenpaar (i,j) mit i<j und π(i)>π(j). Nach der Permutation steht dann die größere Zahl vor der kleineren. Die Menge aller Fehlstände ist inv(π) = {(i,j) | i<j und π(i)>π(j)}; ihre Anzahl |inv(π)| heißt Fehlstandszahl oder Inversionszahl und kann als Maß für die Unordnung dienen.

Das Vorzeichen oder Signum ist sgn(π)=(-1)^|inv(π)|. Bei gerader Fehlstandszahl ist sgn(π)=+1 und die Permutation gerade, sonst ist sgn(π)=−1 und sie ist ungerade. Die geraden Permutationen bilden die alternierende Gruppe Aₙ.

Ein Anstieg liegt an der Stelle i vor, wenn π(i+1)>π(i), ein Abstieg, wenn π(i+1)<π(i). Die Anzahl der Permutationen in Sₙ mit genau k Anstiegen beziehungsweise Abstiegen wird durch die Euler-Zahlen ⟨n über k⟩ angegeben. Ein maximaler, nicht verlängerbarer Abschnitt aufeinanderfolgender steigender oder fallender Zahlen heißt ansteigender beziehungsweise absteigender Lauf. Hat eine Permutation k Anstiege beziehungsweise Abstiege, besteht sie aus k+1 absteigenden beziehungsweise ansteigenden Läufen; deren Anzahl wird durch ⟨n über k−1⟩ angegeben.

Ordnungseigenschaften und Symmetrien

Über Fehlstände wird auf den n-stelligen Permutationen eine partielle Ordnung definiert: π≤τ genau dann, wenn inv(π)⊆inv(τ). Das minimale Element ist die identische Permutation, das maximale Element die Permutation, welche die Reihenfolge aller Zahlen umkehrt. Im Hasse-Diagramm sind zwei Permutationen durch eine Kante verbunden, wenn sie durch eine Nachbarvertauschung auseinander hervorgehen. Knoten und Kanten bilden einen Cayley-Graphen, der isomorph zum Kantengraphen des entsprechenden Permutaeders ist. Das Permutaeder entsteht als konvexe Hülle der Permutationen von {1,…,n}, wenn diese als Koordinatenvektoren aufgefasst werden.

Der Inversionsvektor oder die Inversionstafel I(π)=(b₁,b₂,…,bₙ) ordnet jeder Zahl j die Anzahl der größeren Zahlen zu, die in der Tupeldarstellung links von j stehen. Aus dem Inversionsvektor lässt sich die Permutation eindeutig zurückgewinnen. Als Zahl im fakultätsbasierten Zahlensystem ergibt sich die eindeutige Nummer z(π) = Σᵢ₌₁ⁿ bᵢ·(n−i)! aus {0,…,n!−1}. Zur Nummerierung wird auch der Lehmer-Code verwendet.

Die komplementäre Permutation lautet π⁻ = (n−π(1)+1,…,n−π(n)+1) und entsteht durch horizontale Spiegelung der Permutationsmatrix. Die reverse Permutation lautet π′=(π(n),π(n−1),…,π(1)) und entsteht durch vertikale Spiegelung. Beide besitzen denselben Zykeltyp und dieselbe Ordnung wie π. Bei ihnen werden Anstiege und Abstiege vertauscht. Das Vorzeichen ändert sich bei der Komplementbildung sowie bei reversen Permutationen der Länge 2 modulo 4 oder 3 modulo 4. Außerdem ist die Inverse des Komplements gleich der revertierten Inversen und die Inverse der Reversion gleich dem Komplement der Inversen.

Spezielle Permutationen, Algorithmen und Anwendungen

Eine zyklische Permutation oder ein k-Zyklus vertauscht k Zahlen zyklisch und lässt die übrigen fest. Ein 2-Zyklus ist eine Transposition. Disjunkte zyklische Permutationen können kommutativ verkettet werden. Die Inverse eines Zyklus ist wieder zyklisch; ebenso sind Potenzen eines Zyklus mit Primlänge zyklisch. Jeder Zyklus lässt sich in nicht notwendig disjunkte Transpositionen zerlegen und hat genau dann ein gerades Vorzeichen, wenn seine Länge ungerade ist.

Fixpunkte sind Zahlen, die von einer Permutation festgehalten werden. In der Zweizeilenform sind oberer und unterer Eintrag derselben Spalte gleich; in der Zyklenschreibweise erscheinen Fixpunkte als Einerzyklen oder gar nicht, und in der Permutationsmatrix steht auf der Hauptdiagonale eine 1. Eine fixpunktfreie Permutation heißt Derangement. Ihre Anzahl wird durch die Subfakultät !n berechnet; für wachsendes n nähert sich der Anteil fixpunktfreier Permutationen sehr schnell dem Kehrwert der eulerschen Zahl e. Wenn einige Elemente an ihrem alten Platz bleiben dürfen, handelt es sich um ein partielles Derangement, dessen Anzahl durch Rencontres-Zahlen ermittelt wird.

Eine Involution oder selbstinverse Permutation erfüllt π²=id beziehungsweise π⁻¹=π. Dazu gehören genau die Permutationen der Ordnung zwei sowie die Identität als einzige Permutation der Ordnung eins. In ihrer Zyklendarstellung kommen höchstens Zyklen der Länge zwei vor, und ihre Permutationsmatrix ist symmetrisch. Die Spiegelung σₙ=((1 2 … n)/(n n−1 … 1))=(1 n)(2 (n−1))(3 (n−2))… ist ein Beispiel. Selbstinverse Permutationen können in der Kryptographie zur Verschlüsselung und Entschlüsselung mit derselben Permutation dienen.

Alternierende Permutationen wechseln in ihrer Tupeldarstellung stets zwischen größer und kleiner; keine Zahl π(j) liegt ihrer Größe nach zwischen π(j−1) und π(j+1). Beginnt die Folge mit einem Anstieg, heißt sie Up-Down-, bei einem Abstieg Down-Up-Permutation. Separable Permutationen entstehen rekursiv als direkte oder schiefe Summe trivialer Permutationen; ihre Anzahl wird durch Schröder-Zahlen beschrieben. Zufällige Permutationen sind zufällig aus Sₙ ausgewählte Elemente eines diskreten Wahrscheinlichkeitsraums. Kennzahlen wie Fixpunkte, Fehlstände und Zyklen werden dabei als diskrete Zufallsvariablen untersucht. Das Fisher-Yates-Verfahren erzeugt solche Permutationen effizient.

Zur Erzeugung aller Permutationen gibt es rekursive Verfahren. Der 1963 von B. R. Heap vorgeschlagene Heap-Algorithmus erzeugt jede nächste Permutation durch den Austausch eines einzigen Elementpaars und minimiert dadurch die Bewegungen. Der Steinhaus-Johnson-Trotter-Algorithmus erzeugt ebenfalls alle Permutationen; aufeinanderfolgende Permutationen unterscheiden sich jeweils durch die Vertauschung zweier benachbarter Elemente. Er entspricht damit einem Hamiltonweg im Permutaeder. Die Folge für n entsteht aus der Folge für n−1, indem n an allen Positionen eingefügt wird: Bei geraden Vorgängerpermutationen in absteigender, bei ungeraden in aufsteigender Positionsreihenfolge.

Anwendungen gibt es unter anderem in der linearen Algebra, etwa in der Leibniz-Formel, bei der Umordnung von Reihen in der Analysis, in Graphentheorie, Spieltheorie, Kryptographie, Informatik und Quantenmechanik. In der Zwölftontechnik bezeichnet Permutation die Ableitung weiterer Zwölftonreihen, indem nach einem bestimmten numerischen Auswahlmodus nacheinander einzelne Töne entnommen werden; Alban Berg verwendet dieses Verfahren in seiner Oper Lulu.