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

Перестано́вка в комбинаторике — упорядоченный набор без повторений чисел $1,\ 2,\ \ldots ,\ n,$ обычно трактуемый как биекция на множестве $\{1,\;2,\;\ldots ,\;n\}$ , которая числу $i$ ставит в соответствие $i$ -й элемент из набора. Число $n$ при этом называется длиной перестановки[1].

6 перестановок трёх шаров

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

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

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

Свойства

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

P_{n}=A_{n}^{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!=1\cdot 2\cdot \ldots \cdot n

.

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

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

Связанные определения

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

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

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

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

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

Подстановка

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

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

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

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

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

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

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

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

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

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

(1,\;2,\;3)=(1,\;3)(1,\;2)=(2,\;3)(1,\;3)=(1,\;3)(2,\;4)(2,\;4)(1,\;2).

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

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

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

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

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

.

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

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

.

Перестановки с повторением

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

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

Случайная перестановка

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

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

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)}}}

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

\forall i\ (1\leqslant i\leqslant n)\colon p_{i1}+\ldots +p_{in}=1

\sum \limits _{\pi \in S_{n}}p_{1\pi (1)}\ldots p_{n\pi (n)}>0.

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

См. также

Примечания

Евгений Вечтомов, Дмитрий Широков. Математика: логика, множества, комбинаторика. Учебное пособие для академического бакалавриата. — 2-е изд.. — Litres, 2018-03-02. — С. 145—146. — 244 с.
Учебник по математике для СПО / Башмаков М. И., 10-11 класс. — С. 67
[https://rustem-af.ru/assets/res/files/161/tvims.pdf#:~:text=Перестановки%2C%20размещения%2C%20сочетания%20(с%20повторами,следования%2C%20так%20и%20составом%20элементов Теория вероятностей и математическая статистика
Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
Теория конфигураций и теория перечислений
Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.
Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы

Литература

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

Ссылки

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Евгений Вечтомов, Дмитрий Широков. Математика: логика, множества, комбинаторика. Учебное пособие для академического бакалавриата. — 2-е изд.. — Litres, 2018-03-02. — С. 145—146. — 244 с.

[2] Учебник по математике для СПО / Башмаков М. И., 10-11 класс. — С. 67

[3] [https://rustem-af.ru/assets/res/files/161/tvims.pdf#:~:text=Перестановки%2C%20размещения%2C%20сочетания%20(с%20повторами,следования%2C%20так%20и%20составом%20элементов Теория вероятностей и математическая статистика

[4] Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.

[5] Теория конфигураций и теория перечислений

[6] Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.

[7] Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы