Действие перестановки на набор из элементов, представление в виде циклов
Перестановка — это отображение
, которое каждому ставит во взаимно-однозначное соответствиеИндексы
, где . Число называют порядком перестановки. Перестановку можно записать в виде упорядоченного набора из чисел . Элемент такого набора означает, что . Таким образом, если — упорядоченный набор элементов из множества , то , где . Например, применив перестановку к набору элементов , получим набор . <br\>Произведение перестановок
Произведением перестановок
и называется композиция (т.е. последовательное применение) этих перестановок: . Легко показать, что произведение перестановок тоже является перестановкой, причем если , то .Циклы
Циклом длины
называется такая перестановка которая тождественна на всём множестве кроме подмножества и Обозначается Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: .Перестановку можно представить в виде графа. Граф содержит ребро от вершины
к вершине если , то есть элемент переходит в после применения перестановки . Тогда циклы перестановки соответствуют циклическим путям в графе.