В этой статье мы обсудим с разных сторон такое важное понятие, как знак перестановки. Перестановки играют важную роль в разных разделах математики, прежде всего в алгебре и комбинаторике. Знак (чётность) перестановки — это её важнейшая характеристика. На ней, в частности, основана теория определителей.

Перестановкой конечного множества называется любое его биективное (т. е. взаимно однозначное) соответствие на себя. Перестановку часто записывают в виде таблицы: в верхней строке — аргументы, в нижней — значения функции. Например,

— перестановка на множестве , при которой ,
и т. д. Как правило, природа переставляемых элементов не важна, и их считают числами . Перестановок элементов всего .

Перестановки можно перемножать в смысле композиции (как обычные функции), справа налево, при этом снова получается перестановка. Все перестановки на элементах образуют группу . Она называется симметрической группой. Кто знает, почему, пишите в комментариях. И заодно про знакопеременную группу . Автор знает :)

Действие перестановки можно наглядно изобразить: отметим вершины и нарисуем стрелку от к , если (в случае рисуем петлю). Получим ориентированный граф, в котором из каждой вершины выходит одно ребро и в каждую вершину входит одно ребро. Этот граф распадается на циклы. Тем самым, перестановка представляется в виде произведения независимых циклов. Неподвижные элементы считаются циклами длины 1 и в записи обычно опускаются. Пример:

Все перестановки делятся на чётные и нечётные. По какому принципу? Есть несколько подходов.

Подход через инверсии. Инверсия в перестановке — это число таких пар , что , но . Чётность перестановки — это чётность числа всех её инверсий. Например, для перестановки

все инверсии суть: , , , , , , . Всего 7 штук, поэтому перестановка (3) нечётная.

Но как с помощью данного определения найти чётность перестановки (1)? Минус этого подхода в том, что в определении перестановки вовсе не предполагается какой-то порядок на множестве, а понятие инверсии основано на порядке.

Отметим, что если фигурки в (1) занумеровать так, как они идут в первой строке, то (1) превратится в (3). Но, что если фигурки занумеровать как-то по другому? Число инверсий может измениться, хотя можно доказать, что их чётность не изменится. Знатоки, конечно, сразу объяснят, почему: при другой нумерации получится сопряжённая перестановка.

Знак перестановки — это число , если перестановка чётная, и число , если она нечётная; обозначения: . Вот главное свойство знака:

При подходе через инверсии оно не очевидно; доказательство требует некоторой возни.

Наконец отметим, что подсчёт инверсий требует время : их наибольшее число равно

и реализуется для перестановки

В то же время любой программист скажет, что определить чётность перестановки легко за линейное время .

Всех этих недостатков лишён подход через транспозиции. Транспозицией называется цикл длины 2 — своего рода простейшая перестановка.

Теорема-определение. Любую перестановку можно представить в виде произведения транспозиций. Чётность их числа в любом представлении одинакова и называется чётностью перестановки.

Всякую перестановку можно представить в виде произведения независимых циклов, а каждый цикл — в виде произведения транспозиций, например, так:

Почему никакую перестановку нельзя одновременно представить в виде произведения чётного и нечётного числа транспозиций? Потому что при умножении перестановки на транспозицию число независимых циклов в её разложении (включая циклы длины 1) меняется на 1. Действительно, если в разложении перестановки элементы и были в одном цикле, то в перестановке этот цикл распадётся на два:

(что верно и при ). А если и были в разных циклах, то эти циклы сольются в один, о чём свидетельствует то же равенство (7), только его надо справа умножить на .
Есть и другое красивое доказательство, использующее многочлен

Надо показать, что он меняет знак при любой транспозиции переменных. Порядок на элементах (переменных) здесь вводится только в доказательстве. (Знатоки, конечно, узнали определитель Вандермонда, но помнят, что обычно определители строятся через перестановки, а не наоборот. Впрочем, можно извратиться...)

Пример. Перестановка (5) есть произведение транспозиций:

Согласно (6) чётность цикла противоположна его длине. Кстати, цикл длины нельзя представить в виде произведения транспозиций. Попробуйте это доказать, модифицировав приведённое выше доказательство. Более общо, перестановку из , которая раскладывается в произведение независимых циклов, можно представить в виде произведения транспозиций и никак не меньше. Это число называется декрементом перестановки. Его преимущество над числом в том, что декремент не зависит от приписывания неподвижных элементов. Так, декремент транспозиции равен 1 при любом .

Итак, вот преимущества подхода через транспозиции.

Грамотное определение, не зависящее от порядка. Например,

— нечётная перестановка.

Разложение в произведение транспозиций (равно как и разложение на независимые циклы) требует линейное время .

Основное свойство знака (4) очевидно!

P.S. По-видимому, понятие чётности перестановки возникло при решении известной игры "Пятнашки" (почему нельзя переставить 14 и 15 по правилам).

P.P.S. Не говорите "подстановки". Это явно не подходящий в данном контексте термин применяется только в некоторой русскоязычной литературе, причём, в основном, учебной. В англоязычной литературе — только permutations и никаких substitutions. Подстановка (substitution) — это .

Автор: Андрей Канунников, к. ф.-м. н., мехмат МГУ, преподаватель ШАД Хелпер