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

Пусть дано некоторое конечное множество 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,,п на себя будем называть подстановкой порядка п (степени п). Подстановку можно записать в другом виде, переставив местами её столбики. Так подстановки

и

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

, (2)

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

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

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