ru.wikipedia.org

Перестановка — Википедия

6 перестановок трёх шаров; {\displaystyle 6=1\cdot 2\cdot 3=3!}

В комбинаторике перестано́вкой заданного конечного множества {\displaystyle X=\{a_{1},a_{2},\ldots ,a_{n}\}} (все элементы {\displaystyle X} различны) называется произвольный упорядоченный набор всех элементов {\displaystyle X} (без повторений). Группируя эти элементы в разном порядке, можно получить различные перестановки. Всего из множества с {\displaystyle n} элементами можно получить {\displaystyle n!=1\cdot 2\cdot 3\cdot \ldots \cdot n} ({\displaystyle n}-факториал) различных перестановок (см. рисунок)[1][2].

Перестановка является частным случаем размещения, когда выбираются все элементы множества[1].

Перестановку можно рассматривать как функцию, которая каждому элементу некоторой начальной перестановки сопоставляет соответствующий по номеру элемент данной перестановки. Такую функцию часто называют подстановкой[3]. Перестановка {\displaystyle \pi } множества {\displaystyle X} может быть наглядно представлена в виде таблицы:

{\displaystyle {\begin{pmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}\\y_{1}&y_{2}&y_{3}&\ldots &y_{n}\end{pmatrix}},}

где {\displaystyle \{x_{1},\;\ldots ,\;x_{n}\}=\{y_{1},\;\ldots ,\;y_{n}\}=X} и {\displaystyle \pi (x_{i})=y_{i}}.

Пример: перестановка элементов множества {\displaystyle X} в обратном порядке:

{\displaystyle {\begin{pmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}\\x_{n}&x_{n-1}&x_{n-2}&\ldots &x_{1}\end{pmatrix}},}

Инверсией в перестановке {\displaystyle \pi } называется всякая пара индексов {\displaystyle i,\ j} такая, что {\displaystyle 1\leqslant i<j\leqslant n} и {\displaystyle \pi (i)>\pi (j)}. Чётность числа инверсий в перестановке определяет чётность перестановки. Пример:

{\displaystyle {\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}},}

Здесь элементы 2 и 3 образуют инверсию.

Носитель перестановки {\displaystyle \pi \colon X\to X} — это подмножество множества {\displaystyle X}, определяемое как {\displaystyle \operatorname {supp} (\pi ):=\{x\in X\mid \pi (x)\neq x\}.}

Неподвижной точкой перестановки {\displaystyle \pi } является всякая неподвижная точка отображения {\displaystyle \pi \colon X\to X}, то есть элемент множества {\displaystyle \{x\in X\mid \pi (x)=x\}.} Множество всех неподвижных точек перестановки {\displaystyle \pi } является дополнением её носителя в {\displaystyle X}.

Перестановку {\displaystyle \pi } можно представить в виде ориентированного графа, где вершинами являются элементы конечного множества, а связи между вершинами описывают переход. В случае, {\displaystyle \pi (i)=i}, для {\displaystyle i} элемента рисуется петля. Таким образом, получается граф, где из каждой вершины выходит и входит одно ребро. Пример перестановки представленной в виде ориентированного графа можно увидеть на изображении справа.

Пример перестановки, представленной в виде ориентированного графа

Таким образом, любая перестановка {\displaystyle \pi } может быть разложена в произведение (композицию) непересекающихся циклов длины {\displaystyle \ell \geqslant 2}, причём единственным образом с точностью до порядка следования циклов в произведении. Например:

{\displaystyle {\begin{pmatrix}1&2&3&4&5&6\\5&1&6&4&2&3\end{pmatrix}}=(1,\;5,\;2)(3,\;6).}

Часто также считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведённого выше примера таким дополненным разложением будет {\displaystyle (1,\;5,\;2)(3,\;6)(4)}. Число циклов разной длины, а именно набор чисел {\displaystyle (c_{1},\;c_{2},\;\ldots )}, где {\displaystyle c_{\ell }} — это число циклов длины {\displaystyle \ell }, определяет цикловую структуру перестановки. При этом величина {\displaystyle 1\cdot c_{1}+2\cdot c_{2}+\ldots } равна длине перестановки, а величина {\displaystyle c_{1}+c_{2}+\ldots } равна общему числу циклов. Число перестановок из {\displaystyle n} элементов с {\displaystyle k} циклами даётся числом Стирлинга первого рода без знака {\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}}.

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой {\displaystyle e}) можно представить как пустое произведение[англ.] транспозиций или, например, как квадрат любой транспозиции: {\displaystyle (1,\;2)(1,\;2)=(2,\;3)(2,\;3)=e.} Цикл длины {\displaystyle \ell \geqslant 2} можно разложить в произведение {\displaystyle \ell -1} транспозиций следующим образом:

