Изменения

'''Перестановка''' — это отображение <mathtex>\pi:X\rightarrow X</mathtex>, которое каждому <mathtex>x_i \in X</mathtex> ставит во взаимно-однозначное соответствие <mathtex>x_j \in X</mathtex>

Индексы <mathtex>i,j \in \mathcal{f}1, 2, \ldots, n\mathcal{g}</mathtex>, где <mathtex>n = \mathcal{j}X\mathcal{j}</mathtex>.Число <mathtex>~n</mathtex> называют порядком перестановки. Перестановку можно записать в виде упорядоченного набора из чисел <mathtex>1, 2,\ldots, n</mathtex>.Элемент такого набора <mathtex>~<\mathcal{h}a_1,a_2,\ldots,a_n>\mathcal{i}~ a_k</mathtex> означает, что <mathtex>~\pi (x_{a_k}) = x_k </mathtex>. Таким образом, если <mathtex> \Theta = <\mathcal{h}x_1,x_{2},\ldots,x_{n}>\mathcal{i}</mathtex> — упорядоченный набор элементов из множества<mathtex>~X</mathtex>, то <mathtex>\pi (\Theta) = <\mathcal{h}x_{q_1},x_{q_2},\ldots,x_{q_n}> \mathcal{i} </mathtex>, где <mathtex>q_{a_i} = i</mathtex>. Например, применив перестановку <mathtex>~<\mathcal{h}3,2,4,1>\mathcal{i}</mathtex> к набору элементов <mathtex>~(x_1,x_2,x_3,x_4)</mathtex>, получим набор <mathtex>~<\mathcal{h}x_4,x_2,x_1,x_3>\mathcal{i}</mathtex>. <br\>

Произведением перестановок <mathtex>~\pi</mathtex> и <mathtex>~\sigma</mathtex> называется композиция (т.е. последовательное применение) этих перестановок: <mathtex>(\pi*\sigma)(\Theta) = \pi(\sigma(\Theta)) = \pi \circ \sigma (\Theta)</mathtex>.Легко показать, что произведение перестановок тоже является перестановкой, причем если <mathtex>~\phi = \pi*\sigma</mathtex>, то <mathtex>\phi(x_i) = \pi \circ \sigma (x_i)</mathtex>.

Циклом длины <mathtex>~l</mathtex> называется такая перестановка <mathtex>~\pi,</mathtex> которая тождественна на всём множестве <mathtex>X,</mathtex> кроме подмножества <mathtex>\{x_1,x_2,\dots,x_l\}\subset X</mathtex> и <mathtex>~\pi(x_l)=x_1,</mathtex> <mathtex>~\pi(x_i)=x_{i+1}.</mathtex> Обозначается <mathtex>(x_1,x_2,\dots,x_l).</mathtex> Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: <mathtex>~(1, 5, 2)(3, 6)(4)=<\mathcal{h}5,1,6,4,2,3> \mathcal{i} </mathtex>.

Перестановку можно представить в виде графа. Граф содержит ребро от вершины <mathtex>~x_i</mathtex> к вершине <mathtex>~x_j</mathtex> если <mathtex>~\pi(x_j) = x_i</mathtex>, то есть элемент <mathtex>~x_i</mathtex> переходит в <mathtex>~x_j</mathtex> после применения перестановки <mathtex>~\pi</mathtex>. Тогда циклы перестановки соответствуют циклическим путям в графе.