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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Перестановки»)
Перейти к навигации Перейти к поиску
6 перестановок трёх шаров

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

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

Термин «перестановка» возник потому, что сначала брались объекты, каким-то образом расставленные, а другие способы упорядочения требовали переставить эти объекты.[2].

Свойства[править | править код]

Число всех перестановок из элементов равно числу размещений из по , то есть факториалу[3][4][5][6]:

.

Композиция определяет операцию произведения на перестановках одной длины: Относительно этой операции множество перестановок из элементов образует группу, которую называют симметрической и обычно обозначают .

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

Связанные определения[править | править код]

Носитель перестановки  — это подмножество множества , определяемое как

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

Инверсией в перестановке называется всякая пара индексов такая, что и . Чётность числа инверсий в перестановке определяет чётность перестановки.

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

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

Подстановка[править | править код]

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

где и .

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

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

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

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

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

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

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

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

.

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

.

Перестановки с повторением[править | править код]

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

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

Случайная перестановка[править | править код]

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

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

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

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

См. также[править | править код]

Примечания[править | править код]

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

Литература[править | править код]

Ссылки[править | править код]