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

1.

Подстановки
Калининград, 2023

2.

Дано множество En 1,2,..., n , n N .
Взаимнооднозначное отображение : En En
множества на себя называется подстановкой
степени n.
Если прообразы (аргументы) расположены в
порядке возрастания, запись подстановки такого
вида называется канонической.
Например, 1 2 3 4 5 6 7 .
6 2 5 3 1 7 4

3.

Чтобы из подстановки получить обратную, нужно
поменять местами образы и прообразы, т.е.
верхнюю и нижнюю строчки, и, если требуется,
привести к каноническому виду.
Например, если 16 22 53 43 15 76 74
, то
1 16 22 53 34 15 76 74 15 22 34 74 53 16 76 .
Обратная подстановка единственная.
Если подстановка записана в каноническом виде,
то первую строчку можно не писать.

4.

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

5.

Порядком подстановки называется наименьшее
e
натуральное число λ, такое что
.
1 2 3 4
Например, для подстановки
λ=3.
2 4 3 1
В подстановке любая перемена двух элементов
второй строки местами называется транспозицией.
Подстановка называется чётной, если число
транспозиций, приводящих эту подстановку к
тождественной, чётно. В противном случае
подстановка называется нечётной.

6.

Пример.
Приведём подстановку σ к тождественной
подстановке с помощью транспозиций.
1 1 2 3 4 5 6
2 1 2 3 4 5 6
3
16 24 33 14 52 65
1 4 3 6 2 5
1 2 3 6 4 5
3 1 2 3 4 5 6
4
1 2 3 4 5 6 .
1 2 3 4 6 5
1 2 3 4 5 6
Чётное число транспозиций (n = 4) указывает на
чётность подстановки.

7.

Пример умножения подстановок:

8.

Спасибо за внимание!
Калининград, 2023