Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 16. Комбинаторика-2. Перестановки.

На этом занятии мы более подробно рассмотрим комбинаторный объект - перестановки. Напомним, что перестановкой из N элементов (еще говорят порядка N) называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно P_N = N!

Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говоит, что на i место нужно поставить a_i элемент множества, где a_i - i-тый элемент перестановки. Например, множество {Красный,Зеленый,Синий} перестановка (1,3,2) переведет в множество {Красный,Синий,Зеленый}.
// Перестановка порядка N является биективным отображением N-элементного множества X на себя.

Тождественной перестановкой называется перестановка, которая не изменяет порядок элементов множества (отображает каждый элемент сам на себя). Такая перестановка обозначается ε = (1,2,3,...,N).

Произведением перестановок π и σ называется композиция (т.е. последовательное применение) этих перестановок: (π*σ)(X) = π(σ(X)).
Легко показать, что произведение перестановок тоже является перестановкой, причем если φ = πσ, то φ[i] = π[σ[i]].
Обратите внимание, что πσ <> σπ.
Обозначим πⁿ = π*π*...*π (n раз).
Заметим, что επ = πε = π, т.е. произведение перестановок некоммутативно.

Обратной перестановкой к перестановке π называется такая перестановка π^-1, что ππ^-1 = π^-1π = ε.

Утверждение. Обратная перестановка существует и единственна.

Степенью перестановки называется минимальное натуральное число k такое, что π^k = ε

Утверждение. Степень перестановки конечна.

Инверсией перестановки называется пара целых чисел (i, j) из диапазона от 1 до N, таких что i < j, а π[i] > π[j].

Четностью перестановки называется четность числа инверсий данной перестановки.

Транспозицией называется обмен местами любых двух элементов перестановки.

Элементарной транспозицией называется транспозиция двух соседних элементов.

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

Пусть дана перестановка π порядка N. Построим ориентированный граф из N вершин, где дугами соединим вершины i и π[i]. В полученном графе из каждой вершины выходит ровно одна дуга, и в каждую вершину входит так же ровно одна дуга. Значит данный граф представляет собой объединение циклов и петель. Пусть мы применили нашу перестановку π к некоторому упорядоченному множеству X. Расставим элементы этого множества в вершины построенного графа. i-й элемент поставим в i-ю вершину. В результате применения перестановки каждый элемент переместится вдоль дуги, выходящей из вершины, где он находится. Таким образом, по каждой перестановке мы можем однозначно построить соответствующий ей граф, а по графу восстановить перестановку.