Введение
В комбинаторной математике индекс цикла — это многочлен от нескольких переменных, структура которого позволяет легко из коэффициентов и степеней считывать информацию о том, как группа перестановок действует на множество. Этот компактный способ хранения информации в алгебраической форме часто используется в комбинаторной перечислительной теории. Каждая перестановка π конечного множества объектов разбивает это множество на циклы; мономиал индекса цикла для π — это многочлен в переменных a₁, a₂, …, описывающий тип циклов этого разбиения: степень aᵢ равна числу циклов в π длины i. Полином индекса цикла для группы перестановок — это среднее арифметическое мономов индекса цикла по всем её элементам. Термин "индикатор цикла" также иногда используется вместо "индекс цикла". Зная полином индекса цикла группы перестановок, можно перечислять классы эквивалентности, возникающие в результате действия группы. Это ключевой элемент в теореме перечисления Пойи. Выполнение формальных алгебраических и дифференциальных операций над этими многочленами с последующей комбинаторной интерпретацией результатов лежит в основе теории видов.
Группы пермутации и групповые действия
Биективное отображение из множества X на себя называется перестановкой X, а множество всех перестановок X образует группу относительно композиции отображений, называемую симметрической группой X и обозначаемую Sym(X). Каждая подгруппа Sym(X) называется группой перестановок степени |X|. Пусть G — абстрактная группа с групповым гомоморфизмом φ из G в Sym(X). Образ, φ(G), является группой перестановок. Групповой гомоморфизм можно рассматривать как средство, позволяющее группе G "действовать" на множестве X (используя перестановки, связанные с элементами G). Такой групповой гомоморфизм формально называется групповым действием, а образ гомоморфизма представляет собой пермутационное представление G. У данной группы может быть множество различных пермутационных представлений, соответствующих различным действиям. Предположим, что группа G действует на множество X (то есть, групповое действие существует). В комбинаторных приложениях интерес представляет множество X; например, подсчет элементов в X и знание того, какие структуры могут быть инвариантны относительно G. При работе в такой постановке мало что теряется при использовании групп перестановок, поэтому в этих приложениях, когда рассматривается группа, используется пермутационное представление этой группы, и, следовательно, необходимо указывать групповое действие. Алгебраисты, с другой стороны, больше заинтересованы в самих группах и больше внимания уделяют ядрам групповых действий, которые показывают, какая информация теряется при переходе от группы к ее пермутационному представлению.
Диссойунтный цикл представления пермутаций
Конечные перестановки чаще всего представляются как групповые действия на множестве X = {1, 2, ..., n}. Перестановка в этом контексте может быть представлена двустрочной нотацией. Таким образом,
соответствует биекции на X = {1, 2, 3, 4, 5}, которая отображает 1 ↦ 2, 2 ↦ 3, 3 ↦ 4, 4 ↦ 5 и 5 ↦ 1. Это можно прочитать из столбцов данной нотации. Если верхнюю строку понимать как элементы X в некотором порядке, достаточно записать только вторую строку. В таком однострочном представлении наш пример будет выглядеть как [2 3 4 5 1]. Этот пример известен как циклическая перестановка, поскольку он "циклически" переставляет числа, и третьей нотацией для него будет (1 2 3 4 5). Эта циклическая нотация читается следующим образом: каждый элемент отображается в элемент справа от него, но последний элемент отображается в первый (он "возвращается" к началу). При использовании циклической нотации не имеет значения, с какого элемента начинается цикл, поэтому (1 2 3 4 5), (3 4 5 1 2) и (5 1 2 3 4) представляют одну и ту же перестановку. Длина цикла — это количество элементов в цикле. Не все перестановки являются циклическими, но каждую перестановку можно представить как произведение непересекающихся (не имеющих общих элементов) циклов единственным образом (с точностью до порядка). Поскольку перестановка может иметь неподвижные точки (элементы, которые не изменяются при перестановке), они будут представлены циклами длины один. Например:
Эта перестановка является произведением трех циклов: один длины два, один длины три и одна неподвижная точка. Элементы в этих циклах являются непересекающимися подмножествами X и образуют разбиение X. Циклическую структуру перестановки можно закодировать в виде алгебраического монома в нескольких (фиктивных) переменных следующим образом: для каждой различной длины цикла, встречающейся в циклическом разложении перестановки, требуется переменная. В предыдущем примере было три различные длины цикла, поэтому мы будем использовать три переменные: a1, a2 и a3 (в общем случае используйте переменную ak для циклов длины k). Переменная ai будет возведена в степень ji(g), где ji(g) — количество циклов длины i в циклическом разложении перестановки g. Затем мы можем связать мономиал цикла-индекса
с перестановкой g. Мономиал цикла-индекса для нашего примера будет a1a2a3, а мономиал цикла-индекса для перестановки (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13) будет a1a2²a4².
Пример
Рассмотрим группу G вращательных симметрий квадрата в евклидовой плоскости. Ее элементы полностью определяются изображениями только углов квадрата. Обозначив эти углы 1, 2, 3 и 4 (последовательно по часовой стрелке, например), мы можем представить элементы G как перестановки множества X = {1, 2, 3, 4}. Пермутационное представление G состоит из четырех перестановок (1 4 3 2), (1 3)(2 4), (1 2 3 4) и e = (1)(2)(3)(4), которые представляют собой вращения против часовой стрелки на 90°, 180°, 270° и 360° соответственно. Обратите внимание, что тождественная перестановка e является единственной перестановкой с неподвижными точками в этом представлении G. Как абстрактная группа, G известна как циклическая группа C4, и это пермутационное представление является ее регулярным представлением. Мономиальные индексы цикла – a4, a22, a4 и a14 соответственно. Таким образом, индекс цикла этой группы перестановок:
Группа C4 также действует на неупорядоченные пары элементов X естественным образом. Любая перестановка g будет отображать {x, y} → {x g, y g} (где x g – образ элемента x при перестановке g). Множество X теперь {A, B, C, D, E, F}, где A = {1, 2}, B = {2, 3}, C = {3, 4}, D = {1, 4}, E = {1, 3} и F = {2, 4}. Эти элементы можно рассматривать как стороны и диагонали квадрата или, в совершенно другом контексте, как ребра полного графа K4. Действуя на этот новый набор, четыре элемента группы теперь представлены (A D C B)(E F), (A C)(B D)(E)(F), (A B C D)(E F) и e = (A)(B)(C)(D)(E)(F), и индекс цикла этого действия:
Группа C4 также может действовать на упорядоченные пары элементов X тем же естественным образом. Любая перестановка g будет отображать (x, y) → (x g, y g) (в этом случае мы также будем иметь упорядоченные пары вида (x, x)). Элементы X можно рассматривать как дуги полного диграфа D4 (с петлями на каждой вершине). В этом случае индекс цикла будет:
Группа идентификации En
Эта группа содержит одну перестановку, которая оставляет неизменным каждый элемент (это должно быть естественным действием).
Циклическая группа Cn
Циклическая группа Cn — это группа вращений правильного n-угольника, то есть n элементов, равноудалённых друг от друга на окружности. Эта группа содержит φ(d) элементов порядка d для каждого делителя d числа n, где φ(d) — функция Эйлера, дающая количество натуральных чисел, меньших d и взаимно простых с d. В регулярном представлении Cn пермутация порядка d имеет n/d циклов длины d, таким образом:
Диедрическая группа Dn
Диэдрическая группа похожа на циклическую группу, но также включает в себя отражения. В своем естественном представлении,