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

ГЛАВА I. ТЕОРИЯ ОПРЕДЕЛИТЕЛЕЙ

Считаем известным определение бинарного отношения, отображения, кортежа длины n. Напомним, что отображение j: А®В называется сюръективным, если

" bÎB $aÎA (j(a)=b).

Отображение j: А®В называется взаимно однозначным или инъективным, если

" а₁, а₂ÎА (а₁¹ а₂ Þ j(а)¹j(а₂)).

И наконец, отображение j: А®В называется биекцией, если оно одновременно сюръективно и инъективно. Отображение множества М в себя называется преобразованием множества М.

Определение. Любой упорядоченный кортеж длины n называется перестановкой из n элементов.

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

Доказательство

При доказательстве будем использовать метод математической индукции по числу элементов.

1. При n=1 теорема верна, что очевидно.

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

Перестановку можно также определить как строго линейно упорядоченное множество.

Примеры: Из элементов множества {1,2,3,4,5} можно составить 5!=120 различных перестановок. Например, J₁=(1,2,3,4,5); J₂=(1,2,4,3,5)...

В общем виде перестановки принято записывать

J=(I₁, I₂ ,..., I_k).

Определение. Если в перестановке J символы I_к и I_в таковы, что I_к > I_в, но I_к предшествует I_в, то говорят, что символы I_к и I_в образуют инверсию.

Пример: В перестановке J=(3,2,1,4,5) символы 3 и 2, 3 и 1, 2 и 1 образуют инверсию.

Определение. Если в перестановке J число инверсий четно, то такая перестановка называется четной, если число инверсий нечетно, то перестановка называется нечетной.

Определение. Если в перестановке J поменять местами два символа, то такое преобразование перестановкиназывается транспозицией.

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

Доказательство

Для доказательства рассмотрим случай, когда транспонируемые символы стоят рядом. Пусть

J₁=(I₁, I₂,..., I_k-1, I, J, I_k+2,..., I_n).

В результате транспозиции получим перестановку:

J₂=(I₁, I₂,..., I_k-1, J, I, I_k+2,..., I_n).

Очевидно, для любого элемента I_s верно следующее: если J и I_s составляли инверсию в J₁, они составляют инверсию и в J₂, аналогично, если I_s и I составляли инверсию в J₁, то они составляют инверсию и в J₂, так как их взаимное расположение не изменилось. Таким образом, общее число инверсий, которые образуют символы I и J с остальными символами, одинаково для J₁ и J₂, а сами символы I и J, если они образовывали инверсию в J₁, то не образуют инверсии в J₂ и наоборот. То есть в любом случае число инверсий в перестановках J₁ и J₂ отличается на 1, следовательно, эти перестановки имеют разную четность.

Теперь пусть между транспонируемыми элементами I и J находится некоторое количество символов

J₁=(I₁, I₂,..., I_k-1, I, e₁, e₂,..., e_m, J,..., I_n),

J₂=(I₁, I₂,..., I_k-1, J, e₁, e₂,..., e_m, I,..., I_n).

чтобы поменять местами элементы I и J, сначала элемент I будем менять местами последовательно с элементами e₁, e₂,..., e_m, J, для этого нам придется сделать m+1 транспозицию, а затем элемент J будем менять местами с элементами e_m, е_m-1,..., e₂, e₁, то есть совершим еще m транспозиций. Таким образом, чтобы поменять местами элементы I и J, нам пришлось сделать m+1+m=2m+1 транспозицию, а так как каждая следующая транспозиция меняет четность перестановки, то 2m+1 транспозиция изменит четность перестановки J₁.

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

Следствие. Для n³2 число четных перестановок равно числу нечетных перестановок и равно