Изменения

Пусть <tex>\pi</tex> {{---}} перестановка порядка из <tex>n</tex>элементов, и <tex>\{a_i\}</tex> {{---}} множество некоторых объектов, занумерованных числами от одного <tex>1</tex> до <tex>n</tex>. Тогда '''результатом действия перестановки''' на этот набор объектов назовём множество объектов <tex>\{b_i\}</tex>, занумерованных числами от одного до <tex>n</tex>, причём <tex>b_i = a_{\pi_i}</tex>.

Обозначим за <tex>A</tex> множество (не пронумерованных) объектов <tex>\{a_1, \dots, a_n\}</tex>. Поскольку перестановку можно рассматривать как отображение <tex>\pi \colon \{1, \dots, n\} \to \{a_1, \dots, a_n\}</tex>, а нумерацию как отображение <tex>\alpha \colon \{1, \dots, n\} \to A</tex>, то [[Файл:Permutation_action.png|400px|thumbДействие_группы_на_множестве|right|Иллюстрация действия действие перестановки]]можно определить как композицию отображений <tex>\alpha \circ \pi</tex>.

Обозначим за Например, рассмотрим множество <tex>A= (a, b, c, d)</tex> множество (не пронумерованных) объектов и перестановку <tex>\{a_1pi = \langle 3, 4, \dots1, a_n2 \}rangle</tex>. Поскольку перестановку можно рассматривать как отображение Тогда результат действия <tex>\pi \colon \{1, \dots, n\} \to \{1, \dots, n\}</tex>, а нумерацию как отображение на <tex>\alpha \colon \{1, \dots, n\} \to A</tex>, то действие перестановки можно определить как композицию отображений {{---}} упорядоченное множество <tex>\alpha \circ \pi(A) = (c, d, a, b)</tex>. Если рассмотреть [[Основные_определения_теории_графов|граф]] перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру.

Например, рассмотрим множество <tex>A = (a, b, c, d)</tex> и перестановку <tex>\pi = \langle 3, 4, 1, 2 \rangle</tex>[[Файл:Permutation_action. Тогда результат png|400px|frame|center|Иллюстрация действия <tex>\pi</tex> на <tex>A</tex> {{---}} упорядоченное множество <tex>\pi(A) = (c, d, a, b)</tex>. Если рассмотреть граф перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру.]]

[[Файл:cycles.gif{{Определение|150px|right|thumb|Изображение перестановки в виде графа]]definition= '''Циклом ''' длины <tex>~l</tex> называется такая перестановка <tex>\pi,</tex> которая тождественна на всём множестве <tex>X,</tex> кроме подмножества <tex>\{x_1,x_2,\dots,x_l\}\subset X</tex> и <tex>\pi(x_l)=x_1</tex>, <tex>\pi(x_i)=x_{i+1}.</tex> . Обозначается <tex>(x_1,x_2,\dots,x_l)</tex>. }}[[Файл:cycles.gif|150px|right|frame|Изображение перестановки в виде графа]]Перестановку можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: <tex>(1, 5, 2)(3, 6)(4)=\langle 5,1,6,4,2,3\rangle </tex>.  Перестановку можно представить в виде графа. Граф содержит ребро от вершины <tex>x_i</tex> к вершине <tex>x_j</tex> если <tex>\pi(x_i) = x_j</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе.

Пусть <tex>k</tex> — степень перестановки. Граф перестановки разбит на циклы, и для того, чтобы какой-то элемент прошёл по своему циклу один раз, нужно возвести перестановку в степень <tex>l</tex>, где <tex>l</tex> — длина цикла. Если элемент проходит цикл несколько раз и возвращается на своё место, то можно сделать вывод о том, что перестановка возводится в степень кратную <tex>l</tex>. Тогда только в том случае, когда <tex>k</tex> делится на длины всех циклов, все элементы вернутся на свои места, а наименьшее такое <tex>k</tex> — это НОК длин всех циклов. }} 

Действительно, в таком случае по вышеупомянутому <tex>\pi^2 = i</tex>. Домножив на <tex>\pi^{-1}</tex> получим <tex>\pi^{-1} = \pi</tex>. }}

|definition=Дана перестановка <tex>\pi</tex> порядка из <tex>n</tex>элементов, требуется найти все циклы в ней. }}

*[[Действие группы на множествеТеорема Кэли]]