Перестановка, также называемая “порядковым номером” или “порядком”, представляет собой перестановку элементов упорядоченного списка S в соответствие один к одному с самим S. Количество перестановок на наборе из n элементов задается n! (n факториал; Успенский 1937, с. 18). Например, 2!=2-1=2 перестановки {1,2}, а именно {1,2} и {2,1}, а 3!=3-2-1=6 перестановок {1,2,3}, а именно {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, и {3,2,1}. Перестановки списка можно найти в языке Wolfram с помощью команды Permutations[list]. Список длиной n может быть протестирован на перестановку 1, …, n в языке Wolfram с помощью команды PermutationListQ[list].

Sedgewick (1977) суммирует ряд алгоритмов генерации перестановок и определяет минимальное изменение алгоритма перестановки Heap (1963), который, как правило, является самым быстрым (Skiena 1990, p. 10). Другой метод подсчета перестановок был приведен Джонсоном (1963; Сероул 2000, с. 213-218).

Количество способов получения упорядоченного подмножества k элементов из набора n элементов приведено

(Успенский 1937, с. 18), где n! – факториал. Например, 4!/2!=12 2-подмножества {1,2,3,4}, а именно {1,2}, {1,3}, {1,4}, {2,1}, {2,3}, {2,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2}, и {4,3}. Неупорядоченные подмножества, содержащие k элементов, известны как k-подмножества данного множества.

Изображение изменения в результате циклов ступеней является новым (вплоть до запроса циклов). Случаем циклического распада является этап {4,2,1,3} из {1,2,3,4}. Это означает (2)(143), относящийся к разобщенным циклам изменения (2) и (143). При выборе изображения циклического распада есть много возможностей, так как (1) циклы являются разобщенными и, таким образом, могут быть определены в любом запросе, и (2) любой поворот данного цикла указывает на аналогичный цикл (Skiena 1990, p. 20). Таким образом, (431)(2), (314)(2), (143)(2), (2)(431), (2)(314) и (2)(143) изображают похожие изменения.

Другая документация, которая прямо признает позиции, вовлеченные компонентами при использовании изменения на n компонентах, использует рамки 2×n, где первичная линия (123…n) и последующая линия – это новый ход действий. Например, изменение, которое переключает компоненты 1 и 2 и исправляет 3, было бы составлено как

Любая перестановка также является продуктом транспозиции. Пермутации обычно обозначаются в лексикографическом или транспозиционном порядке. Существует соответствие между перестановкой и парой таблиц Юнга, известной как соответствие Шенстеда.

Количество неправильных перестановок n объектов – [n!/e], где [x] – ближайшая целочисленная функция. Перестановка n упорядоченных объектов, в которых ни один объект не находится на своем естественном месте, называется перестановкой (или иногда полной перестановкой), а количество таких перестановок задается подфакториалом !n.

Используя

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

(3)

с x=y=1 дает

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

(4)

так что количество вариантов выбора 0, 1, … или n за раз составляет 2^n.

Набор всех перестановок набора элементов 1, …, n можно получить с помощью следующей рекурсивной процедуры

1 2; / ; 2 1

(5)

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

(6)

Рассмотрим перестановки, в которых не происходит ни одной пары последовательных элементов (т.е. восходящих или нисходящих последовательностей). Для n=1, 2, … элементов число таких перестановок равно 1, 0, 0, 2, 14, 90, 646, 5242, 47622, … (OEIS A002464).

Пусть набор целых чисел 1, 2, …, N будет перемьютирован, а результирующая последовательность разделена на возрастающие прогоны. Обозначим среднюю длину n-го прогона по мере приближения N к бесконечности, L_n. Первые несколько значений приведены в следующей таблице, где e является основой натурального логарифма (Le Lionnais 1983, pp. 41-42; Knuth 1998).

n L_n OEIS приблизительное

1 е-1 А091131 1.7182818…

2 е^2-2е A091132 1.9524…

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