Действие перестановки на набор из элементов, представление в виде циклов
Версия от 11:46, 12 января 2012; Андрей Шулаев (обсуждение | вклад)
Действие перестановки на набор элементов
Определение: |
Пусть | — перестановка порядка , и — множество некоторых объектов, занумерованных числами от одного до . Тогда результатом действия перестановки на этот набор объектов назовём множество объектов , занумерованных числами от одного до , причём .
Обозначим за множество (не пронумерованных) объектов . Поскольку перестановку можно рассматривать как отображение , а нумерацию как отображение , то действие перестановки можно определить как композицию отображений .
Например, рассмотрим множество
и перестановку . Тогда результат действия на — упорядоченное множество .Также, композицию перестановок можно выразить как действие одной перестановки на другую.
Циклы
Циклом длины
называется такая перестановка которая тождественна на всём множестве кроме подмножества и , Обозначается . Перестановку можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: .Перестановку можно представить в виде графа. Граф содержит ребро от вершины
к вершине если . Тогда циклы перестановки соответствуют циклическим путям в графе.