В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.

В теории групп под перестановкой (подстановкой) произвольного множества подразумевается биекция этого множества на себя.

Свойства

• Число всех перестановок порядка равно числу размещений из n по n, то есть факториалу:^[1][2][3][4]

• Композиция определяет операцию произведения на перестановках одного порядка: Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают .
• Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент сопоставляется с перестановкой , задаваемой тождеством где g — произвольный элемент группы G, а  — групповая операция.

Связанные определения

• Носитель перестановки  — это подмножество множества , определяемое как
• Неподвижной точкой перестановки является всякая неподвижная точка отображения , то есть элемент множества Множество всех неподвижных точек перестановки является дополнением её носителя в .
• Инверсией в перестановке порядка n называется всякая пара индексов такая, что и . Чётность числа инверсий в перестановке определяет чётность перестановки.
• Знак перестановки определяется как +1 для чётной перестановки и −1 для нечётной, что выражается формулой , где  — количество инверсий в перестановке . Знак перестановки может быть также определен как , где m — количество транспозиций в разложении в произведение транспозиций. Несмотря на то, что такое разложение не единственно, чётность количества транспозиций во всех разложениях одна и та же, и поэтому знак перестановки корректно определён.

Специальные типы перестановок

• Инволюция — перестановка которая является обратной самой себе, то есть
• Беспорядок — перестановка без неподвижных точек.
• Циклом длины называется такая подстановка которая тождественна на всём множестве кроме подмножества и Обозначается
• Транспозиция — перестановка элементов множества , которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановки и произведения циклов

Перестановка множества может быть записана в виде подстановки, например:

где и

Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например:

Перестановки с повторением

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если k_i — количество элементов i-го типа, то и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту

Случайная перестановка

Случайной перестановкой называется случайный вектор все элементы которого принимают натуральные значения от 1 до и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка , для которой

для некоторых таких что

Если при этом не зависят от , то перестановку называют одинаково распределённой. Если же нет зависимости от , то есть то называют однородной.

См. также

• Гигантская компонента
• Сочетание
• Размещение
• Анаграмма

Примечания