EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 8 минут
#симметрическая группа#перестановки#теория групп#циклы#композиция
Симметрическая группа: перестановки и композиция

Симметрическая группа SnS_n состоит из всех перестановок nn различимых элементов. Её операция - последовательное применение перестановок: сначала меняем элементы по одному правилу, затем по другому. На трёх элементах уже видно, что порядок действий способен изменить результат. Разберём, как записывать и перемножать перестановки, находить их циклы и применять эту идею в информатике. Калькулятор покажет, как быстро растёт число элементов группы при увеличении nn.

Что такое перестановка и группа SnS_n

Пусть есть множество X={1,2,…,n}X=\{1,2,\ldots,n\}. Перестановка - биекция из XX в себя: каждому элементу назначен единственный образ, причём каждый элемент множества встречается среди образов ровно один раз. Например, правило 1↦21\mapsto2, 2↦32\mapsto3, 3↦13\mapsto1 переставляет три числа. Его можно записать двумя строками: первая содержит исходные элементы, вторая - их образы.

(123231).\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}.

Множество всех таких правил обозначают SnS_n. Его элементы - сами отображения, а не числа 1,…,n1,\ldots,n. Слово «симметрическая» здесь относится ко всем возможным перестановкам множества; геометрическая симметрия фигуры даёт важный пример, но не является обязательным условием определения.

В ролике фишка хранит номер исходного элемента, а номер места показывает его текущий образ. Сначала меняются места 2 и 3, затем места 1 и 2; обратный ход возвращает исходное расположение.

Фишки последовательно проходят два обмена местами, а затем обратные обмены возвращают их в исходное положение.

Операция группы - композиция отображений. Она замкнута: композиция двух биекций снова биекция. Композиция ассоциативна; тождественная перестановка ee оставляет все элементы на месте; у каждой перестановки есть обратная, отменяющая её действие. Этого достаточно для четырёх аксиом группы. При этом коммутативность не требуется: начиная с S3S_3 её в общем случае нет.

Почему в S3S_3 ровно шесть элементов

Первому элементу можно назначить любой из трёх образов, второму - любой из двух оставшихся, а третьему остаётся один. Поэтому ∣S3∣=3⋅2⋅1=6|S_3|=3\cdot2\cdot1=6. На рисунке каждая строка из трёх ячеек - список образов элементов 1, 2 и 3 в этом порядке.

Шесть различных списков образов трёх элементов: порядок группы S3 равен шести
Шесть различных списков образов трёх элементов: порядок группы S3 равен шести

В общем случае по тому же правилу произведения получаем

∣Sn∣=n!=n(n−1)⋯2⋅1.|S_n|=n!=n(n-1)\cdots2\cdot1.

Например, ∣S4∣=24|S_4|=24, а ∣S8∣=40 320|S_8|=40\,320. Договорённость 0!=10!=1 согласуется с тем, что у пустого множества есть одно отображение в себя. Факториал считает биекции различимых элементов. В задачах на одинаковые буквы число различных видимых слов может быть меньше: подробнее различие объясняется в статье про перестановки с повторениями. Сравнение выбора и упорядочивания дано также в материале о сочетаниях и перестановках.

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

Как перемножать перестановки

В этой статье произведение ab=a∘bab=a\circ b означает: сначала применить bb, затем aa. В других источниках встречается и противоположное соглашение, поэтому при чтении задач его надо уточнять. Возьмём a=(12)a=(12) - обмен 1 и 2, и b=(23)b=(23) - обмен 2 и 3. Проследим каждое число:

  • 1→b1→a21\xrightarrow{b}1\xrightarrow{a}2;
  • 2→b3→a32\xrightarrow{b}3\xrightarrow{a}3;
  • 3→b2→a13\xrightarrow{b}2\xrightarrow{a}1.

Получилось ab=(123)ab=(123): единица переходит в двойку, двойка в тройку, тройка в единицу. Если поменять множители местами, то ba=(132)ba=(132). Уже образ единицы отличается: при abab это 2, при baba - 3. Следовательно, ab≠baab\ne ba, и группа S3S_3 не абелева.

Обратное к произведению находится в обратном порядке: (ab)−1=b−1a−1(ab)^{-1}=b^{-1}a^{-1}. У каждого обмена двух элементов обратная перестановка совпадает с ним самим. Поэтому для примера (ab)−1=ba(ab)^{-1}=ba. Это не формальное правило для перестановки символов: чтобы отменить последовательность действий, приходится отменять последнее действие первым.

Циклы, транспозиции и порядок элемента

Цикл (a1 a2 … ak)(a_1\ a_2\ \ldots\ a_k) отправляет a1a_1 в a2a_2, следующий элемент - в следующий и, наконец, aka_k в a1a_1. Элементы, не указанные в записи, остаются на месте. Двухэлементный цикл называют транспозицией: (12)(12) просто меняет местами 1 и 2.

Любую перестановку можно разложить на непересекающиеся циклы, прослеживая путь каждого ещё не посещённого элемента. Например, правило 1↦21\mapsto2, 2↦12\mapsto1, 3↦43\mapsto4, 4↦54\mapsto5, 5↦35\mapsto3 записывается как (12)(345)(12)(345). Эти циклы действуют на разных элементах и потому коммутируют. Записи (345)(345) и (453)(453) обозначают один цикл: отправная точка записи не меняет отображение. Но (354)(354) задаёт обратное направление и обычно другую перестановку.

