- Перестановка
-
В комбинаторике перестано́вка — это упорядоченный набор чисел
обычно трактуемый как биекция на множестве
, которая числу 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.