Перестановки. Знак перестановки

1^о. Перестановки, умножение перестановок.

Пусть ­­− произвольное множество из элементов; например,

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

Множество всех перестановок степени обозначается . Каждую перестановку будем в дальнейшем обозначать строчной буквой греческого алфавита: Перестановка изображается двурядным символом (или, другими словами, матрицей размера ):

. (1)

Такой символ обозначает отображение

Замечание. Порядок столбцов в обозначении (1) перестановки не является существенным. А именно, ту же перестановку можно записать в виде

.

Утверждение 1. Число различных перестановок степени равно

Доказательство. В качестве первого элемента можно выбрать любой из элементов, в качестве второго − любой из оставшихся элементов, и т.д. Всего различных возможностей выбора Таким образом, ■

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

Например, если

то

Свойства (умножения перестановок)

1) Ассоциативность умножения, т.е. справедливо

Доказательство. По определению 2, Аналогично, что и требовалось доказать.

2) Если – тождественная перестановка, то выполняется

3) Для любой такая, что Такая перестановка называется обратной к и обозначается

Доказательство. Если

,

то

Упражнение. Доказать единственность обратной перестановки.

Замечание. Произведение перестановок не является коммутативной операцией. Например, в разобранном выше примере

2 ^о. Знак перестановки.

Определение 3. Пусть – перестановка степени и пусть . Тогда пара называется инверсией относительно , если .

Перестановка называется четной, если число инверсий относительно четное, и перестановка называется нечетной, если число инверсий − нечетное.

Знак перестановки – это , где – число инверсий.

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

Таким образом, если – четная, то , и если – нечетная, то .

Пример. . Возможные пары . Их них подчеркнутые – инверсии. Таким образом, , т.е. – четная.