WikiSort.ru - Не сортированное

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

• Тождественная перестановка — перестановка ${\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 )}.}$