Действие перестановки на набор из элементов, представление в виде циклов — различия между версиями
(→Циклы) |
|||
Строка 1: | Строка 1: | ||
'''Перестановка''' — это отображение <tex>\pi:X\rightarrow X</tex>, которое каждому <tex>x_i \in X</tex> ставит во взаимно-однозначное соответствие <tex>x_j \in X</tex> | '''Перестановка''' — это отображение <tex>\pi:X\rightarrow X</tex>, которое каждому <tex>x_i \in X</tex> ставит во взаимно-однозначное соответствие <tex>x_j \in X</tex> | ||
+ | [[Файл:cycles.gif|150px|right|thumb|Изображение перестановки в виде графа]] | ||
+ | |||
Индексы <tex>i,j \in \mathcal{f}1, 2, \ldots, n\mathcal{g}</tex>, где <tex>n = \mathcal{j}X\mathcal{j}</tex>. | Индексы <tex>i,j \in \mathcal{f}1, 2, \ldots, n\mathcal{g}</tex>, где <tex>n = \mathcal{j}X\mathcal{j}</tex>. | ||
Строка 11: | Строка 13: | ||
Перестановку можно представить в виде графа. Граф содержит ребро от вершины <tex>~x_i</tex> к вершине <tex>~x_j</tex> если <tex>~\pi(x_j) = x_i</tex>, то есть элемент <tex>~x_i</tex> переходит в <tex>~x_j</tex> после применения перестановки <tex>~\pi</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе. | Перестановку можно представить в виде графа. Граф содержит ребро от вершины <tex>~x_i</tex> к вершине <tex>~x_j</tex> если <tex>~\pi(x_j) = x_i</tex>, то есть элемент <tex>~x_i</tex> переходит в <tex>~x_j</tex> после применения перестановки <tex>~\pi</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе. | ||
− |
Версия 11:17, 12 января 2012
Перестановка — это отображение
, которое каждому ставит во взаимно-однозначное соответствие
Индексы , где .
Число называют порядком перестановки. Перестановку можно записать в виде упорядоченного набора из чисел .
Элемент такого набора означает, что . Таким образом, если — упорядоченный набор элементов из множества , то , где . Например, применив перестановку к набору элементов , получим набор . <br\>
Произведение перестановок
Произведением перестановок
и называется композиция (т.е. последовательное применение) этих перестановок: . Легко показать, что произведение перестановок тоже является перестановкой, причем если , то .Циклы
Циклом длины
называется такая перестановка которая тождественна на всём множестве кроме подмножества и Обозначается Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: .Перестановку можно представить в виде графа. Граф содержит ребро от вершины
к вершине если , то есть элемент переходит в после применения перестановки . Тогда циклы перестановки соответствуют циклическим путям в графе.