Чётность подстановки: инверсии и знак

Чётность подстановки отвечает на вопрос: нужно чётное или нечётное число обменов двух элементов, чтобы получить заданный порядок? Разложений на обмены бывает много, но их количества всегда совпадают по чётности. Это свойство позволяет присвоить подстановке знак или и использовать его в формулах и алгоритмах. Ниже разберём инверсии, проверим пример двумя способами и выясним, почему ответ не зависит от выбранного пути.
В калькуляторе начните с и меняйте соседние элементы. Столбцы показывают вклад каждой позиции в число инверсий, а итог сразу меняется после обмена.
Что именно переставляется
Подстановка множества - взаимно однозначное отображение этого множества на себя. Удобно перечислить образы в порядке исходных элементов: , где . Например, означает , , , . Каждое число от 1 до 4 встречается ровно один раз.
Такой список можно также понимать как порядок различных фишек. Важно заранее договориться о нумерации и исходном порядке: чётность относится к конкретной подстановке относительно этого порядка. Вопрос о числе возможных упорядочиваний и отличие от выбора без учёта порядка подробно рассмотрены в статье о сочетаниях и перестановках.
Транспозиция - обмен ровно двух элементов при неизменных остальных. Любую подстановку можно получить из тождественной последовательностью таких обменов. Если их число чётно, подстановка чётная; если нечётно - нечётная. Ноль тоже чётен, поэтому тождественная подстановка чётная.
На видео первые две фишки меняются местами и возвращаются обратно. После каждого соседнего обмена чётность переключается: в исходном списке три инверсии, после обмена - две.
Как считать инверсии
Инверсия - пара позиций , в которой значения стоят в обратном порядке: . Число инверсий обозначим . Тогда
При чётном знак равен , при нечётном - . Чётность зависит от количества пар, а не от суммы их значений. Для примера последовательно посмотрим на элементы справа:
- у 3 меньшие справа - 1 и 2: две инверсии;
- у 1 меньших справа нет;
- у 4 меньший справа - 2: одна инверсия;
- у последнего элемента справа элементов нет.

