Перестановка n элементов — это отображение, которое переставляет эти элементы. Например, перестановка может быть представлена в виде последовательности, где каждый элемент указывает, на какую позицию изначального множества он переместится.

Разложение на циклы

Перестановку можно разложить на дисjoint (независимые) циклы. Этот метод позволяет представить перестановку как множество циклов, где каждый цикл описывает, как элементы "перемещаются" друг к другу. Чтобы найти циклы в перестановке, вы можете начать с любого элемента и следовать, куда он перемещается, пока не вернетесь к исходному элементу. Это образует один цикл. Затем вы переходите к любому элементу, который не был посещен, и повторяете процесс, пока не будут обработаны все элементы.

Например, рассмотрим перестановку из 5 элементов, записанную как ( \sigma = (3, 1, 2, 5, 4) ). Это означает, что 1-й элемент переходит на 3-е место, 2-й на 1-е, 3-й на 2-е и так далее.

Циклы в этой перестановке будут:

Начнем с элемента 1: ( 1 \to 3 \to 2 \to 1 ) (цикл (1 3 2))Другие элементы: ( 4 \to 5 \to 4 ) (цикл (4 5))

Таким образом, ( \sigma ) представляется как ( (1 \, 3 \, 2)(4 \, 5) ).

Порядок перестановки

Порядок перестановки — это наименьшее положительное число ( k ), такое что ( \sigma^k ) (перестановка, примененная ( k ) раз) равна тождественной перестановке (где каждый элемент остается на своем месте).

Порядок перестановки, разложенной на циклы, можно найти следующим образом:

Найдите длину каждого цикла.Порядок перестановки равен наименьшему общему кратному (НОК) всех длин циклов.

В нашем примере:

Цикл (1 3 2) имеет длину 3.Цикл (4 5) имеет длину 2.

Теперь находим НОК(3, 2):

НОК(3, 2) = 6.

Таким образом, порядок нашей перестановки ( \sigma ) равен 6. Это означает, что если мы применим перестановку 6 раз, все элементы вернутся на свои места.