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