Подстановки, инверсии, транспозиции

Числа i и j образуют в перестановке инверсию, если i > j, но i расположено раньше j. Если число инверсий в перестановке четно, то перестановка называется четной, в противном случае нечетной. Например, перестановка (4 7 1 5 3 6 2) четна, так как число инверсий в ней 12 четно. Для определения числа инверсий в перестановке следует выбрать порядок их подсчета. Проще всего подсчитывать сколько инверсий образует число с последующими числами перестановки:

Inv(4 7 1 5 3 6 2) = 3 + 5 + 0 + 2 + 1+ 1+ 0 = 12.

Операция транспозиции заключается в перемене местами двух элементов перестановки.

Теорема. Одна транспозиция меняет четность перестановки на противоположную.

Доказательство. Теорема очевидна, если операции транспозиция подвергнуты два соседних числа перестановки. Пусть теперь между числами i и j находится s чисел. Для того, чтобы число j оказалось на месте i, его следует поменять местами с соседними s+1раз. А чтобы затем число i заняло место числа j его следует поменять местами с соседними s раз. Всего необходимо произвести операцию транспозиция над соседними числами s+1+s=2s+1нечетное число раз. Следовательно, четность перестановки изменится на противоположную. ■

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

Здесь мы работаем, как это часто делается в комбинаторике, не с самими элементами какого-либо множества, а с их номерами. В верхней строчке-числителе расположены элементы множества, а в нижней строчке-знаменателе расположены те элементы, в которые переходят соответствующие элементы числителя при отображении f,т.е. Конечно, элементы числителя могут быть расположены в ином порядке, чем естественный. Здесь подстановка записана в каноническом виде, когда порядок номеров в числителе естественный. И в числителе и в знаменателе подстановки стоят перестановки n-й степени. Если сумма инверсий в числителе и знаменателе четна, то подстановка называется четной, в противном случае нечетной. При любой замене местами столбцов подстановки ее четность не меняется. Для канонической записи подстановки

Множество всех подстановок n-й степени обозначается через . Число всех подстановок n-йстепени равно n!. Введем на множестве S операцию умножения – композицию отображений. Пример умножения подстановок:

Теорема. Множество всех подстановок n-й степени образует группу относительно операции композиции отображений.

Для доказательства необходимо проверить выполнение всех аксиом группы. ■

Нейтральным элементом является тождественное отображение

Обратным элементом для подстановки является подстановка