Подстановки

Определение. Операция, переводящая одну перестановку в другую, состоящую из тех же чисел, называется подстановкой.

Обычно подстановку записывают в виде матрицы из двух строк. Например, символ

обозначает подстановку, в которой 3 переходит в 1, 2 переходит в 3, 1 переходит в 5, 5 переходит в 4, 4 переходит в 2. Отметим, что одну и ту же подстановку можно записать многими способами. Например, символы

, , , ,

обозначают подстановку, переводящую 1 в 3, 2 в 1, 3 в 2. Всего получилось 6 = 3! способов записи одной и той же подстановки. Очевидно, подстановку из n чисел можно записать n! способами. Пусть u – число инверсий в верхней строке подстановки, а v – число инверсий в нижней строке подстановки, w = u + v общее число инверсий в строках подстановки.

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

Если два столбца подстановки поменять местами, то ее четность не изменится, так как одновременно меняется четность обеих перестановок. Например, подстановки

,

обе четные (здесь меняли местами первый и второй столбцы).

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