bulgakov

02. Инверсии и чётность перестановок

Мы уже знаем, что перестановка — это список чисел 1,2,…,n1,2,\ldots,n без повторений. Теперь научимся считать инверсии и по ним определять чётность перестановки.

Когда пара нарушает порядок

Определение 22.2. В списке a=(i1,…,in)a=(i_1,\ldots,i_n) возьмём два места t<kt<k. Если число слева больше числа справа, то пара образует инверсию, или нарушение порядка:

t<k,it>ik.t<k,\qquad i_t>i_k.

Здесь сравниваются не соседние места обязательно. Например, в (4,1,2,6,3,5)(4,1,2,6,3,5) числа 44 и 33 образуют инверсию, хотя между ними стоят другие числа. А пара 11 и 66 инверсии не образует: меньшее число записано левее большего.

Чтобы найти все инверсии, идём слева направо и для каждого числа считаем меньшие числа справа. Для перестановки (4,1,2,6,3,5)(4,1,2,6,3,5) получаем:

  • справа от 44 меньше его числа 1,2,31,2,3 — три инверсии;
  • справа от 11 меньших чисел нет; справа от 22 — тоже;
  • справа от 66 меньше него числа 3,53,5 — ещё две;
  • справа от 33 и 55 новых инверсий нет.

Итак, инверсии — это (4,1)(4,1), (4,2)(4,2), (4,3)(4,3), (6,3)(6,3) и (6,5)(6,5); всего s=5s=5. Мы записали пары в порядке появления чисел в списке. Если бы мы считали только соседние пары, ответ получился бы неверным.

Определение 22.3. Перестановка называется чётной, если число её инверсий ss чётно, и нечётной, если ss нечётно. Поскольку 55 нечётно, перестановка (4,1,2,6,3,5)(4,1,2,6,3,5) нечётная. У списка (1,2,…,n)(1,2,\ldots,n) инверсий нет, значит, он чётный.

Почему обмен двух чисел всегда меняет чётность

Теорема 22.1. Если поменять местами любые два числа перестановки и оставить все остальные на местах, чётность изменится на противоположную.

Сначала поменяем соседние числа. Их взаимный порядок изменится: если между ними была инверсия, она исчезнет; если инверсии не было, она появится. Положение каждой другой пары относительно этих двух чисел остаётся тем же. Следовательно, общее число инверсий изменится ровно на 11 или −1-1. Чётность обязательно поменяется.

Теперь пусть обмениваются числа на местах tt и kk, где t<kt<k, а расстояние между местами равно d=k−td=k-t. Можно сдвинуть первое число вправо с помощью dd соседних обменов. Затем сдвинуть второе число влево с помощью d−1d-1 соседних обменов. В результате именно эти два числа поменяются местами, а все промежуточные вернутся на исходные места. Число соседних обменов равно

d+(d−1)=2d−1.d+(d-1)=2d-1.

Это нечётное число. Каждый соседний обмен меняет чётность, поэтому после нечётного числа шагов итоговая чётность противоположна исходной.

Например, обменяем 11 и 44 в (1,2,3,4)(1,2,3,4). Получим (4,2,3,1)(4,2,3,1). Сам обмен можно разложить на пять соседних:

(1,2,3,4)→(2,1,3,4)→(2,3,1,4)→(2,3,4,1)→(2,4,3,1)→(4,2,3,1).(1,2,3,4)\to(2,1,3,4)\to(2,3,1,4)\to (2,3,4,1)\to(2,4,3,1)\to(4,2,3,1).

У начального списка 00 инверсий, у конечного 55: (4,2)(4,2), (4,3)(4,3), (4,1)(4,1), (2,1)(2,1), (3,1)(3,1). Число инверсий при обмене несоседних элементов может измениться больше чем на единицу; теорема утверждает именно изменение чётности.

Проверь себя

  1. Сколько перестановок можно составить из 1,2,31,2,3? Является ли (2,1,2)(2,1,2) перестановкой этих чисел?
  2. Найди все инверсии в (3,1,4,2)(3,1,4,2) и определи её чётность.
  3. Из (3,1,4,2)(3,1,4,2) получили (3,2,4,1)(3,2,4,1) обменом двух чисел. Какой должна стать чётность? Проверь подсчётом.
Показать решение

1. 3!=63!=6. Список (2,1,2)(2,1,2) не подходит: число 22 повторено, а 33 отсутствует.

2. Инверсии (3,1)(3,1), (3,2)(3,2) и (4,2)(4,2). Их три, поэтому перестановка нечётная.

3. После обмена 11 и 22 перестановка должна стать чётной. В (3,2,4,1)(3,2,4,1) четыре инверсии: (3,2)(3,2), (3,1)(3,1), (2,1)(2,1) и (4,1)(4,1).

ПрактикаЗагружаем тест…