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

Для определения и изучения определителей порядка n рассмотрим некоторые понятия, относящиеся к конечным множествам.

Пусть дано некоторое конечное множество N, состоящее из n элементов. Эти элементы пронумеруем с помощью первых n натуральных чисел 1, 2, …, n. Числа 1, 2, …, n можно помимо их естественного порядка упорядочить многими другими способами.

Определение. Всякое расположение чисел 1, 2,…, n в некотором определенном порядке называется перестановкой из n чисел (символов).

Число различных перестановок из n символов равно произведению (читается n – факториал). Если в некоторой перестановке поменять местами какие-либо два символа, не обязательно стоящие рядом, а все остальные символы оставить на месте, то получим новую перестановку. Такое преобразование называется транспозицией.

Пусть , , …, – некоторая перестановка чисел 1, 2,…, n. Говорят, что в данной перестановке числа и образуют инверсию (беспорядок), если > и i<j. Общее число инверсий в перестановке , ,…, обозначим через inv(, ,…, ).

Перестановка называется четной, если inv(, ,…, ) – четное число или ноль и нечетной в противоположном случае.

Пример. Определить четность перестановки 5, 3, 1, 6, 4, 2.

Решение. Число 5 образует четыре инверсии с числами 3, 1, 4, 2. Число 3 образует две инверсии с числами 1 и 2. Число 1 не образует инверсий. Число 6 образует 2 инверсии с числами 4 и 2. Число 4 образует одну инверсию с числом 2. Общее число инверсий inv (5, 3, 1, 6, 4, 2)=9, следовательно, данная перестановка является нечетной.

Очевидно, что перестановка 1, 2,…, n четна при любом n, так как общее число инверсий inv (1, 2, ….., n)=0.

Теорема. Всякая транспозиция меняет четность перестановки.

Определение. Всякое взаимно однозначное отображение множества первых n натуральных чисел на себя называется подстановкой n –ой степени.

Всякая подстановка может быть записана при помощи двух перестановок

,

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

Существуют различные формы записи подстановок, которые получают транспозицией нескольких столбцов.

Всякая подстановка n –ой степени может быть записана в виде

,

т.е. с естественным расположением чисел в верхней строке.

Очевидно, что при такой форме записи подстановки отличаются друг от друга перестановками, стоящими в нижней строке. Поэтому число различных подстановок n –ой степени равно числу перестановок из n символов, т.е. равно n!.

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

Покажем, что четность подстановки не зависит от формы ее записи. Рассмотрим произвольную запись некоторой подстановки

.

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

Поиск по сайту: