§ 6. ПОДСТАНОВКИ

1. Умножение подстановок. Напомним (см. §1, п.6, определение 17), что подстановкой на множестве символов называется всякое взаимно однозначное отображение множества на себя:

,

где . Эта запись означает, что , , … , . При перемене мест столбцов матрицы подстановка не изменяется.

Определение 1. Произведением подстановок (взаимно однозначных отображений) называется результат их последовательного выполнения:

.

Пример: .

Поясним вычисления. Сначала в результирующей подстановке записываем первую строчку. Затем, последовательно находим образы элементов первой строки. Первая подстановка 1 отображает в 2, а вторая подстановка 2 отображает в 3. Следовательно, в произведении образ 1 есть 3, под 1 ставим 3. Теперь находим образ символа 2. Первая подстановка 2 отображает в 3, а вторая подстановка 3 отображает в 1. Следовательно, в произведении образ 2 есть 1, под 2 ставим 1. И так далее.

Множество всех подстановок n символов обозначается . Отображение , при котором всякой упорядоченной паре подстановок ставится в соответствие их произведение , является бинарной операцией, которая называется умножением подстановок.

Основные свойства умножения подстановок

1. Умножение подстановок ассоциативно.

Доказательство. Пусть

, , ,

докажем, что . Имеем:

;

*

2. Роль единицы при умножении подстановок играет тождественная подстановка . Для любой подстановки имеем .

3. Для любой подстановки существует обратная подстановка такая, что . В самом деле, легко проверить, что если , то .

2. Разложение подстановки в произведение независимых циклов.

Рассмотрим подстановку . Замечаем, что она символы 1,2,3 перемещает последовательно каждый ¾ в следующий, а последний ¾ в первый. Остальные символы отображаются каждый в себя. Такая подстановка называется циклом и записывается кратко в виде (123). Дадим общее определение цикла.

Определение 2. Циклом или циклической подстановкой называется подстановка, которая отображает некоторое подмножество символов последовательно каждый ¾ в следующий, а последний ¾ в первый, а остальные символы оставляет на месте. Такой цикл записывается кратко в виде . Символы, не входящие в запись цикла, преобразуются каждый в себя.

Примеры циклов в . Одноэлементные циклы: , двухэлементные циклы: , трехэлементные циклы: , , . Заметим, что циклы и не содержат общих перемещаемых символов, в силу чего их называют независимыми циклами.

Определение 3. Циклы называются независимыми, если они не содержат общих перемещаемых символов.

Теорема 1. Всякую подстановку можно представить в виде произведения независимых циклов.

Доказательство. Дадим алгоритм такого представления.

1. Формируем новый цикл: открываем скобку и записываем новый символ.

2. Находим образ записанного символа. Если он совпадает с первым символом формируемого цикла, то ставим ответную скобку, говорим: «цикл замкнулся» и переходим к пункту 4.

3. Записываем найденный образ рассматриваемого символа и переходим к пункту 2.

4. Если есть новый символ, то переходим к пункту 1.

5. Разложение в произведение независимых циклов закончено. *

Пример. Разложим данную подстановку в произведение независимых циклов, указывая шаги алгоритма:

(1 (13 (134 (134) ¾ цикл замкнулся; (134)(2 (134)(2) ¾ цикл замкнулся; (134)(2)(5 (134)(2)(56 (134)(2)(56) ¾ цикл замкнулся; разложение в произведение независимых циклов закончено.

Таким образом, =(134)(2)(56). Поскольку одноэлементный цикл ¾ это тождественная подстановка, то в записи ответа одноэлементный цикл можно отбросить.

Ответ: =(134)(56).

3. Разложение подстановки в произведение транспозиций.

Определение 4. Двухэлементный цикл называется транспозицией.

Основные свойства транспозиций

1. Произведение транспозиции на себя равно тождественной подстановке.

Доказательство. Например, . *

2. Если ¾ транспозиция, то .

Доказательство вытекает из равенства . *

3. Для транспозиций имеет место формула .

Доказательство вытекает из равенства . *

Теорема 2. Всякую подстановку можно представить в виде произведения транспозиций.

Доказательство. Поскольку всякую подстановку можно представить в виде произведения независимых циклов, то достаточно уметь всякий цикл раскладывать в произведение транспозиций. Если это не одноэлементный цикл, то делается это так: = . Тождественная подстановка . *

Пример. =(134)(56)=(13)(14)(56).

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

Лемма. Пусть подстановка разложена в произведение независимых циклов. Если ее умножить на транспозицию, то количество независимых циклов изменится на единицу.

Доказательство. Разложим подстановку a в произведение независимых циклов и умножим ее на транспозицию . Понятно, что это умножение никак не влияет на те циклы, которые не содержат символов i и j. Рассмотрим, как изменятся те циклы, которые содержат эти символы. При этом возможны два случая.

1. Символы i и j содержатся в одном из независимых циклов. Покажем, что в этом случае при умножении подстановки на транспозицию этот цикл распадется на два независимых цикла. Действительно,.

2. Символы i и j содержатся в двух независимых циклах. Покажем, что в этом случае при умножении подстановки на транспозицию эти циклы «склеиваются» в один. Действительно, .

Итак, при умножении подстановки на транспозицию количество независимых циклов в ее разложении в первом случае увеличивается на единицу, а во втором уменьшается также на единицу. *

Теорема 3. При любом разложении подстановки в произведение транспозиций четность числа транспозиций постоянна.

Доказательство. Пусть дана подстановка на множестве символов . Пусть разложена в произведение m независимых циклов , , и в произведение k транспозиций , , т.е. :

.

Тогда . По предыдущей лемме, при каждом умножении подстановки на транспозицию число независимых циклов m изменяется на единицу, причем количество таких изменений k. Следовательно, в последнем произведении число независимых циклов равно . Пусть в этой сумме среди слагаемых ровно единиц, тогда в ней слагаемых, равных 1, и вся сумма равна . С другой стороны, ¾ n независимых циклов. Следовательно, , откуда . Таким образом, четность числа k совпадает с четностью числа , а это число однозначно определяется данной подстановкой. Итак, четность числа k постоянна для данной подстановки. 

Определение 5. Подстановка называется четной, если она представима в виде произведения четного числа транспозиций, и называется нечетной, если она представима в виде произведения нечетного числа транспозиций.

Определение 6. Будем называть знаком четной подстановки +1, а знаком нечетной подстановки 1.

Знак подстановки a обозначается (читается сигнум a).

Пример. Чтобы найти знак подстановки ,

представим ее сначала в виде произведения независимых циклов, а потом ¾ в произведение транспозиций:

.

Подстановка a оказалась нечетной, следовательно, .