Permutacja, zwana również “numerem porządkowym” lub “zamówieniem”, jest przekształceniem elementów zamówionej listy S w korespondencję indywidualną z samym S. Liczba permutacji na zbiorze n elementów jest podana przez n! (n factorial; Uspensky 1937, s. 18). Na przykład, są 2!=2-1=2 permutacje {1,2}, czyli {1,2} i {2,1}, oraz 3!=3-2-1=6 permutacji {1,2,3}, czyli {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, i {3,2,1}. Permutacje listy można znaleźć w Wolfram Language przy pomocy polecenia Permutations[list]. Przy pomocy polecenia PermutationListQ[lista] można sprawdzić, czy w języku Wolfram Language jest to permutacja 1, …, n.

Sedgewick (1977) podsumowuje szereg algorytmów do generowania permutacji i określa algorytm minimalnej zmiany permutacji Heap (1963) jako ogólnie najszybszy (Skiena 1990, s. 10). Inną metodę wyliczania permutacji podał Johnson (1963; Séroul 2000, s. 213-218).

Ilość sposobów uzyskania zamówionego podzbioru elementów k z zestawu n elementów jest podana przez

(Uspensky 1937, s. 18), gdzie n! jest czynnikiem. Na przykład, są 4,/2,=12 2-subsety {1,2,3,4}, a mianowicie {1,2}, {1,3}, {1,4}, {2,1}, {2,3}, {2,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2}, i {4,3}. Niezamówione podzestawy zawierające k elementów znane są jako k-zestawy danego zestawu.

Przedstawienie zmiany w wyniku cykli scenicznych jest nowością (aż do żądania cykli). Przypadek cyklicznego rozpadu to etap {4,2,1,3} z {1,2,3,4}. Oznacza to (2)(143), odnoszące się do cykli zmiany przegubu (2) i (143). Jest wiele okazji do wybrania przedstawienia rozpadu cyklicznego, ponieważ (1) cykle są rozłączne i mogą być w ten sposób określone w każdym żądaniu, oraz (2) każdy czop danego cyklu wskazuje na podobny cykl (Skiena 1990, s. 20). W ten sposób (431)(2), (314)(2), (143)(2), (2)(431), (2)(314) i (2)(143) wszystkie przedstawiają podobną zmianę.

Inna dokumentacja, która wyraźnie rozpoznaje pozycje zaangażowane przez komponenty przy wykorzystaniu zmiany na n komponentach, wykorzystuje szkielet 2×n, gdzie linia podstawowa jest (123…n), a kolejna linia jest nowym przebiegiem działania. Na przykład zmiana, która przełącza elementy 1 i 2 oraz ustala 3, składałaby się z następujących elementów

Każda permutacja jest również produktem transpozycji. Zezwolenia są powszechnie oznaczane w porządku leksykograficznym lub transpozycyjnym. Istnieje korespondencja pomiędzy permutacją a parą Young tableaux, znaną jako korespondencja Schensted.

Liczba błędnych permutacji n obiektów wynosi [n!/e], gdzie [x] jest najbliższą funkcją całkowitą. Permutacja n uporządkowanych obiektów, w których żaden obiekt nie znajduje się na swoim naturalnym miejscu, jest nazywana obłąkaniem (lub czasami całkowitą permutacją), a ilość takich permutacji jest podana przez podczynnik !n.

Za pomocą

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

(3)

z x=y=1 daje

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

(4)

więc liczba sposobów wyboru 0, 1, …, lub n na raz wynosi 2^n.

Zestaw wszystkich permutacji zestawu elementów 1, …, n można uzyskać przy użyciu następującej procedury powtarzalnej

 1 2; / ; 2 1

(5)

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

(6)

Należy rozważyć permutacje, w których nie występuje para następujących po sobie elementów (tzn. dziedziczenie w górę lub w dół). Dla n=1, 2, … elementów, liczby takich permutacji wynoszą 1, 0, 0, 2, 14, 90, 646, 5242, 47622, … (OEIS A002464).

Niech zestaw liczb całkowitych 1, 2, …, N zostanie przerwany, a otrzymany ciąg zostanie podzielony na rosnące przebiegi. Oznacza średnią długość n-tego biegu, gdy N zbliża się do nieskończoności, L_n. Kilka pierwszych wartości podsumowano w poniższej tabeli, gdzie e jest podstawą logarytmu naturalnego (Le Lionnais 1983, s. 41-42; Knuth 1998).

n               L_n          OEIS        przybliżony

1               e-1           A091131               1.7182818…

2               e^2-2e  A091132               1.9524…

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