§3. Перестановки.

Пусть X — непустое множество элементов произвольной природы, так как природа элементов для нас несущественна, то в случае конечного множества считаем X =.

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

Пример:

Если X = , то (2,5,3,4,1) - перестановка множества X.

Перестановку элементов множества X обозначают , причем среди (i = 1,2,…, n)нет равных.

Определение 2. Две перестановки множества X называются равными, если у них на одинаковых местах стоят одинаковые элементы.

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

◄ Докажем эту теорему индукцией по числу . При 1 имеется одна перестановка, т.е. 1!.

Пусть >1 и число различных перестановок, которые можно составить из заданных () элементов, равно . Всякая перестановка данных элементов с фиксированным первым числом а имеет вид:

,

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

Определение 3. Будем говорить, что в перестановке чисел два числа образуют инверсию если >, но i < j. В противном случае образуют порядок.

Пример:

В перестановке (1 3 4 2) инверсии: 4,2 ; 3,2 , а остальные пары образуют порядок.

Определение 4. Количество пар чисел, образующих инверсию в перестановке, называют числом инверсий данной перестановки. Отображение XX будем называть преобразованием множества X.

Пусть множество X состоит не менее чем из двух элементов X.

Определение 5. Преобразование множества Х называют транспозицией элементов и , если ,, .Такое преобразование обозначают .

Определение 6. Перестановку называют четной, если число инверсий в ней четно, и нечетной в противном случае.

Теорема 2. Однократное применение транспозиции к перестановке изменяет ее характер четности на противоположный.

◄ Пусть имеется перестановка . Применим к ней транспозицию , получим . Рассмотрим несколько случаев:

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

2. Пусть и не стоят рядом . От к можно перейти следующим способом: менять с рядом стоящим элементом дойти до и перегнать на место . Всего нам придется применить S+1+S=2S+1 транспозиций соседних чисел, где число элементов между и , поэтому характер четности перестановок и различны.►

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

◄ Пусть число четных перестановок равно S, нечетных — T. Если к каждой четной перестановке мы применим транспозицию двух элементов, мы превратим их в нечетные S, аналогично наоборот T T=S

=S+T =2S

S=T=.►

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

◄ Пусть

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

Если , то к перестановке применим транспозицию .В результате получим перестановку . Продолжаем этот процесс получаем требуемое.►

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

Пример:

(1, 2, 3, 4)

(3, 1, 4 ,2)

(1,2,3,4) (3,2,1,4) (3,1,2,4) (3,1,4,2).

(6) (7)

Такая последовательность транспозиций не однозначна (это может быть не самый короткий путь перехода от одной перестановки к другой).