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

В комбинаторике перестано́вкой заданного конечного множества ${\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}$-факториал) различных перестановок (см. рисунок).

6 перестановок трёх шаров; ${\displaystyle 6=1\cdot 2\cdot 3=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 e,}$ которая каждый элемент ${\displaystyle x\in X}$ отображает в себя: ${\displaystyle e(x)=x.}$
• Инволюция — перестановка ${\displaystyle \tau ,}$ которая является обратной самой себе, то есть ${\displaystyle \tau \cdot \tau =e.}$
• Беспорядок — перестановка без неподвижных точек.
• Циклом длины ${\displaystyle \ell }$ называется такая подстановка ${\displaystyle \pi ,}$ которая тождественна на всём множестве ${\displaystyle X,}$ кроме подмножества ${\displaystyle \{x_{1},\;x_{2},\;\ldots ,\;x_{\ell }\}\subset X}$ и ${\displaystyle \pi (x_{\ell })=x_{1},\ \pi (x_{i})=x_{i+1}.}$ Обозначается ${\displaystyle (x_{1},\;x_{2},\;\ldots ,\;x_{\ell }).}$.
• Транспозиция — перестановка элементов множества ${\displaystyle X}$, которая меняет местами два элемента. Транспозиция является циклом длины 2.

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

Перестановку ${\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,b\in G}$ сопоставляется с парой перестановок ${\displaystyle \pi _{a},\pi _{b}}$, задаваемых на элементах ${\displaystyle G}$ тождествами ${\displaystyle \pi _{a}(g)=\pi _{b},a\circ g=b,}$ где ${\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. Выгодский М. Я. Справочник по элементарной математике. — М.: АСТ, 2006. — С. 293—294. — 509 с. — ISBN 5-17-009554-6.
2. Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с. Архивировано 14 октября 2010 года.
3. Математическая энциклопедия, 1984.

Литература

• Дональд Кнут. Искусство программирования, том 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.
• Перестановка // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1984. — Т. 4. — Стб. 256. — 1216 с.
• Сергей Мельников. Перестановки, сочетания, размещения: вывод всех перестановок // Delphi и Turbo Pascal на занимательных примерах. — БХВ-Петербург, 2012. — 448 с. — ISBN 978-5-94157-886-3.

Ссылки

• Аранжеман // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.