Условие
Определите чётность перестановки (2,1,4,3). Объясните, почему её нельзя получить из (1,2,3,4) нечётным числом обменов двух элементов.
Решение по шагам
Инверсия — пара позиций i<j с pᵢ>pⱼ. Здесь это пары (2,1) и (4,3), всего две. Чётность числа инверсий чётная, поэтому знак перестановки равен +1.
Один обмен двух элементов меняет знак перестановки. Два обмена — первой пары и второй пары — явно строят нужный порядок. Любая другая цепочка обменов должна иметь ту же чётность, иначе её знак был бы −1 вместо +1.
Проверка результата
Прямой просмотр шести пар даёт ровно две инверсии. Цикловое разложение (1 2)(3 4) содержит две транспозиции и подтверждает знак.
Типичная ошибка
Число элементов, стоящих не на своих местах, не определяет чётность. У трёхциклов тоже несколько неправильных мест, но их знак положителен.
Что даёт этот метод
Знак перестановки связывает сортировку, циклы и определитель. Для цикла длины k он равен (−1)ᵏ⁻¹.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.