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

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

Подстановка

Перестановку можно рассматривать как функцию, которая каждому элементу некоторой начальной перестановки сопоставляет соответствующий по номеру элемент данной перестановки. Такую функцию часто называют подстановкой . Перестановка ${\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\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 }$ называют однородной .

См. также

Примечания

Литература

• Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М. : , 2007. — 824 с. — ISBN 0-201-89685-0 .
• Кострикин А. И. . — М. : Физматлит , 1994. — С. -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.