Eine Permutation, auch “Ordnungsnummer” oder “Ordnung” genannt, ist eine Umordnung der Elemente einer geordneten Liste S in eine Eins-zu-Eins-Korrespondenz mit S selbst. Die Anzahl der Permutationen auf einer Menge von n Elementen ist durch n gegeben! (n faktoriell; Uspensky 1937, S. 18). So gibt es beispielsweise 2!=2-1=2 Permutationen von {1,2}, nämlich {1,2} und {2,1}, und 3!=3-2-1=6 Permutationen von {1,2,3}, nämlich {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} und {3,2,1}. Die Permutationen einer Liste können in der Wolfram-Sprache mit dem Befehl Permutations[list] gefunden werden. Eine Liste der Länge n kann mit dem Befehl PermutationListQ[list] getestet werden, um festzustellen, ob es sich um eine Permutation von 1, …, n in der Wolfram-Sprache handelt.

Sedgewick (1977) fasst eine Reihe von Algorithmen zur Generierung von Permutationen zusammen und identifiziert den Permutationsalgorithmus von Heap (1963) mit der geringsten Änderung als den schnellsten (Skiena 1990, S. 10). Eine weitere Methode zur Aufzählung von Permutationen wurde von Johnson (1963; Séroul 2000, S. 213-218) angegeben.

Die Anzahl der Möglichkeiten, eine geordnete Teilmenge von k Elementen aus einer Menge von n Elementen zu erhalten, ist gegeben durch

(Uspensky 1937, S. 18), wobei n! eine Fakultät ist. Zum Beispiel gibt es 4!/2!=12 2-Untergruppen von {1,2,3,4}, nämlich {1,2}, {1,3}, {1,4}, {2,1}, {2,3}, {2,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2} und {4,3}. Die ungeordneten Untermengen, die k Elemente enthalten, werden als die k-Untermengen einer gegebenen Menge bezeichnet.

Die Darstellung einer Veränderung als Folge von Bühnenzyklen ist neuartig (bis hin zur Beantragung der Zyklen). Ein Fall eines zyklischen Zerfalls ist das Stadium {4,2,1,3} von {1,2,3,4}. Dies wird mit (2)(143) bezeichnet, was sich auf die disjunkten Änderungszyklen (2) und (143) bezieht. Die Darstellung eines zyklischen Zerfalls bietet eine Menge Möglichkeiten, da (1) die Zyklen disjunkt sind und somit in jeder Anfrage bestimmt werden können, und (2) jeder Drehpunkt eines bestimmten Zyklus auf einen ähnlichen Zyklus hinweist (Skiena 1990, S. 20). Auf diese Weise stellen (431)(2), (314)(2), (143)(2), (2)(431), (2)(314) und (2)(143) alle eine ähnliche Änderung dar.

Eine weitere Dokumentation, die ausdrücklich die Positionen anerkennt, die von den Komponenten betroffen sind, wenn die Nutzung einer Änderung an n Komponenten einen 2×n Rahmen verwendet, wobei die Primärlinie (123…n) und die nachfolgende Linie die neue Vorgehensweise ist. Zum Beispiel würde die Änderung, die die Komponenten 1 und 2 wechselt und 3 fixiert, folgendermaßen zusammengesetzt sein

Jede Permutation ist auch ein Produkt von Transpositionen. Permutationen werden üblicherweise in lexikographischer oder transpositionstechnischer Reihenfolge bezeichnet. Es gibt eine Übereinstimmung zwischen einer Permutation und einem Paar junger Tableaus, die als die Schensted-Korrespondenz bekannt sind.

Die Anzahl der falschen Permutationen von n Objekten ist [n!/e], wobei [x] die nächstliegende Ganzzahl-Funktion ist. Eine Permutation von n geordneten Objekten, in denen sich kein Objekt an seinem natürlichen Platz befindet, wird als Umgehung (oder manchmal auch als vollständige Permutation) bezeichnet, und die Anzahl solcher Permutationen wird durch die Subfaktorielle !n angegeben.

Verwendung von

 (x+y)^n=Summe_(r=0)^n(n; r)x^(n-r)y^r

(3)

mit x=y=1 ergibt

 2^n=Summe_(r=0)^n(n; r),

(4)

so dass die Anzahl der Möglichkeiten, 0, 1, …, oder n gleichzeitig zu wählen, 2^n beträgt.

Die Menge aller Permutationen einer Menge von Elementen 1, …, n kann durch folgende rekursive Prozedur erhalten werden

 1 2; / ; 2 1

(5)

 1  2 3;     / ; 1 3 2 ; /    ; 3 1 2 ; |     ; 3 2 1 ; \    ; 2 3 1 ; \     ; 2  1 3

(6)

Betrachten Sie Permutationen, bei denen kein Paar aufeinanderfolgender Elemente (d.h. steigende oder fallende Abfolgen) auftreten. Für n=1, 2, … Elemente beträgt die Anzahl solcher Permutationen 1, 0, 0, 2, 14, 90, 646, 5242, 47622, … (OEIS A002464).

Lassen Sie die Menge der ganzen Zahlen 1, 2, …, N permutieren und die sich daraus ergebende Folge in aufsteigende Läufe aufteilen. Bezeichnen die durchschnittliche Länge des n-ten Durchlaufs, da sich N der Unendlichkeit nähert, L_n. Die ersten paar Werte sind in der folgenden Tabelle zusammengefasst, wobei e die Basis des natürlichen Logarithmus ist (Le Lionnais 1983, S. 41-42; Knuth 1998).

n               L_n          OEIS        ungefähr

1               e-1           A091131               1.7182818…

2               e^2-2e  A091132               1.9524…

3               e^3-3e^2+3/2e A091133               1.9957…