Подстановки n-ой степени. Знак подстановки.

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

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

.

Пример. Запишем все подстановки второй и третьей степеней.

n= 2: , – всего 2 подстановки;

n =3: , , , , , – всего 6 подстановок.

Заметим, что подстановки n -ой степени отличаются друг от друга лишь порядком расположения элементов второй строки, а значит, их число равно количеству перестановок n -ой степени – .

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

Обозначение: .

Например, – тождественная подстановка третьей степени.

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

, и , если и , те.

она получена из тождественной перестановкой двух элементов второй строки. Обозначение: .

Например, , , – транспозиции третьей степени.

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

Определение. Произведением подстановок n-ой степени называется их композиция.

Из свойств композиции следует, что произведение подстановок – также подстановка.

Примеры. ,

,

Таким образом, в общем случае !

Определение. Подстановка называется обратимой, если существует такая подстановка , что . При этом подстановка называется обратной для и обозначается .

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

Примеры. , , , , , .

Заметим, что .

Определение. Говорят, что подстановка имеет инверсию, если найдутся такие элементы , что , т.е во второй ее строке нарушен естественный порядок расположения элементов.

Пример. Подсчитаем число инверсий для подстановок третье степени:

: ни одной инверсии; : 1 инверсия;

: 1 инверсия; : 2 инверсии;

: 2 инверсии; – 3 инверсии.

Определение. Подстановка называется четной, если число ее инверсий четно; нечетной – в противном случае.

Обозначение: .

Дата добавления: 2015-11-26