В этой статье мы обсудим с разных сторон такое важное понятие, как знак перестановки. Перестановки играют важную роль в разных разделах математики, прежде всего в алгебре и комбинаторике. Знак (чётность) перестановки — это её важнейшая характеристика. На ней, в частности, основана теория определителей.
Перестановкой конечного множества называется любое его биективное (т. е. взаимно однозначное) соответствие на себя. Перестановку часто записывают в виде таблицы: в верхней строке — аргументы, в нижней — значения функции. Например,
— перестановка на множестве , при которой
,
и т. д. Как правило, природа переставляемых элементов не важна, и их считают числами . Перестановок
элементов всего
.
Перестановки можно перемножать в смысле композиции (как обычные функции), справа налево, при этом снова получается перестановка. Все перестановки на элементах образуют группу
. Она называется симметрической группой. Кто знает, почему, пишите в комментариях. И заодно про знакопеременную группу
. Автор знает :)
Действие перестановки можно наглядно изобразить: отметим вершины
и нарисуем стрелку от
к
, если
(в случае
рисуем петлю). Получим ориентированный граф, в котором из каждой вершины выходит одно ребро и в каждую вершину входит одно ребро. Этот граф распадается на циклы. Тем самым, перестановка
представляется в виде произведения независимых циклов. Неподвижные элементы считаются циклами длины 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) — это .
Автор: Андрей Канунников, к. ф.-м. н., мехмат МГУ, преподаватель ШАД Хелпер