Вычисление порядка перестановки в группе перестановок

Для нахождения порядка перестановки достаточно разложить её в произведение независимых циклов (циклических перестановок). Тогда порядок перестановки будет равен НОК длин всех циклов.

Лемма:

Для того, чтобы перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы каждый цикл был пройден целое число раз.

Доказательство:

[math]\triangleright[/math]

Для того, чтобы при перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы любой ее элемент перешел сам в себя, что равносильно тому, что цикл, в который он входит, пройден целое число раз (если пройден не целое, то элемент не перейдет сам в себя)

[math]\triangleleft[/math]

Теорема (О порядке перестановки, НОК):

Порядок перестановки равен НОК длин всех её независимых циклов.

Доказательство:

[math]\triangleright[/math]

Поскольку при умножении на себя каждый цикл сдвигается на 1, то для того, чтобы перестановка перешла сама в себя, необходимо и достаточно, в силу леммы, чтобы степень перестановки делилась на все длины циклов. Минимальным таким числом является НОК длин циклов.

[math]\triangleleft[/math]