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

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

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

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

Свойства[ | ]

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

${\displaystyle P_{n}=A_{n}^{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!=1\cdot 2\cdot \dots \cdot n.}$

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

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

• Носитель перестановки ${\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 i,j}$ такая, что ${\displaystyle 1\leqslant i<j\leqslant n}$ и ${\displaystyle \pi (i)>\pi (j)}$. Чётность числа инверсий в перестановке определяет чётность перестановки.

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

• Тождественная перестановка — перестановка ${\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},\dots ,x_{\ell }\}\subset X}$ и ${\displaystyle \pi (x_{\ell })=x_{1},\pi (x_{i})=x_{i+1}.}$ Обозначается ${\displaystyle (x_{1},x_{2},\dots ,x_{\ell }).}$.
• Транспозиция — перестановка элементов множества ${\displaystyle X}$, которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановка[ | ]

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

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

где ${\displaystyle \{x_{1},\dots ,x_{n}\}=\{y_{1},\dots ,y_{n}\}=X}$ и ${\displaystyle \pi (x_{i})=y_{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},\dots )}$, где ${\displaystyle c_{\ell }}$ — это количество циклов длины ${\displaystyle \ell }$, определяет цикловую структуру перестановки. При этом величина ${\displaystyle 1\cdot c_{1}+2\cdot c_{2}+\dots }$ равна длине перестановки, а величина ${\displaystyle c_{1}+c_{2}+\dots }$ равна общему количеству циклов. Количество перестановок из n элементов с k циклами даётся числом Стирлинга первого рода без знака ${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}}$.

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

${\displaystyle (x_{1},\dots ,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 )}.}$

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

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

Перестановку с повторениями можно также рассматривать как перестановку мультимножества ${\displaystyle \{1^{k_{1}},2^{k_{2}},\dots ,m^{k_{m}}\}}$ мощности ${\displaystyle k_{1}+k_{2}+\dots +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):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 \scriptstyle \forall i,j(1\leq i,j\leq n):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. — С. 59-71. — 320 с. — ISBN 5-02-014644-7.
• Сергей Мельников. Перестановки, сочетания, размещения: вывод всех перестановок // Delphi и Turbo Pascal на занимательных примерах. — БХВ-Петербург, 2012. — 448 с. — ISBN 978-5-94157-886-3.

Ссылки[ | ]

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