#import "cfg.typ": cfg
#show: cfg

= Перестановки
Перестановка $:=$ биекция между ${1, ..., n}$.

$S_n :=$ множество всех перестановок длины $n$.

Записывают в виде $mat(1, 2, ..., n; pi_1, pi_2, ..., pi_n)$.

$S_n$ - группа, называемая симметрической группой степени $n$.

Цикл - это перестановка, которая циклически переставляет элементы. Например,
$mat(1, 2, 4) = mat(1, 2, 3, 4; 2, 4, 3, 1)$.

$e :=$ id перестановка.

$q$ - порядок перестановки $:= pi^q = e$.

$exists q space pi^q = e$.

$i, j - pi$-эквивалентные $:= exists s in ZZ space j = (pi^s)_i$. $pi$-орбита $:=$
класс такой эквивалентности.

Независимые циклы $:=$ циклы без общих элементов.

Перестановка однозначно разлагается в произведение независимых циклов.

Транспозиция $:=$ цикл длины 2.

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

$mat(i_1, ..., i_n) = mat(i_1, i_n) ... mat(i_1, i_3) mat(i_1, i_2)$.

$op("sign") pi := (-1)^k$, где $k$ - $\#$ транспозиций в разложении $pi$.

Знак перестановки однозначен.

$op("sign") pi sigma = (op("sign") pi) (op("sign") sigma)$.

$op("sign") e = 1$.

$(i, j)$ - инверсия $:= cases(i < j, pi_i > pi_j)$.

$op("sign") pi = (-1)^k$, где $k$ - $\#$ инверсий $pi$.

Декремент перестановки $:= op(d) pi := sum_(i = 1)^m l_i - m$, где $m$ - число циклов в
разложении, а $l_i$ - длина $i$ цикла.

$op("sign") pi = (-1)^(op(d) pi)$.

$op(d) pi = min \#$ транспозиций в разложении.

При перестановке чисел $q, q + 1 space \#$ инверсий меняется на $plus.minus 1$.

$mat(a_1, ..., a_n) mat(a_n, c) = mat(a_1, ..., a_n, c)$.