Итак, , а : подстановка нечётная. На диаграмме калькулятора высоты столбцов именно . Обмен первых элементов даёт и оставляет пары и : всего две, знак .
Проверка начинается с корректности ввода: повторяющееся значение или пропущенное число в списке образов означает, что задана не подстановка этого множества. Задачи с неразличимыми объектами требуют другой постановки; их подсчёт разобран в статье о перестановках с повторениями.
Почему обмен меняет знак
Сначала рассмотрим соседние значения и . При их обмене порядок каждой из остальных пар не меняется: любой третий элемент остаётся либо слева от обоих, либо справа от обоих. Зато ровно одна пара меняет порядок, поэтому число инверсий увеличивается или уменьшается на единицу. Значит, его чётность переключается.
Обмен двух несоседних позиций тоже переключает чётность. Если между ними элементов, где - расстояние между позициями, то такой обмен можно выполнить за соседних обменов: провести один элемент до другого, затем вернуть второй к освободившемуся месту. Число нечётно, поэтому после всей последовательности чётность снова меняется ровно один раз по модулю двух.
Теперь причина независимости разложения ясна. Начинаем с тождества, у которого ноль инверсий. Каждая транспозиция переключает чётность числа инверсий. Если до одной и той же подстановки дошли за и за транспозиций, то и , и имеют ту же чётность, что и . Поэтому : одного чётного и одного нечётного разложения для одной подстановки не существует.
Как не пропустить пару при ручном подсчёте
Практический способ проверки - идти слева направо и записывать вклад каждого элемента отдельно. Для каждого числа сравните его со всеми числами строго правее и отметьте только меньшие. Затем сложите получившиеся количества. Так одна и та же пара встретится ровно один раз: у неё есть единственный левый элемент. Если перестановка длинная, удобно сделать строку подсчётов под исходной записью и проверить, что последний вклад всегда равен нулю.
Другой наглядный способ - расположить исходные номера в одном ряду, их возможные образы в другом и соединить каждый номер с его образом. Два отрезка пересекаются внутри схемы, когда порядок их концов в верхнем и нижнем рядах противоположен. Именно это условие и определяет инверсию. Нумерация в обоих рядах должна идти в одном направлении, иначе смысл пересечения изменится. Для нашего примера получается три пересечения, как и три пары в списке.
Полезна и оценка результата: число инверсий неотрицательно и не превосходит числа всех пар позиций. У возрастающего списка инверсий нет; у убывающего каждая пара является инверсией. Между этими крайностями могут находиться и чётные, и нечётные ответы. Например, два разных списка с одинаковой чётностью не обязаны иметь одинаковое число инверсий: достаточно, чтобы разность этих чисел делилась на два.
Проверка по циклам
Цикл отправляет каждый элемент в следующий, а последний - в первый. Остальные элементы он не меняет. При соглашении, что в произведении отображений правый множитель применяется первым, цикл длины раскладывается в транспозиций:
Разложим наш пример: , то есть . Это цикл длины четыре, поэтому достаточно трёх транспозиций: . Три - нечётное число, в согласии с подсчётом инверсий. Цикл длины два сам является транспозицией, а цикл длины один чётен.
Если разложение подстановки состоит из непересекающихся циклов длин , включая неподвижные точки как циклы длины один, то сумма длин равна и
Это особенно удобно для длинной записи циклами. Если неподвижные точки опущены, сначала восстановите их число либо сложите только по выписанным циклам: неподвижные точки добавляют ноль.
Композиция, обратная подстановка и определитель
При последовательном применении двух подстановок количества транспозиций в их разложениях складываются. Поэтому знак произведения равен произведению знаков:
Две нечётные подстановки в композиции дают чётную, а чётная и нечётная - нечётную. Порядок композиции важен для самой итоговой подстановки, хотя произведение её знаков от порядка не зависит. Поскольку есть тождество со знаком , обратная подстановка имеет тот же знак, что и .
Знаки подстановок входят в формулу определителя: для каждого выбора по одному элементу из каждой строки и каждого столбца множители берутся со знаком соответствующей подстановки. Это согласуется с тем, что обмен двух строк меняет знак определителя. Другие правила и их геометрический смысл разобраны в статье про свойства определителя.
Как найти чётность в программе
Прямой алгоритм перебирает все пары и прибавляет единицу, когда . Для элементов он проверяет пар: время работы , дополнительная память для одного счётчика - . Если нужен только знак, вместо полного счётчика можно переключать один бит при каждой найденной инверсии.
Для больших массивов число инверсий считают за при сортировке слиянием. Когда очередной элемент правой половины меньше текущего элемента левой, он меньше и всех оставшихся элементов этой отсортированной левой половины; их количество прибавляется к счёту разом. Память зависит от реализации; обычное слияние использует дополнительной памяти. Сам факт сортировки недостаточен: алгоритм должен учитывать пары, пересекающие границу половин. Для сравнения подходов к оценке времени и памяти полезен материал о пирамидальной сортировке.
Частые ошибки
- Считать инверсиями соседние пары только. Пара может занимать любые позиции ; в примере тоже нужно учесть.
- Путать число инверсий с минимальным числом произвольных обменов. Эти числа могут отличаться; совпадает их чётность. Для соседних обменов минимальное число равно числу инверсий.
- Судить по последней цифре записи или длине цикла. Сначала найдите нужный показатель: число инверсий либо сумму по циклам.
- Считать тождество нечётным. Оно получается за ноль обменов и имеет знак .
FAQ
Может ли одна подстановка иметь и чётное, и нечётное разложение?
Нет. Любой обмен меняет чётность числа инверсий, поэтому число обменов в каждом разложении имеет одну и ту же чётность.
Сколько чётных подстановок в ?
При ровно половина, то есть . Фиксированный обмен связывает каждую чётную подстановку с одной нечётной и при повторении возвращает исходную. При единственная подстановка чётная.
Меняется ли чётность при обращении подстановки?
Нет. Знак обратной подстановки равен знаку исходной, поскольку их композиция тождественна и произведение знаков равно .
Коротко
Чётность подстановки определяется чётностью числа её инверсий или транспозиций в любом разложении. Для инверсий три, поэтому знак равен ; цикл подтверждает ответ тремя транспозициями. Каждый обмен переключает знак, а при композиции знаки перемножаются.
Читайте также

Алгоритм LZ77: сжатие с помощью ссылок назад
Алгоритм LZ77 на пошаговом примере: как скользящее окно находит повторы, что означают расстояние и длина, как работает перекрытие и от чего зависит размер результата.

Числа Белла: разбиения множества и формула
Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

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

Дерево двоичного поиска: построение и операции
Дерево двоичного поиска: как устроены узлы, как построить BST по ключам, выполнить обход и удалить элемент, от чего зависит высота и сложность операций.

Доминирующее множество в графе: определение и примеры
Как проверить доминирующее множество графа и найти число доминирования: разбираем путь из шести вершин, полный перебор, жадный подход и типичные ошибки.

Формула Бине: вывод и вычисление чисел Фибоначчи
Разбираем формулу Бине для чисел Фибоначчи: подробный вывод через корни характеристического уравнения, пример вычисления, округление и ограничения точности в программе.