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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
6 перестановок 3 шаров

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

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

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

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

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

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

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

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

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

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

где и

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

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

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

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

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


Замечание. Имеется два соглашения по умножению перестановок и циклов:

1) .

Например: .

2) .

Например: .

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

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

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

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

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

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

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

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

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

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

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]