12

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

Пусть дано некоторое конечное множество N, состоящее из п элементов. Каждому из этих элементов может быть присвоен номер от 1 до п. В рассматриваемых в дальнейшем задачах свойства элементов множества N не будут существенны, и будем считать, что элементами множества служат сами числа 1, 2, ¼, п.

Перестановкой степени п называется упорядоченный набор (i₁,i₂,¼,i_n) п чисел 1,2, ¼,п (или п различных элементов).

Число различных перестановок из п элементов равно произведению 1×2×¼×п, которое обозначается п! (читается “эн-факториал”). Действительно, в качестве i₁ можно взять любой из п элементов (любое из чисел 1,×2,×¼,×п), для чего можно выбрать п вариантов. Если элемент i₁ выбран, то в качестве i₂ можно взять любой из оставшихся п – 1 элементов, то есть число различных вариантов выбора i₁, i₂ равно п(п –1) и т. д.

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

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

Доказательство проведём по индукции. Утверждение, очевидно, справедливо при п = 2. Предположим, что утверждение справедливо при п – 1, и покажем, что тогда оно справедливо при п. Пусть задана изначальная перестановка i₁,i₂,¼,i_n. Рассмотрим все перестановки из п элементов, в которых на первом месте стоит i₁. Таких перестановок (п – 1)!, и их можно упорядочить любым способом с помощью конечного числа транспозиций, так как, согласно предположению индукции, доказываемое утверждение справедливо для числа элементов п – 1. В последней из полученных перестановок из п элементов поменяем местами элемент i₁ с любым из остальных элементов, например, с i₂. Начиная с полученной перестановки, можно упорядочить любым способом все перестановки, у которых на первом месте стоит i₂. Действуя таким образом, можно перебрать все перестановки из п элементов.

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

Пусть элементами перестановки являются числа 1,2, ¼,п.. Числа i и j составляют инверсию в данной перестановке, если i > j и при этом i стоит в этой перестановке раньше j. Перестановка называется чётной, если она содержит чётное число инверсий и нечётной – в противоположном случае.

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

Доказательство. Очевидно, что чётность перестановки после транспозиции двух рядом стоящих элементов изменится. Пусть теперь первый из тех элементов перестановки, который будет “участвовать” в транспозиции (в дальнейшем будем называть его первым элементом), стоит на i-м месте в перестановке, а второй “участник транспозиции” (в дальнейшем называемый вторым элементом) занимает место с номером i + k. Чтобы поменять местами эти элементы будем действовать следующим образом. Сначала последовательно поменяем местами первый элемент с k – 1 элементами, стоящими между первым и вторым, так, что первый элемент станет соседним элементом слева для второго (тем самым проведём k – 1 транспозиций двух соседних элементов). Затем поменяем местами первый и второй элементы (ещё одна транспозиция двух соседних элементов). Теперь осталось поставить второй элемент на место первого, для чего опять нужно провести k – 1 транспозиций второго элемента с элементами, первоначально находившимися между первым и вторым. Таким образом, проведено 2(k – 1) + 1 транспозиций двух стоящих рядом элементов. Тем самым чётность перестановки была изменена нечётное количество раз, что и доказывает теорему.

При число чётных перестановок степени п равно числу нечётных, то есть равно п!/2. Действительно, все п! перестановок можно упорядочить так, что каждая последующая получается из предыдущей одной транспозицией. Таким образом, две соседние перестановки будут иметь противоположные чётности. Из того, что п! при – число чётное, следует справедливость утверждения.

Если записать одну под другой две перестановки п-й степени, заключая полученные две строки в скобки, например при п = 5,

(1)

то две перестановки, записанные таким образом, определяют взаимно однозначное отображение, которое каждому из натуральных чисел 1,2,3,4,5 ставит в соответствие одно из этих же натуральных чисел, причём разным числам ставятся в соответствие разные числа. Такая запись двух перестановок называется подстановкой п-й степени. Подстановку можно записать в другом виде, переставив местами её столбики. Так подстановки

и

являются другими записями подстановки (1). От одной записи подстановки к другой можно перейти несколькими транспозициями столбиков. В частности, всякая подстановка п-й степени может быть записана в виде

, (2)

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

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

Если подстановка записана в виде (2), то чётность подстановки будет определяться чётностью перестановки , стоящей в нижней строке. Отсюда следует, что число чётных подстановок равно числу нечётных и равно п!/2.