- Перестановка
-
В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки. Как синоним слову "перестановка" в этом смысле некоторые авторы используют слово расстановка.
В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову "перестановка" в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки.)
Содержание
Свойства
- Число всех перестановок порядка равно числу размещений из n по n, то есть факториалу:[1][2][3][4]
- Композиция определяет операцию произведения на перестановках одного порядка: Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают .
- Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент сопоставляется с перестановкой , задаваемой тождеством где g — произвольный элемент группы G, а — групповая операция.
Связанные определения
- Носитель перестановки — это подмножество множества , определяемое как
- Неподвижной точкой перестановки является всякая неподвижная точка отображения , то есть элемент множества Множество всех неподвижных точек перестановки является дополнением её носителя в .
- Инверсией в перестановке порядка n называется всякая пара индексов такая, что и . Чётность числа инверсий в перестановке определяет чётность перестановки.
- Знак перестановки определяется как +1 для чётной перестановки и −1 для нечётной, что выражается формулой , где — количество инверсий в перестановке . Знак перестановки может быть также определен как , где m — количество транспозиций в разложении в произведение транспозиций. Несмотря на то, что такое разложение не единственно, чётность количества транспозиций во всех разложениях одна и та же, и поэтому знак перестановки корректно определён.
Специальные типы перестановок
- Инволюция — перестановка которая является обратной самой себе, то есть
- Беспорядок — перестановка без неподвижных точек.
- Циклом длины называется такая подстановка которая тождественна на всём множестве кроме подмножества и Обозначается
- Транспозиция — перестановка элементов множества , которая меняет местами два элемента. Транспозиция является циклом длины 2.
Подстановки и произведения циклов
Перестановка множества может быть записана в виде подстановки, например:
где и
Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например:
Перестановки с повторением
Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если ki — количество элементов i-го типа, то и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту
Случайная перестановка
Случайной перестановкой называется случайный вектор все элементы которого принимают натуральные значения от 1 до и при этом вероятность совпадения любых двух элементов равна 0.
Независимой случайной перестановкой называется такая случайная перестановка , для которой
для некоторых таких что
Если при этом не зависят от , то перестановку называют одинаково распределённой. Если же нет зависимости от , то есть то называют однородной.
См. также
Примечания
- ↑ Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 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
Ссылки
- Аранжеман // Энциклопедический словарь Брокгауза и Ефрона: В 86 томах (82 т. и 4 доп.). — СПб., 1890—1907.
Категория:- Комбинаторика
Wikimedia Foundation. 2010.