Перестановка
В комбинаторике перестано́вка — это упорядоченный набор без повторений чисел обычно трактуемый как биекция на множестве , которая числу i ставит в соответствие i-й элемент из набора. Число n при этом называется длиной перестановки[1].
В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки.)
Термин перестановка возник потому, что сначала брались объекты, каким-то образом расставленные, а другие способы упорядочения требовали переставить эти объекты. [2].
Свойства[править | править код]
- Число всех перестановок из элементов равно числу размещений из n по n, то есть факториалу:[3][4][5][6]
- Композиция определяет операцию произведения на перестановках одной длины: Относительно этой операции множество перестановок из n элементов образует группу, которую называют симметрической и обычно обозначают .
- Любая конечная группа из n элементов изоморфна некоторой подгруппе симметрической группы (теорема Кэли). При этом каждый элемент сопоставляется с перестановкой , задаваемой на элементах G тождеством где — групповая операция в G.
Связанные определения[править | править код]
- Носитель перестановки — это подмножество множества , определяемое как
- Неподвижной точкой перестановки является всякая неподвижная точка отображения , то есть элемент множества Множество всех неподвижных точек перестановки является дополнением её носителя в .
- Инверсией в перестановке называется всякая пара индексов такая, что и . Чётность числа инверсий в перестановке определяет чётность перестановки.
Специальные типы перестановок[править | править код]
- Тождественная перестановка — перестановка которая каждый элемент отображает в себя:
- Инволюция — перестановка которая является обратной самой себе, то есть
- Беспорядок — перестановка без неподвижных точек.
- Циклом длины называется такая подстановка которая тождественна на всём множестве кроме подмножества и Обозначается .
- Транспозиция — перестановка элементов множества , которая меняет местами два элемента. Транспозиция является циклом длины 2.
Подстановка[править | править код]
Перестановка множества может быть записана в виде подстановки, например:
где и
Произведения циклов и знак перестановки[править | править код]
Любая перестановка может быть разложена в произведение (композицию) непересекающихся циклов длины , причём единственным образом с точностью до порядка следования циклов в произведении. Например:
Часто также считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведенного выше примера таким дополненным разложением будет . Количество циклов разной длины, а именно набор чисел , где — это количество циклов длины , определяет цикловую структуру перестановки. При этом величина равна длине перестановки, а величина равна общему количеству циклов. Количество перестановок из n элементов с k циклами даётся числом Стирлинга первого рода без знака .
Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой e) можно представить как пустое произведение транспозиций или, например, как квадрат любой транспозиции: Цикл длины можно разложить в произведение транспозиций следующим образом:
Следует заметить, что разложение циклов на произведение транспозиций не является единственным:
Таким образом, любая перестановка может быть разложена в произведение транспозиций. Хотя это можно сделать многими способами, чётность количества транспозиций во всех таких разложениях одинакова. Это позволяет определить знак перестановки (чётностью перестановки или сигнатурой перестановки) как
где — количество транспозиций в каком-то разложении . При этом называют чётной перестановкой, если и нечётной перестановкой, если
Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки из элементов, состоящий из циклов, равен
Знак перестановки также может быть определен через количество инверсий в :
Перестановки с повторением[править | править код]
Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если ki — количество элементов i-го типа, то и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту
Перестановку с повторениями можно также рассматривать как перестановку мультимножества мощности .
Случайная перестановка[править | править код]
Случайной перестановкой называется случайный вектор все элементы которого принимают натуральные значения от 1 до и при этом вероятность совпадения любых двух элементов равна 0.
Независимой случайной перестановкой называется такая случайная перестановка , для которой
для некоторых таких, что
Если при этом не зависят от , то перестановку называют одинаково распределённой. Если же нет зависимости от , то есть то называют однородной.
См. также[править | править код]
Примечания[править | править код]
- ↑ Евгений Вечтомов, Дмитрий Широков. Математика: логика, множества, комбинаторика. Учебное пособие для академического бакалавриата. — 2-е изд.. — Litres, 2018-03-02. — С. 145-146. — 244 с.
- ↑ Учебник по математике для СПО. Башммаков М.И. 10-11 класс. С 67
- ↑ Виленкин Н.Я. Глава 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.
- Кострикин А. И. Введение в алгебру. Основы алгебры. — М.: Физматлит, 1994. — С. 59-71. — 320 с. — ISBN 5-02-014644-7.
- Сергей Мельников. Перестановки, сочетания, размещения: вывод всех перестановок // Delphi и Turbo Pascal на занимательных примерах. — БХВ-Петербург, 2012. — 448 с. — ISBN 978-5-94157-886-3.
Ссылки[править | править код]
- Аранжеман // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.