В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.
В теории групп под перестановкой (подстановкой) произвольного множества подразумевается биекция этого множества на себя.
Свойства
- Композиция определяет операцию произведения на перестановках одного порядка: Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают .
- Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент сопоставляется с перестановкой , задаваемой тождеством где g — произвольный элемент группы G, а — групповая операция.
Связанные определения
- Носитель перестановки — это подмножество множества , определяемое как
- Неподвижной точкой перестановки является всякая неподвижная точка отображения , то есть элемент множества Множество всех неподвижных точек перестановки является дополнением её носителя в .
- Инверсией в перестановке порядка n называется всякая пара индексов такая, что и . Чётность числа инверсий в перестановке определяет чётность перестановки.
- Знак перестановки определяется как +1 для чётной перестановки и −1 для нечётной, что выражается формулой , где — количество инверсий в перестановке . Знак перестановки может быть также определен как , где m — количество транспозиций в разложении в произведение транспозиций. Несмотря на то, что такое разложение не единственно, чётность количества транспозиций во всех разложениях одна и та же, и поэтому знак перестановки корректно определён.
Специальные типы перестановок
- Инволюция — перестановка которая является обратной самой себе, то есть
- Беспорядок — перестановка без неподвижных точек.
- Циклом длины называется такая подстановка которая тождественна на всём множестве кроме подмножества и Обозначается
- Транспозиция — перестановка элементов множества , которая меняет местами два элемента. Транспозиция является циклом длины 2.
Подстановки и произведения циклов
Перестановка множества может быть записана в виде подстановки, например:
![\begin{pmatrix}
x_1 & x_2 & x_3 & \dots & x_n \\
y_1 & y_2 & y_3 & \dots & y_n\end{pmatrix},](//upload.wikimedia.org/math/6/1/6/61610fc47824304af2e7d91c89414923.png)
где и
Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например:
![(1, 5, 2)(3, 6)(4)=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
5 & 1 & 6 & 4 & 2 & 3\end{pmatrix}.](//upload.wikimedia.org/math/5/e/1/5e11ad100564e6a2663a796d5c12ecb5.png)
Перестановки с повторением
Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если ki — количество элементов i-го типа, то и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту
Случайная перестановка
Случайной перестановкой называется случайный вектор все элементы которого принимают натуральные значения от 1 до и при этом вероятность совпадения любых двух элементов равна 0.
Независимой случайной перестановкой называется такая случайная перестановка , для которой
для некоторых таких что
Если при этом не зависят от , то перестановку называют одинаково распределённой. Если же нет зависимости от , то есть то называют однородной.
См. также
Примечания
- Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
- Теория конфигураций и теория перечислений
- Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.
- ↑ Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы
Литература
- Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0
Ссылки