logo search
КЛ

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

Взаимно однозначное отображение конечного упорядоченного множества из n элементов на себя называется подстановкой n- й степени.

Пример.

□ Рассмотрим подстановку пятой степени

.

Здесь осуществляется отображение: число 1 первой строки переводится в число 3 второй строки; число 2 первой строки переводится в число 1 второй строки; число 3 – в 5; число 4 переводится в 4, как говорят, остается на месте; число 5 – в 2. ■

Часто подстановку задают только нижней строкой .

Подстановку, при которой на месте остаются все элементы, называют тождественной :

.

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

Пример. Найти произведение подстановок

□ Имеем

Здесь в первой подстановке 1 переходит в 2, а во второй подстановке 2 переходит в 1. Следовательно, в результирующей подстановке 1 будет переходить в 1. Аналогично поступают и с другими элементами. ■

Можно перемножать только подстановки одинаковой степени (совместимые ). Умножение подстановок n-й степени при некоммутативно.

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

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

Можно видеть, что результаты умножения не совпадают : . ■

Подстановки на множестве М = {1, 2, … ,n } образуют группу относительно операции произведения. Действительно, справедливы следующие утверждения:

1. Для любых двух подстановок элементов множества М = {1, 2, … ,n } произведение есть однозначно определенная подстановка;

2. Произведение подстановок ассоциативно, но не коммутативно:

;

3. Единичным элементом группы является тождественная подстановка :

;

4. Для любой подстановки существует обратная подстановка , т.е. если то существует обратная подстановка , при этом .

Группа подстановок на множестве М ={1,2,…, n} называется симметрической группой п-й степени и обозначается через Sn. Порядок симметрической группы п-й степени (число ее (группы) элементов) равен n!.

Пример.

□ Элементы симметрической группы S3 :

Порядок группы S3 равен 3! = 6. ■

Если в матрице подстановки элементов множества М={1,2, … ,n}

встречаются два столбца, для которых si < sj , ti > tj ( или si > sj , ti < tj ), то такая пара столбцов называется инверсией подстановки .

Подстановка называется четной или нечетной в зависимости от того, четно или нечетно число встречающихся в ней инверсий.

Пример. □ Пусть − число инверсий подстановки , то для подстановки из предыдущего примера будем иметь:

Подстановки − нечетные, − четные, тождественная подстановка не является четной или нечетной. ■

Неподвижной точкой подстановки называется элемент , для которого .

Например, в подстановках группы S3 ( см. выше ) имеет три неподвижные точки; − одну неподвижную точку 3; точку 2; и − не имеют неподвижных точек; − одну, равную 1.

Если матрицу подстановки перестановкой столбцов можно привести к виду

то задает взаимно однозначное отображение

множества на себя, которое называется циклом длины r и обозначается

Каждой неподвижной точке соответствует цикл длины 1. Каждую подстановку можно однозначно представить в виде произведения циклов, не имеющих общих элементов.

Пример. □ Данные подстановки можно записать в виде произведения следующих циклов:

■