[Список тем]

Операция композиции

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

Записываем

Тогда

Пример

Пример:

f = (i₁ i₂ ... i_k)
f ^-1 = (i_k i_k-1 ... i₂ i₁)

Пример: (1 2 3 4 ) ( 3 2 5 ) ( 1 6 2 ) = ( 1 6 5 4 )
1→6, 6→6, 6→6
6→2, 2→5, 5→5
5→5, 5→3, 3→4
4→4, 4→4, 4→1
2→1, 1→1, 1→2

Определение!
Порядок подстановки - наименьшее положительное число k, такое, что f k равно тождественной подстановке.

Пример:

1→2→3→1→2→3→1
2→3→1→2→3→1→2
3→1→2→3→1→2→3
4→4→4→4→4→4→4
5→6→5→6→5→6→5
6→5→6→5→6→5→6
пoрядок=6.

Методика определения порядка:

Если функция f записана как произведение независимых циклов, то порядок функции f - наименьшее общее кратное длины циклов.

Рассмотрим предыдущий пример:

f = (1 2 3) (5 6), длины равны соответственно 2 и 3. НОК(3,2)=6, порядок=6.

Пример: f=(1 3 5 7)(2 4 6)(8 9 10 11 12)(13 14). НОК(4,3,5,2)=60, порядок=60.

Числа f(i) и f(j) находятся в инверсии, если i < j и f(i) > f(j).
Подстановка f считается четной, если число инверсий четное.
Подстановка f считается нечетной, если число инверсий нечетное.

Пример:

Свойство
Композиция двух подстановок одинаковой четности - четная, различной четности - не четная.

Как найти четность:

I-й способ: подсчитать число инверсий.
II-й способ: использовать циклы нечетной длины, как четные, а четной - наоборот.

Тогда f = c₁ ... c_k- произведение циклов и четность равна четности числа циклов четной длины.

Пример: f = (1 5 7 9 11)(3 6 4 5)(1 2)(3 4 5 6 7)(1 2 3 4),

где (3 6 4 5) - четная длина, (1 2) - четная длина, (1 2 3 4) - четная длина, следовательно функция f нечетная.

[Список тем]