Permutation

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 ${\displaystyle n}$ natürlichen Zahlen bildet mit der Hintereinanderausführung als Verknüpfung die symmetrische Gruppe vom Grad ${\displaystyle 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).