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

Пусть – конечное множество из n элементов. Перенумеруем элементы множества : 1, 2, …, n. Обозначим , т.е. номера элементов множества рассматриваем как элементы другого множества М. Эти числа (номера) можно располагать в различном порядке. Если они идут по возрастанию 1, 2,…, n, то такое расположение называется естественным (каноническим).

Определение. Любое расположение чисел 1, 2,…, n в некотором определенном порядке называется перестановкой из n чисел (символов, индексов).

Пример. . Элементы множества М допускают 6 перестановок:

1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2.

В общем случае перестановка из n чисел записывается так:

, где если .

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

Доказательство. Рассмотрим перестановку из n чисел в общем виде . Символ i ₁ можно выбрать n способами. Зафиксируем его. Символ i ₂ можно выбрать n -1 способами, а пару (i ₁ , i ₂) можно выбрать n (n -1) способами. Зафиксируем пару (i ₁ , i ₂). Символ i ₃ можно выбрать n -2 способами, а тройку можно выбрать n (n -1)(n -2) способами. Зафиксируем эту тройку и т.д.

Символ i_n можно выбрать единственным способом, а все символы можно выбрать n (n -1)(n -2)…1= n! способами. ■

Определение. Говорят, что символы i и j образуют инверсию (беспорядок) в перестановке, если , но i стоит в перестановке раньше j.

Пример. Сколько инверсий в перестановке . Укажем все инверсии в перестановке:

4 и 2; 3 и 1; 2 и 1; 4 и 3; 4 и 1.

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

Пример.

1. (1, 2, 3, 4) - четная перестановка;

2. (4, 2, 3, 1) – нечетная, 5 инверсий.

Определение. Взаимное перемещение двух символов перестановки называется транспозицией перестановки.

Пример. .

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

Доказательство. Рассмотрим первый случай, когда транспонируемые индексы стоят рядом: . В обеих перестановках символы i и j образуют одни и те же инверсии с символами, остающимися на месте. Поэтому тип перестановки зависит только от взаимного расположения i и j. Если i < j, то число инверсий в перестановке после транспозиции на единицу больше числа инверсий в исходной транспозиции. Если i>j, то число инверсий в перестановке после транспозиции на единицу меньше числа инверсий в исходной транспозиции. И в том и в другом случаях тип перестановки меняется на противоположный.

Рассмотрим второй случай, когда между транспонируемыми индексами стоит s>0 элементов, т.е.:

.

Транспонируем i и i ₁, затем i и i ₂, …, i и i _s, i и j. После этих (s+1) транспозиций исходная перестановка примет вид . Далее транспонируем j и i _s, затем j и i _s-1,…, j и i ₁. Получаем требуемую перестановку за (2s+1) транспозицию. Итак, для перехода от исходной перестановки к полученной необходимо осуществить (2s+1) транспозицию соседних индексов. Число (2s+1) нечетно, поэтому тип перестановки меняется нечетное число раз, следовательно, исходная и полученная перестановки имеют противоположные типы. ■

Следствие 1. Если , то число четных перестановок из n символов равно числу нечетных и равно .

Доказательство. Пусть среди перестановок из n символов р четных и q нечетных. Во всех перестановках произведем транспозицию каких-либо двух символов (например, первого и второго). Получим те же самые перестановок, но их запись в другом порядке, одинаковых нет. Но среди этих перестановок будет уже q четных и р нечетных. Следовательно, , . ■