Подстановки
проверено
Подстановка
Определение 1. Произвольное взаимно однозначное отображение множества первых натуральных чисел называется подстановкой1) -го порядка.
Замечание 1. Часто подстановки называют перестановками.
Обычно подстановку изображают следующим образом: , что задает образы всех элементов: , и так далее. Также используют запись .
Пример 1. Подстановку можно записать также в виде , так как в обоих случаях мы имеем отображение , , .
Определение 2. Элемент подстановки называется действительно перемещаемым, если .
Пример 2. В подстановке два действительно перемещаемых символа: 1 и 3.
Операция умножения на подстановках определяется как композиция отображений, причем знак композиции обычно опускают
.
Транспозиции и циклы
Определение 3. Циклической подстановкой2), или циклом3) называется такая подстановка , что при повторении ее достаточное число раз всякий из действительно перемещаемых ею символов может быть переведен в любой другой из этих символов. Для обозначения цикла используют запись , где — число действительно перемещаемых символов подстановки, которое называется длиной цикла4).
Пример 3. В подстановке
действительно перемещаемыми символами являются 1, 3, 4, 5, 6. Выберем любой из них, например, 3. , . Поэтому цикл можно записать как .
Определение 4. Циклы называются независимыми5), если они не имеют общих действительно перемещаемых символов.
Предложение 1. Любая подстановка из может быть разлжена в произведение попарно независимых циклов. Такое представление определено однозначно с точностью до порядка перемножения циклов.
Пример 4. — разложение подстановки в произведение попарно независимых циклов.
Определение 5. Цикл длины 2 называется транспозицией6).
Предложение 2. Каждая подстановка может быть представлена в виде произведения транспозиций.
В отличие от представления в произведение попарно независимых циклов, представление в виде произведения транспозиций может не быть единственным.
Пример 5. Подстановка может быть разложена в произведение транспозиций или .
Четность подстановки
Определение 6. Пусть — разложение подстановки в произведение транспозиций. Тогда число называется знаком7)(четностью) подстановки . Подстановка называется четной8), если и нечетной9) в противном случае.
Предложение 3. Четность подстановки не зависит от способа разложения подстановки в произведение транспозиций.
Предложение 4. Для двух подстановок и четность их произведения равна произведению четностей:
.
Предложение 5. Пусть — цикл длины . Тогда его четность равна .
Определение 7. Пусть — разложение подстановки в произведение независимых циклов длин . Число называется декрементом10) подстановки .
Предложение 6. Пусть — разложение подстановки в произведение независимых циклов длин . Тогда четность подстановки вычисляется по формуле
.
Пример 6. Любая транспозиция — это нечетная подстановка. Подстановка из примера 4 нечетная, так как декремент — нечетное число.
Пример 7. Любая подстановка, в разложении которой на независимые циклы все циклы имеют нечетные длины , четна, так как ее декремент — это сумма четных чисел .