02. Инверсии и чётность перестановок
Мы уже знаем, что перестановка — это список чисел без повторений. Теперь научимся считать инверсии и по ним определять чётность перестановки.
Когда пара нарушает порядок
Определение 22.2. В списке возьмём два места . Если число слева больше числа справа, то пара образует инверсию, или нарушение порядка:
Здесь сравниваются не соседние места обязательно. Например, в числа и образуют инверсию, хотя между ними стоят другие числа. А пара и инверсии не образует: меньшее число записано левее большего.
Чтобы найти все инверсии, идём слева направо и для каждого числа считаем меньшие числа справа. Для перестановки получаем:
- справа от меньше его числа — три инверсии;
- справа от меньших чисел нет; справа от — тоже;
- справа от меньше него числа — ещё две;
- справа от и новых инверсий нет.
Итак, инверсии — это , , , и ; всего . Мы записали пары в порядке появления чисел в списке. Если бы мы считали только соседние пары, ответ получился бы неверным.
Определение 22.3. Перестановка называется чётной, если число её инверсий чётно, и нечётной, если нечётно. Поскольку нечётно, перестановка нечётная. У списка инверсий нет, значит, он чётный.
Почему обмен двух чисел всегда меняет чётность
Теорема 22.1. Если поменять местами любые два числа перестановки и оставить все остальные на местах, чётность изменится на противоположную.
Сначала поменяем соседние числа. Их взаимный порядок изменится: если между ними была инверсия, она исчезнет; если инверсии не было, она появится. Положение каждой другой пары относительно этих двух чисел остаётся тем же. Следовательно, общее число инверсий изменится ровно на или . Чётность обязательно поменяется.
Теперь пусть обмениваются числа на местах и , где , а расстояние между местами равно . Можно сдвинуть первое число вправо с помощью соседних обменов. Затем сдвинуть второе число влево с помощью соседних обменов. В результате именно эти два числа поменяются местами, а все промежуточные вернутся на исходные места. Число соседних обменов равно
Это нечётное число. Каждый соседний обмен меняет чётность, поэтому после нечётного числа шагов итоговая чётность противоположна исходной.
Например, обменяем и в . Получим . Сам обмен можно разложить на пять соседних:
У начального списка инверсий, у конечного : , , , , . Число инверсий при обмене несоседних элементов может измениться больше чем на единицу; теорема утверждает именно изменение чётности.
Проверь себя
- Сколько перестановок можно составить из ? Является ли перестановкой этих чисел?
- Найди все инверсии в и определи её чётность.
- Из получили обменом двух чисел. Какой должна стать чётность? Проверь подсчётом.
Показать решение
1. . Список не подходит: число повторено, а отсутствует.
2. Инверсии , и . Их три, поэтому перестановка нечётная.
3. После обмена и перестановка должна стать чётной. В четыре инверсии: , , и .