Порядок элемента группы - наименьшее положительное число повторений, после которого получается тождественная перестановка. Цикл длины kk возвращает каждый свой элемент через kk шагов, поэтому его порядок равен kk. Для произведения непересекающихся циклов берут наименьшее общее кратное их длин. Так, у (12)(345)(12)(345) порядок lcm⁡(2,3)=6\operatorname{lcm}(2,3)=6: оба цикла впервые одновременно вернутся к началу после шести применений.

Чётность и знакопеременная подгруппа

Любой цикл длины kk раскладывается в k−1k-1 транспозиций. Например, при выбранном порядке композиции (123)=(13)(12)(123)=(13)(12). Разложение на транспозиции неоднозначно, но чётность их количества всегда одна и та же. Перестановку называют чётной или нечётной в зависимости от этой чётности. Тождественная перестановка чётна: для неё можно взять ноль транспозиций.

Другой способ вычисления - посчитать инверсии в списке образов: пары позиций i<ji<j, для которых p(i)>p(j)p(i)>p(j). У списка (2,3,1)(2,3,1) две инверсии, (2,1)(2,1) и (3,1)(3,1), значит перестановка чётная. Произведение двух чётных перестановок чётно; обратная к чётной тоже чётна. Поэтому чётные элементы образуют подгруппу AnA_n, называемую знакопеременной. При n≥2n\ge2 в ней n!/2n!/2 элементов: умножение на фиксированную транспозицию попарно связывает чётные и нечётные перестановки.

Как найти циклы по таблице образов

Рассмотрим конкретную перестановку пяти элементов: пусть образы единицы, двойки, тройки, четвёрки и пятёрки равны соответственно трём, пяти, одному, четырём и двум. Начнём с единицы: она переходит в тройку, а тройка возвращается в единицу. Первый цикл замкнулся. Теперь возьмём наименьший ещё не посещённый элемент - двойку: она переходит в пятёрку, которая возвращается в двойку. Четвёрка остаётся на месте, так что её обычно не пишут. Получаем произведение двух непересекающихся транспозиций. Его порядок равен двум, поскольку оба обмена отменяются после второго применения.

Такой алгоритм работает и для длинных списков. Надо только помечать посещённые элементы и продолжать, пока каждый не встретится в некотором цикле. В корректной перестановке путь обязательно замкнётся на исходном элементе текущего цикла: два разных элемента не могут иметь один и тот же образ. Если в таблице повторяется образ, прежде чем искать циклы, проверьте условие биективности: исходное правило не является элементом симметрической группы.

Зачем это информатике и геометрии

Перестановки описывают переименование вершин графа, перестановку индексов массива и переназначение позиций. Например, при изменении порядка строк таблицы последовательность индексов задаёт биекцию; две последовательные перестановки заменяются одной композицией. Направление отображения важно: правило «старый индекс → новый» и правило «новый индекс → старый» обратны друг другу, хотя оба могут храниться массивом чисел.

Группа помогает учитывать преобразования, сохраняющие объект. Не всякая перестановка вершин графа сохраняет его рёбра: те, которые сохраняют, образуют группу автоморфизмов графа, подгруппу соответствующей SnS_n. В задачах на раскраски это позволяет считать конфигурации с точностью до симметрий; следующий шаг разобран в статье о лемме Бернсайда. Более сложные конструкции из перестановок блоков и внутренних действий рассматривает материал о сплетении групп.

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

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

Частые ошибки

  • Считать, что SnS_n содержит nn элементов. В ней n!n! перестановок; число nn обозначает размер исходного множества.
  • Менять порядок множителей без проверки. В S3S_3 уже есть пара ab≠baab\ne ba.
  • Читать цикл как список образов по порядку. (123)(123) означает последовательные переходы, тогда как (2,3,1)(2,3,1) в двухстрочной записи - строка образов; здесь результаты совпали лишь для выбранного примера.
  • Складывать длины непересекающихся циклов для поиска порядка. Нужно брать их наименьшее общее кратное.
  • Считать любую перестановку вершин симметрией графа. Она обязана сохранять отношение смежности.

FAQ

Является ли S2S_2 коммутативной?

Да. Она состоит только из тождества и одного обмена, а они коммутируют. Группа S1S_1 тоже коммутативна; для n≥3n\ge3 симметрическая группа уже не абелева.

Чем порядок группы отличается от порядка перестановки?

Первый - число всех элементов группы, второй - число повторений конкретного элемента до тождества. Например, порядок S3S_3 равен 6, а порядок цикла (123)(123) равен 3.

Почему композиция снова даёт перестановку?

Композиция двух биекций снова взаимно однозначно сопоставляет элементы исходного множества с ним самим. Обратное отображение получается применением обратных перестановок в обратном порядке.

Коротко

Симметрическая группа SnS_n объединяет все n!n! перестановок nn различимых элементов с операцией композиции. Циклы показывают движение отдельных элементов, транспозиции помогают определить чётность, а порядок композиции существенен уже в S3S_3. Эта структура позволяет точно описывать переиндексацию и симметрии дискретных объектов.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Группа диэдра: симметрии и преобразования многоугольника

Группа диэдра: симметрии и преобразования многоугольника

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

8 ноября 20268 минут
Характер представления группы: определение и примеры

Характер представления группы: определение и примеры

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

8 ноября 20268 минут
Числа Стирлинга первого рода: перестановки и циклы

Числа Стирлинга первого рода: перестановки и циклы

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

20 июня 20268 минут
Сплетение групп: конструкция и силовские подгруппы

Сплетение групп: конструкция и силовские подгруппы

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

4 февраля 20268 минут
Чётность подстановки: инверсии и знак

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

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

8 ноября 20268 минут
Граф Кэли: как построить граф группы

Граф Кэли: как построить граф группы

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

8 ноября 20268 минут