{\displaystyle (x_{1},\;\ldots ,\;x_{l})=(x_{1},\;x_{\ell })(x_{1},\;x_{\ell -1})\dots (x_{1},\;x_{2}).}

Разложение циклов на произведение транспозиций не является единственным:

{\displaystyle (1,\;2,\;3)=(1,\;3)(1,\;2)=(2,\;3)(1,\;3)=(1,\;3)(2,\;4)(2,\;4)(1,\;2).}

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

{\displaystyle \varepsilon _{\pi }=(-1)^{t},}

где {\displaystyle t} — число транспозиций в каком-то разложении {\displaystyle \pi }. При этом {\displaystyle \pi } называют чётной перестановкой, если {\displaystyle \varepsilon _{\pi }=1}, и нечётной перестановкой, если {\displaystyle \varepsilon _{\pi }=-1}.

Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки {\displaystyle \pi } из {\displaystyle n} элементов, состоящий из {\displaystyle k} циклов, равен

{\displaystyle \varepsilon _{\pi }=(-1)^{n-k}}.

Знак перестановки {\displaystyle \pi } также может быть определён через число инверсий {\displaystyle N(\pi )} в {\displaystyle \pi }:

{\displaystyle \varepsilon _{\pi }=(-1)^{N(\pi )}}.

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

Композиция определяет операцию произведения на перестановках одной длины: {\displaystyle (\pi \cdot \sigma )(k)=\pi (\sigma (k)).} Относительно этой операции множество перестановок из {\displaystyle n} элементов образует группу, которую называют симметрической и обычно обозначают {\displaystyle S_{n}}.

Любая конечная группа порядка {\displaystyle n} изоморфна некоторой подгруппе симметрической группы {\displaystyle S_{n}} (теорема Кэли). При этом каждый элемент {\displaystyle a\in G} сопоставляется с перестановкой {\displaystyle \pi _{a}}, задаваемой на элементах {\displaystyle G} тождеством {\displaystyle \pi _{a}(g)=a\circ g,} где {\displaystyle \circ } — групповая операция в {\displaystyle G}.

Рассмотрим {\displaystyle n} элементов {\displaystyle m} различных типов, причём в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если {\displaystyle k_{i}} — число элементов {\displaystyle i}-го типа, то {\displaystyle k_{1}+k_{2}+\ldots +k_{m}=n} и число всевозможных перестановок с повторениями равно мультиномиальному коэффициенту {\displaystyle \textstyle {\binom {n}{k_{1},\;k_{2},\;\ldots ,\;k_{m}}}={\frac {n!}{k_{1}!k_{2}!\ldots k_{m}!}}.}

Перестановку с повторениями можно также рассматривать как перестановку мультимножества {\displaystyle \{1^{k_{1}},\;2^{k_{2}},\;\ldots ,\;m^{k_{m}}\}} мощности {\displaystyle k_{1}+k_{2}+\ldots +k_{m}=n}.

Случайной перестановкой называется случайный вектор {\displaystyle \xi =(\xi _{1},\;\ldots ,\;\xi _{n}),} все элементы которого принимают натуральные значения от 1 до {\displaystyle n,} и при этом вероятность совпадения любых двух элементов равна 0.

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

{\displaystyle P\{\xi =\sigma \}={\frac {p_{1\sigma (1)}\ldots p_{n\sigma (n)}}{\sum \limits _{\pi \in S_{n}}p_{1\pi (1)}\ldots p_{n\pi (n)}}}}

для некоторых {\displaystyle p_{ij},} таких, что:

{\displaystyle \forall i\ (1\leqslant i\leqslant n)\colon p_{i1}+\ldots +p_{in}=1}
{\displaystyle \sum \limits _{\pi \in S_{n}}p_{1\pi (1)}\ldots p_{n\pi (n)}>0.}

Если при этом {\displaystyle p_{ij}} не зависят от {\displaystyle i}, то перестановку {\displaystyle \xi } называют одинаково распределённой. Если же нет зависимости от {\displaystyle j}, то есть {\displaystyle \forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,} то {\displaystyle \xi } называют однородной.

  1. ↑ 1 2 Выгодский М. Я. Справочник по элементарной математике. — М.: АСТ, 2006. — С. 293—294. — 509 с. — ISBN 5-17-009554-6.
  2. ↑ Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с. Архивировано 14 октября 2010 года.
  3. ↑ Математическая энциклопедия, 1984.