Перестановка

6 перестановок 3 шаров

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

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

Свойства

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

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

  • Носитель перестановки   — это подмножество множества  , определяемое как  
  • Неподвижной точкой перестановки   является всякая неподвижная точка отображения  , то есть элемент множества   Множество всех неподвижных точек перестановки   является дополнением её носителя в  .
  • Инверсией в перестановке   называется всякая пара индексов   такая, что   и  . Чётность числа инверсий в перестановке определяет чётность перестановки.

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

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

Подстановка

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

 

где   и  

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

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

 

Часто также считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведенного выше примера таким дополненным разложением будет  . Количество циклов разной длины, а именно набор чисел  , где   — это количество циклов длины  , определяет цикловую структуру перестановки. При этом величина   равна длине перестановки, а величина   равна общему количеству циклов. Количество перестановок из n элементов с k циклами даётся числом Стирлинга первого рода без знака  .

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой e) можно представить как пустое произведение (англ.) транспозиций или, например, как квадрат любой транспозиции:   Цикл длины   можно разложить в произведение   транспозиций следующим образом:

 

Следует заметить, что разложение циклов на произведение транспозиций не является единственным:

 

Таким образом, любая перестановка может быть разложена в произведение транспозиций. Хотя это можно сделать многими способами, чётность количества транспозиций во всех таких разложениях одинакова. Это позволяет определить знак перестановки (чётностью перестановки или сигнатурой перестановки)   как

 

где   — количество транспозиций в каком-то разложении  . При этом   называют чётной перестановкой, если   и нечётной перестановкой, если  

Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки   из   элементов, состоящий из   циклов, равен

 

Знак перестановки   также может быть определен через количество инверсий   в  :

 

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

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

Перестановку с повторениями можно также рассматривать как перестановку мультимножества   мощности  .

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

Основная статья: Случайные перестановки

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

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

 

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

 
 

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

См. также

Примечания

  1. Евгений Вечтомов, Дмитрий Широков. Математика: логика, множества, комбинаторика. Учебное пособие для академического бакалавриата. — 2-е изд.. — Litres, 2018-03-02. — С. 145-146. — 244 с.
  2. Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
  3. Теория конфигураций и теория перечислений
  4. Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.
  5. Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы

Литература

Ссылки