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

Мы получили два эквивалентных определения определителя третьего порядка (формулы (4) и (5)). С помощью (4) определитель 3-го порядка вводится с помощью определителей второго порядка (разложение по столбцу). При этом легко проверяется, что все столбцы равноправны. Аналогично рекуррентным образом можно определить определитель n-го порядка (определитель квадратной матрицы n-го порядка), т.е.

=

= (7)

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

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

Определение 5. Перестановкой из n чисел (или n символов) называется расположение этих чисел (или символов) в любом определённом порядке (без повторений).

Теорема 1. Число перестановок из n символов равно n!

Доказательство. Составляя перестановку, в качестве первого её элемента можно выбрать точно n символов. Если первый элемент выбран, то в качестве второго элемента можно выбрать любой из оставшихся (n – 1) символов. Следовательно, первые два места можно заполнить n×(n – 1 ) способами. Если два места в перестановке уже заполнены, то на третье место можно поставить любой из оставшихся (n – 2) символов. Следовательно, первые три места можно заполнить n×(n – 1)×(n – 2 ) способами. Продолжая этот процесс, получим, что все n мест в перестановке можно заполнить n×(n – 1)×(n – 2)×…×3×2×1 = n! способами.

Говорят, что числа к и р образуют в перестановке (…к…р…) инверсию, если к > р, но в перестановке к стоит раньше р. Перестановка называется чётной, если она содержит чётное число инверсий. Перестановка называется нечётной, если она содержит нечётное число инверсий.

Пример. 1) Перестановка (9, 7, 1, 3, 4, 8, 5, 2, 6) чётная. В ней число 9 образует инверсии со всеми стоящими за ней числами, их 8. Число 7 образует новые инверсии со всеми стоящими за ней числами, кроме числа 8, их 6. Число 1 не образует ни одной новой инверсии. Числа 3 и 4 образуют по одной новой инверсии с числом 2. Число 8 образует ещё инверсии с 5, 2 и 6, их 3. Число 5 образует инверсию с числом 2. Итак, получается 8 + 6 + 1 + 1 + 3 + 1 = 20 инверсий.

2) Перестановка ( 2, 1, 3, 5, 4, 6, 9, 8, 7) нечётная. В ней инверсии образуют пары чисел 2 и 1, 5 и 4, 9 и 8, 9 и 7, 8 и 7. Получилось 5 инверсий.

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

Доказательство. Пусть в перестановке символы к и р меняются местами. При этом возможны два случая.

1) Символы к и р в данной перестановке стоят рядом, т.е. (…к, р …). После транспозиции получится перестановка (….р, к …). Если к и р составляли инверсию в данной перестановке, то после инверсии они уже не будут составлять инверсию и наоборот. Число инверсий, которые к и р составляли в данной перестановке с остальными символами, не изменится. Следовательно, число инверсий изменится на 1, т.е. чётность перестановки изменится.

2) Символы к и р в данной перестановке стоят не рядом, т.е. (….к,…,р…). После транспозиции получится перестановка (…р,…,к…). Число инверсий, которые к и р составляли в данной перестановке с символами, стоящими перед к и после р, не изменится. Если между к и р стоят m символов, то переставить к и р можно следующим образом: переставить к последовательно с каждым из этих m символов, затем переставить к и р, затем в обратном порядке переставить р с каждым из этих m символов. Получим 2m + 1 транспозиций соседних символов. По доказанному каждая из них меняет чётность перестановки. Итак, чётность перестановки изменилась.

Следствие. При n > 1 число чётных перестановок равно числе нечётных перестановок и равно 0,5×n!.

Определение 6. Подстановкой из n символов ( или подстановкой n-ой степени) называется любое взаимнооднозначное отображение множества этих символов на себя.

Элементы данного множества будем обозначать 1, 2, …, n. Подстановка А может быть записана так: если число к переходит в число a_к, то А = . Если в записи подстановки А некоторые столбцы поменять местами, то получится то же самое отображение данного множества, т.е. та же подстановка. Например,

А = = .

Запись подстановки А = будем называть стандартной. Всякую подстановку можно записать в стандартном виде. Верхнюю и нижнюю строки подстановки можно рассматривать как перестановки. Подстановка А называется чётной, если её верхняя и нижняя строки есть перестановки одинаковой чётности, т.е. общее число инверсий в них – чётное. В противном случае А называется нечётной. Так как перестановка столбцов равносильна транспозиции как в верхней так и в нижней строке, то при перестановке столбцов чётность подстановки не изменится, поэтому чётность подстановки можно вычислять по её стандартному виду и в этом случае она совпадает с чётностью нижней строки.

Подстановка Е = называется тождественной или единичной.