Доказательство. 1. В единичной перестановке инверсий нет; поэтому

1. В единичной перестановке инверсий нет; поэтому .

2. Пусть – множество инверсий относительно , а – множество инверсий относительно .

Легко видеть, что если , то . Следовательно, между множествами устанавливается взаимнооднозначное соответствие

.

3. Пусть – множество инверсий относительно ,

– множество инверсий относительно ,

– множество инверсий относительно : .

Тогда надо доказать, что , т.е. . Таким образом, надо показать, что |A|+|B|+|C| – четное число.

Пусть ,

,

,

.

Введем следующее обозначение: пусть - это множество пар . Тогда справедлива следующая множественная схема:

Между множествами существует взаимнооднозначное соответствие : .

Поэтому из картинки видно , т.е. четное число. ▄

Следствие. .

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

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

Теорема 2. Транспозиция является нечетной перестановкой.

Доказательство. Вычислим число инверсий. Инверсиями являются пары , где ; пары , где ; и пара . Их всего будет , т.е. нечетное число. ▄

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

Упражнение. Как вычисляется произведение ?

Замечание. , т.е. эти транспозиции совпадают.

Теорема 3. Каждая перестановка является произведением конечного числа транспозиций.

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

Пример.

т.е. .

Аналогично в общем случае.

Пусть на r -ом шаге поменяются местами . Тогда ввиду замечания . ▄

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

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