Симметрическая группа: перестановки и композиция

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

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

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

Характер представления группы: определение и примеры
Что такое характер представления группы, как найти его по матрицам и таблице характеров S₃ и разложить представление на неприводимые с помощью ортогональности.

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

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

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

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