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

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

Утверждение 1. Число всех перестановок n элементов равно .

Доказательство. Действительно, общий вид перестановки из n символов есть i₁, i₂, ..., i_n, где каждое i_s есть одно из чисел 1, 2, ..., n, причем ни одно из этих чисел не встречается дважды. В качестве i₁ можно взять любое из чисел 1, 2, ..., n; это дает n различных возможностей. Если, однако, i₁ уже выбрано, то в качестве i₂ можно взять лишь одно из оставшихся n-1 чисел, т.е. число различных способов выбрать символы i₁ и i₂ равно произведению n(n-1) и т.д.

Таким образом, число перестановок из n символов при n=2 равно 2!=2 (перестановки 12 и 21; в примерах, где n  9, мы не будем разделять переставляемые символы запятыми); при n=3 это число равно 3!=6. С ростом n число перестановок чрезвычайно быстро возрастает; так, при n=10 оно равно 3628800.

Теперь разобьем все n! перестановок n элементов на два класса по признаку, кажущемуся довольно искусственным, но именно это разбиение будет нужно для разумного правила расстановки знаков в определителе.

Пусть ( ₁,  ₂, ...,  _n) - некоторая перестановка чисел 1, 2, ..., n. Говорят, что пара элементов ( _i,  _j), i < j, образует инверсию, если  _i >  _j. Число всех пар элементов перестановки, образующих инверсию, называется числом инверсий в перестановке и обозначается inv( ₁,  ₂, ...,  _n). Так, inv(35142687)=7 (инверсии образуют пары 31, 32, 51, 54, 52, 42, 87).

Перестановки, содержащие четное число инверсий, называются четными, содержащие нечетное число инверсий - нечетными.

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

Утверждение 2. От любой перестановки из n символов можно перейти к любой другой перестановки посредством нескольких транспозиций.

Доказательство. Применим индукцию. Это утверждение справедливо при n = 2; если требуется начинать с перестановки 12, то вторая (а их всего две) 21 получается из первой в результате одной транспозиции. Предположим, что наше утверждение уже доказано для n-1, и докажем его для n. 

Пусть ( ₁,  ₂, ...,  _n) и ( ₁,  ₂, ...,  _n) - две данные перестановки. 

Если  ₁=  ₁, то ( ₂, ...,  _n) и ( ₂, ...,  _n) отличаются только порядком и, в силу предположения об индукции, посредством нескольких транспозиций можно перейти от ( ₂, ...,  _n) к ( ₂, ...,  _n) и, следовательно, от ( ₁,  ₂, ...,  _n) к ( ₁,  ₂, ...,  _n). Пусть теперь  ₁  ₁. Тогда  ₁=  _i при некотором i  1. Сделав в ( ₁,  ₂, ...,  _n) транспозицию ( ₁,  _i), мы придем к новой перестановке, у которой на первом месте находится  _i = ₁. В силу доказанного выше свойства, эта перестановка превращается в ( ₁,  ₂, ...,  _n) посредством нескольких транспозиций. Следовательно, от ( ₁,  ₂, ...,  _n) к ( ₁,  ₂, ...,  _n) можно перейти посредством нескольких транспозиций, что и требовалось доказать.

Заметим, что переход от одной перестановки к другой посредством транспозиций неоднозначен.

Утверждение 3. Всякая транспозиция меняет четность перестановки.

Доказательство. Рассмотрим сначала случай, когда транспонируемые символы i и j стоят рядом, т.е. перестановка имеет вид ..., i, j, ..., где многоточия заменяют те символы, которые не затрагиваются транспозицией. Транспозиция превращает нашу перестановку в перестановку ..., j, i, ..., причем, понятно, в обеих перестановках каждый из символов i, j составляет одни и те же инверсии с символами, остающимися на месте. Если символы i и j раньше не составляли инверсии, то в новой перестановке появляется одна новая инверсия, т.е. число инверсий увеличивается на единицу; если же они раньше составляли инверсию, то теперь она пропадает, т.е. число инверсий на единицу уменьшается. В обоих случаях четность перестановки меняется.

Пусть теперь между транспонируемыми символами i и j расположены s символов, s > 0, т.е. перестановка имеет вид ..., i, k₁, k₂, ..., k_s, j, ... (1)

Транспозицию символов i и j можно получить в результате последовательного выполнения 2s+1 транспозиций соседних элементов. А именно это будут транспозиции, переставляющие символы i и k₁, затем i (уже стоящие на месте символа k₁) и k₂ и т.д., пока i не займет место символа k_s. За этими s транспозициями следует транспозиция, перемещающая символы i и j, а затем s транспозиций символа j со всеми k, после чего j занимает место символа i, а символы k возвращаются на свои старые места. Таким образом, мы нечетное число раз меняли четность перестановки, а поэтому перестановки (1) и ..., j, k₁, k₂, ..., k_s, i, ...

имеют противоположные четности.

Утверждение 4. Число четных перестановок n элементов равно числу нечетных перестановок.

Доказательство. Пусть число четных перестановок равно a, число нечетных равно b. Рассмотрим множество всех четных перестановок. Сделаем в них одну и ту же транспозицию, например, (1,2). Мы получим нечетные перестановки, попарно различные, в количестве a штук. Так как число всех нечетных перестановок равно b, то заключаем, что a  b. Теперь рассмотрим множество всех нечетных перестановок и сделаем в них транспозицию (1,2). Мы получим b четных перестановок и, следовательно, b  a. Из установленных неравенств следует, что a = b, что и требовалось доказать.

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

Определим теперь еще одно понятие, а именно понятие подстановки. 

Подстановкой n-й степени на множестве {1, 2, ..., n} называется взаимно однозначное отображение множества на себя. Удобно задавать подстановку прямым указанием замен для каждого элемента, посредством записи образа под прообразом. Так, запись задает подстановку, которая заменяет элементы 1, 2, 3, 4, 5, соответственно, на 5, 1, 3, 2, 4; порядок расположения ее столбцов безразличен. В такой записи в "числителе" и в "знаменателе" оказываются перестановки. Удобно в "числителе" записывать элементы в натуральном расположении. От одной записи подстановки к другой можно перейти при помощи нескольких транспозиций столбиков. В частности, всякая подстановка на множестве {1, 2, ..., n} может быть записана в виде

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

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

Утвержденние 5. Либо при всех записях подстановки четности верхней и нижней строк совпадают, либо же при всех записях они противоположны.

В первом случае подстановка будет называться четной, во втором - нечетной.

Если подстановка записана в виде (2), т.е. в верхней строке стоит четная перестановка 1, 2, ..., n, то четность подстановки будет определяться четностью перестановки  ₁,  ₂, ...,  _n, стоящей в нижней строке. Отсюда следует

Утверждение 6. Число четных подстановок n-й степени равно числу нечетных, т.е. равно.

Таблица. 1. Генерирование перестановок в лексикографическом порядке