Подстановки.

Определение. Подстановкой - ой степени называется взаимно однозначное отображение множества на себя.

Всякая подстановка может быть представлена при помощи двух перестановок, записанных одна под другой.

,

где .

Подстановка может быть записана неединственным способом.

Пример 5.

Дана подстановка .

Это означает, что двойке соответствует пятерка, единице - четверка и т.д., т.е. . Но ясно, что это же взаимно однозначное соответствие можно получить, меняя в нашей подстановке столбцы местами, т.е.

Перемену столбцов местами можно, в частности, произвести так, что в верхней строке будет стоять перестановка , а вся подстановка примет вид , где .

Число всех подстановок -ой степени, очевидно, равна числу перестановок из элементов, т.е.

Определение. Подстановка называется единичной или тождественнойподстановкой.

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

разные, т.к. в первой из них тройке соответствует двойка, а во второй - тройке соответствует единица.

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

Пример 6.

Пусть .

Тогда есть .

Действительно,

Умножение подстановок некоммутативно. Так, если в рассмотренном выше примере вычислить произведение , то получим

.

Еще раз подчеркнем, что перемножать можно лишь подстановки одинаковой степени.

Из определения единичной подстановки следует, что для любой подстановки .

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

А именно, если

,

т.е. для нахождения обратной подстановки достаточно поменять строки в исходной подстановке.

Подстановка и ей обратная удовлетворяют соотношениям

.

Пусть задана подстановка , где некоторые перестановки.

Определение.Сигнатурой подстановки назовем величину .