Индекс цикла

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

Каждая перестановка π конечного набора объектов разбиений, которые установлены в циклы ; моном индекса цикла числа π является мономом от переменных a 1, a 2,…, который описывает тип этого разбиения ( тип цикла числа π): показатель степени a i - это количество циклов числа π размера i. Полином индекса цикла группы перестановок представляет собой среднее значение одночленов индекса цикла его элементов. Фраза индикатор цикла также иногда используется вместо индекса цикла.

Зная полином индекса цикла группы перестановок, можно перечислить классы эквивалентности из-за действия группы. Это главный компонент теоремы перечисления Полиа. Выполнение формальных алгебраических и дифференциальных операций над этими многочленами, а затем комбинаторная интерпретация результатов лежит в основе теории видов.

• 1 Группы перестановок и действия групп
• 2 Непересекающееся циклическое представление перестановок
• 3 Определение
• 4 Пример
• 5 Типы действий
  • 5.1 Индекс цикла группы перестановок ребер полного графа на трех вершинах
  • 5.2 Индекс цикла группы перестановок ребер полного графа на четыре вершины
  • 5.3 Индекс цикла перестановок граней куба
• 6 Индексы цикла некоторых групп перестановок
  • 6.1 Группа идентичности E n
  • 6.2 Циклическая группа C n
  • 6.3 Группа диэдра D n
  • 6.4 Переменная группа A n
  • 6.5 Симметричная группа S n
• 7 Приложения
• 8 Примечания
• 9 Ссылки
• 10 Внешние ссылки

A биективное отображение из множество X на себя называется перестановкой X, и множество всех перестановок X образует группу под копией Расположение отображений, называемое симметричной группой X и обозначаемое Sym (X). Каждая подгруппа в Sym (X) называется группой перестановок степени | X |. Пусть G - абстрактная группа с групповым гомоморфизмом φ из G в Sym (X). Изображение , φ (G), является группой перестановок. Групповой гомоморфизм можно рассматривать как средство, позволяющее группе G «действовать» на множестве X (используя перестановки, связанные с элементами группы G). Такой гомоморфизм группы формально называется действием группы , а образ гомоморфизма является представлением перестановки группы G. У данной группы может быть много различных представлений перестановок, соответствующих различным действиям.

Предположим, что группа G действует на множестве X (т.е. существует групповое действие). В комбинаторных приложениях интерес представляет множество X; например, подсчет вещей в X и знание того, какие структуры могут быть оставлены инвариантными при помощи G. Литтл теряется, работая с группами перестановок в таких условиях, поэтому в этих приложениях, когда группа рассматривается, это представляет собой перестановочное представление группы с которым будет работать, и поэтому необходимо указать групповое действие. С другой стороны, алгебраистов больше интересуют сами группы, и их больше интересуют ядра действий группы, которые измеряют, сколько теряется при переходе от группы к ее перестановочному представлению. 122>

Конечные перестановки чаще всего представляются как групповые действия на множестве X = {1,2,..., n}. Перестановка в этом параметре может быть представлена ​​двухстрочной записью. Таким образом,

$(1\; 2\; 3\; 4\; 5\; 2\; 3\; 4\; 5\; 1)\; \{\backslash \; displaystyle\; \backslash \; left\; (\{\backslash \; begin\; \{matrix\}\; 1\; 2\; 3\; 4\; 5\; \backslash \backslash \; 2\; 3\; 4\; 5\; 1\; \backslash \; end\; \{matrix\}\}\; \backslash \; right)\}$

соответствует биекция на 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) все представляют собой одну и ту же перестановку. Длина цикла - это количество элементов в цикле.

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

$(1\; 2\; 3\; 4\; 5\; 6\; 2\; 1\; 3\; 5\; 6\; 4)\; =\; (12)\; (3)\; (456).\; \{\backslash \; displaystyle\; \backslash \; left\; (\{\backslash \; begin\; \{matrix\}\; 1\; 2\; 3\; 4\; 5\; 6\; \backslash \backslash \; 2\; 1\; 3\; 5\; 6\; 4\; \backslash \; end\; \{matrix\}\}\; \backslash \; right)\; =\; (12)\; (3)\; (456).\}$

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

Циклическую структуру перестановки можно закодировать как алгебраический моном в нескольких (dummy ) переменными следующим образом: переменная необходима для каждой отдельной длины цикла циклов, которые появляются в циклической декомпозиции перестановки. В предыдущем примере было три разных длины цикла, поэтому мы будем использовать три переменные: a 1, a 2 и 3 (обычно используйте переменная a k для соответствия длине k циклов). Переменная a i будет увеличена до степени j i (g), где j i (g) - количество циклов длины i в цикле разложение перестановки g. Затем мы можем связать моном индекса цикла

$\prod \; k\; =\; 1\; nakjk\; (g)\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; a\_\; \{k\}\; ^\; \{j\_\; \{k\}\; (g)\}\}$

к перестановке g. Мономом индекса цикла в нашем примере будет 1a2a3, а мономом индекса цикла перестановки (1 2) (3 4) (5) (6 7 8 9) (10 11 12 13) (14) (15) будет 1a2a4.

индекс цикла группы перестановок G является средним значением одночленов индекса цикла всех перестановок g в G.

Более формально, пусть G - группа перестановок порядка m и степени n. Каждая перестановка g в G имеет единственное разложение на непересекающиеся циклы, скажем c 1c2c3.... Обозначим длину цикла c через | c |.

Теперь пусть j k (g) будет количеством циклов g длины k, где

$0\; \le \; jk\; (g)\; \le \; \lfloor \; n\; /\; k\; \rfloor \; и\; \sum \; k\; =\; 1\; nkjk\; (g)\; =\; n.\; \{\backslash \; displaystyle\; 0\; \backslash \; leq\; j\_\; \{k\}\; (g)\; \backslash \; leq\; \backslash \; lfloor\; n\; /\; k\; \backslash \; rfloor\; \{\backslash \; t\_dv\; \{and\}\}\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; k\; \backslash ,\; j\_\; \{k\}\; (g)\; \backslash ;\; =\; n.\}$

Сопоставим g моном

$\prod \; c\; \in \; ga\; |\; c\; |\; Знак\; равно\; \prod \; К\; =\; 1\; nakjk\; (g)\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{c\; \backslash \; in\; g\}\; a\_\; \{|\; c\; |\}\; =\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; a\_\; \{k\}\; ^\; \{j\_\; \{k\}\; (g)\}\}$

в переменных a 1, a 2,..., a n.

Тогда индекс цикла Z (G) группы G определяется выражением

$Z\; (G)\; =\; 1\; |\; G\; |\; \sum \; g\; \in \; G\; \prod \; k\; =\; 1\; n\; a\; k\; j\; k\; (g).\; \{\backslash \; displaystyle\; Z\; (G)\; =\; \{\backslash \; frac\; \{1\}\; \{|\; G\; |\}\}\; \backslash \; sum\; \_\; \{g\; \backslash \; in\; G\}\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; a\_\; \{k\}\; ^\; \{j\_\; \{k\; \}\; (g)\}.\}$

Рассмотрим группу 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 известна как циклическая группа C 4, и это ее перестановочное представление является ее регулярным представлением.. Мономы индекса цикла - это a 4, a 2, a 4 и a 1 соответственно. Таким образом, индекс цикла этой группы перестановок равен:

$Z\; (C\; 4)\; =\; 1\; 4\; (a\; 1\; 4\; +\; a\; 2\; 2\; +\; 2\; a\; 4).\; \{\backslash \; displaystyle\; Z\; (C\_\; \{4\})\; =\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{4\}\; +\; a\_\; \{2\}\; ^\; \{2\}\; +\; 2a\_\; \{4\}\; \backslash \; right).\; \}$

Группа C 4 также естественным образом действует на неупорядоченные пары элементов X. Любая перестановка g отправила бы {x, y} → {x, y} (где x - изображение элемента 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. Действуя на этом новом наборе, четыре элемента группы теперь представлены (ADCB) (EF), (AC) (BD) (E) (F), (ABCD) (EF) и e = (A) (B) ( C) (D) (E) (F) и индекс цикла этого действия:

$Z\; (C\; 4)\; =\; 1\; 4\; (a\; 1\; 6\; +\; a\; 1\; 2\; a\; 2\; 2\; +\; 2\; a\; 2\; a\; 4).\; \{\backslash \; displaystyle\; Z\; (C\_\; \{4\})\; =\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{6\}\; +\; a\_\; \{1\}\; ^\; \{2\}\; a\_\; \{2\}\; ^\; \{2\}\; +\; 2a\_\; \{2\}\; a\_\; \{4\}\; \backslash \; right).\}$

Группа C 4 также может действовать на упорядоченные пары элементов X таким же естественным образом. Любая перестановка g отправила бы (x, y) → (x, y) (в этом случае у нас также были бы упорядоченные пары формы (x, x)). Элементы X можно рассматривать как дуги полного орграфа D4(с петлями в каждой вершине). Индекс цикла в этом случае будет:

$Z\; (C\; 4)\; =\; 1\; 4\; (a\; 1\; 16\; +\; a\; 2\; 8\; +\; 2\; a\; 4\; 4).\; \{\backslash \; displaystyle\; Z\; (C\_\; \{4\})\; =\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{16\}\; +\; a\_\; \{2\}\; ^\; \{8\}\; +\; 2a\_\; \{4\}\; ^\; \{4\}\; \backslash \; right).\}$

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

Когда абстрактная группа определяется в терминах перестановок, это группа перестановок, а действие группы - это тождественный гомоморфизм. Это называется естественным действием.

Симметрическая группа S 3 в своем естественном действии имеет элементы

$S\; 3\; =\; \{e,\; (23),\; (12),\; (123),\; (132),\; (\; 13)\}\; \{\backslash \; displaystyle\; S\_\; \{3\}\; =\; \backslash \; \{e,\; (23),\; (12),\; (123),\; (132),\; (13)\; \backslash \}\}$

и поэтому его индекс цикла:

$Z\; (S\; 3)\; =\; 1\; 6\; (a\; 1\; 3\; +\; 3\; a\; 1\; a\; 2\; +\; 2\; a\; 3).\; \{\backslash \; displaystyle\; Z\; (S\_\; \{3\})\; =\; \{\backslash \; frac\; \{1\}\; \{6\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{3\}\; +\; 3a\_\; \{1\}\; a\_\; \{2\}\; +\; 2a\_\; \{3\}\; \backslash \; right).\; \}$

Группа перестановок G на множестве X транзитивна, если для каждой пары элементов x и y в X существует хотя бы один g в G такой, что y = x. Группа транзитивных перестановок является регулярной (или иногда называемой строго транзитивной), если единственная перестановка в группе, которая имеет неподвижные точки, является тождественной перестановкой.

Конечная транзитивная группа подстановок G на множестве X регулярна тогда и только тогда, когда | G | = | X |. Теорема Кэли утверждает, что каждая абстрактная группа имеет регулярное перестановочное представление, заданное группой, действующей на себя (как набор) посредством (правого) умножения. Это называется регулярным представлением группы.

Циклическая группа C 6 в своем регулярном представлении содержит шесть перестановок (однострочная форма перестановки дается первой):

[1 2 3 4 5 6] = (1) (2) (3) (4) (5) (6)

[2 3 4 5 6 1] = (1 2 3 4 5 6)

[3 4 5 6 1 2] = (1 3 5) (2 4 6)

[4 5 6 1 2 3] = (1 4) (2 5) (3 6)

[ 5 6 1 2 3 4] = (1 5 3) (2 6 4)

[6 1 2 3 4 5] = (1 6 5 4 3 2).

Таким образом, его индекс цикла равен :

$Z\; (C\; 6)\; =\; 1\; 6\; (a\; 1\; 6\; +\; a\; 2\; 3\; +\; 2\; a\; 3\; 2\; +\; 2\; a\; 6).\; \{\backslash \; displaystyle\; Z\; (C\_\; \{6\})\; =\; \{\backslash \; frac\; \{1\}\; \{6\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{6\}\; +\; a\_\; \{2\}\; ^\; \{3\}\; +\; 2a\_\; \{3\}\; ^\; \{2\}\; +\; 2a\_\; \{6\}\; \backslash \; right).\}$

Часто, когда автор не желает использовать терминологию группового действия, задействованной группе перестановок дается имя, которое подразумевает, что это за действие. Следующие три примера иллюстрируют эту точку зрения.

Индекс цикла группы перестановок ребер полного графа на трех вершинах

Мы отождествим полный граф K3с равносторонним треугольником в Евклидова плоскость. Это позволяет нам использовать геометрический язык для описания задействованных перестановок как симметрий равностороннего треугольника. Каждая перестановка в группе S 3 перестановок вершин (S 3 в ее естественном действии, данном выше) индуцирует перестановку ребер. Это перестановки:

• Тождество: никакие вершины не переставляются и никакие ребра; вклад равен $a\; 1\; 3.\; \{\backslash \; displaystyle\; a\_\; \{1\}\; ^\; \{3\}.\}$
• Три отражения на оси, проходящей через вершину и середину противоположного ребра: они фиксируют одно ребро (то, которое не инцидентно вершине) и меняют оставшиеся два; вклад равен $3\; a\; 1\; a\; 2.\; \{\backslash \; displaystyle\; 3a\_\; \{1\}\; a\_\; \{2\}.\}$
• Два поворота, один по часовой стрелке, другой против часовой стрелки: они создают цикл из трех ребер; вклад равен $2\; a\; 3.\; \{\backslash \; displaystyle\; 2a\_\; \{3\}.\}$

Индекс цикла группы G перестановок ребер, индуцированных перестановками вершин из S 3, равен

$Z\; (G)\; =\; 1\; 6\; (a\; 1\; 3\; +\; 3\; а\; 1\; а\; 2\; +\; 2\; а\; 3).\; \{\backslash \; displaystyle\; Z\; (G)\; =\; \{\backslash \; frac\; \{1\}\; \{6\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{3\}\; +\; 3a\_\; \{1\}\; a\_\; \{2\}\; +\; 2a\_\; \{3\}\; \backslash \; right).\}$

Бывает, что полный граф K 3 изоморфен своему собственному линейному графу (дуальный вершина-ребро), и поэтому группа перестановок ребер, индуцированная группой перестановок вершин, такая же, как группа перестановок вершин, а именно S 3, и индекс цикла равен Z (S 3). Это не относится к полным графам, имеющим более трех вершин, поскольку они имеют строго больше ребер ($(n\; 2)\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{2\}\}\}$), чем вершины (п).

Индекс цикла группы перестановок ребер полного графа с четырьмя вершинами

Это полностью аналогично случаю с тремя вершинами. Это перестановки вершин (S 4 в его естественном действии) и перестановки ребер (S 4, действующие на неупорядоченные пары), которые они индуцируют:

• Тождество: эта перестановка отображает все вершины (и, следовательно, рёбра) в себя, и вклад равен $a\; 1\; 6.\; \{\backslash \; displaystyle\; a\_\; \{1\}\; ^\; \{6\}.\}$
• Шесть перестановок, которые меняют две вершины: Эти перестановки сохраняют ребро, которое соединяет две вершины, а также ребро, которое соединяет две вершины, не поменялись местами. Остальные ребра образуют два двухцикла, и вклад равен $6\; a\; 1\; 2\; a\; 2\; 2.\; \{\backslash \; displaystyle\; 6a\_\; \{1\}\; ^\; \{2\}\; a\_\; \{2\}\; ^\; \{2\}.\}$
• Восемь перестановок, которые фиксируют одну вершину и производят три цикла для трех нефиксированных вершин: эти перестановки создают два трехцикла ребер, одно из которых содержит те, которые не инцидентны вершине, а другое - ребра, инцидентные вершине; вклад равен $8\; a\; 3\; 2.\; \{\backslash \; displaystyle\; 8a\_\; \{3\}\; ^\; \{2\}.\}$
• Три перестановки, которые обменивают две пары вершин одновременно: эти перестановки сохраняют два ребра, соединяющих две пары. Остальные ребра образуют два двухцикла, и вклад равен $3\; a\; 1\; 2\; a\; 2\; 2.\; \{\backslash \; displaystyle\; 3a\_\; \{1\}\; ^\; \{2\}\; a\_\; \{2\}\; ^\; \{2\}.\}$
• Шесть перестановок, которые циклируют вершины за четыре цикла: эти перестановки создают четыре цикла ребер (те, которые лежат на цикл) и поменять местами оставшиеся два ребра; вклад $6\; a\; 2\; a\; 4.\; \{\backslash \; displaystyle\; 6a\_\; \{2\}\; a\_\; \{4\}.\}$

Мы можем визуализировать типы перестановок геометрически как симметрии правильного тетраэдра. Это дает следующее описание типов перестановок.

• Тождество.
• Отражение в плоскости, содержащей одно ребро и среднюю точку противоположного ему ребра.
• Поворот на 120 градусов вокруг оси, проходящей через вершину и среднюю точку
• Поворот на 180 градусов вокруг оси, соединяющей средние точки двух противоположных краев.
• Шесть вращательных отражений на 90 градусов.

Индекс цикла группы перестановок ребер G K 4 :

$Z\; (G)\; =\; 1\; 24\; (a\; 1\; 6\; +\; 9\; a\; 1\; 2\; a\; 2\; 2\; +\; 8\; a\; 3\; 2\; +\; 6\; a\; 2\; a\; 4).\; \{\backslash \; displaystyle\; Z\; (G)\; =\; \{\backslash \; frac\; \{1\}\; \{24\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{6\}\; +\; 9a\_\; \{1\}\; ^\; \{2\}\; a\_\; \{2\}\; ^\; \{2\}\; +\; 8a\_\; \{3\; \}\; ^\; \{2\}\; +\; 6a\_\; \{2\}\; a\_\; \{4\}\; \backslash \; right).\}$

Индекс цикла перестановок граней куба

Рассмотрим обычный куб в трехмерном пространстве. и его группу симметрий (автоморфизмов) назовем C. Он переставляет шесть граней куба. (Мы могли бы также рассмотреть перестановки ребер или перестановки вершин.) Существует двадцать четыре автоморфизма.

• Идентификатор:

Существует одна такая перестановка, и ее вклад равен $a\; 1\; 6.\; \{\backslash \; displaystyle\; a\_\; \{1\}\; ^\; \{6\}.\}$

• Шесть поворотов грани на 90 градусов:

Мы вращаемся вокруг оси, проходящей через центры грани и грани напротив. Это зафиксирует грань и грань напротив нее и создаст четыре цикла граней, параллельных оси вращения. Вклад равен $6\; a\; 1\; 2\; a\; 4.\; \{\backslash \; displaystyle\; 6a\_\; \{1\}\; ^\; \{2\}\; a\_\; \{4\}.\}$

• Три поворота лица на 180 градусов:

Мы вращаемся вокруг той же оси, что и в предыдущем случае, но теперь нет четырех циклов грани параллельны оси, а точнее два двухцикла. Вклад равен $3\; a\; 1\; 2\; a\; 2\; 2.\; \{\backslash \; displaystyle\; 3a\_\; \{1\}\; ^\; \{2\}\; a\_\; \{2\}\; ^\; \{2\}.\}$

• Восемь поворотов вершин на 120 градусов:

На этот раз мы вращаемся вокруг оси, проходящей через две противоположные вершины (конечные точки главная диагональ). Это создает два трехцикла граней (грани, входящие в одну вершину, образуют цикл). Вклад равен $8\; a\; 3\; 2.\; \{\backslash \; displaystyle\; 8a\_\; \{3\}\; ^\; \{2\}.\}$

• Шесть поворотов краев на 180 градусов:

Эти повороты краев вращаются вокруг оси, проходящей через середины противоположных краев, не входящих в одну грань и параллельных друг друга и меняют местами две грани, которые инцидентны на первом ребре, две грани, инцидентные на втором ребре, и две грани, которые имеют две общие вершины, но не имеют ребра с двумя ребрами, т.е. есть три двухцикла и вклад равно $6\; a\; 2\; 3.\; \{\backslash \; displaystyle\; 6a\_\; \{2\}\; ^\; \{3\}.\}$

Вывод состоит в том, что индекс цикла группы C равен

$Z\; (C)\; =\; 1\; 24\; (a\; 1\; 6\; +\; 6\; a\; 1\; 2\; a\; 4\; +\; 3\; а\; 1\; 2\; а\; 2\; 2\; +\; 8\; а\; 3\; 2\; +\; 6\; а\; 2\; 3).\; \{\backslash \; displaystyle\; Z\; (C)\; =\; \{\backslash \; frac\; \{1\}\; \{24\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{6\}\; +\; 6a\_\; \{1\}\; ^\; \{2\}\; a\_\; \{4\}\; +\; 3a\_\; \{1\}\; ^\; \{2\; \}\; a\_\; \{2\}\; ^\; \{2\}\; +\; 8a\_\; \{3\}\; ^\; \{2\}\; +\; 6a\_\; \{2\}\; ^\; \{3\}\; \backslash \; right).\}$

Группа идентичности E n

Эта группа содержит одну перестановку, фиксирующую каждый элемент (это должно быть естественное действие).

$Z\; (E\; n)\; =\; a\; 1\; n.\; \{\backslash \; displaystyle\; Z\; (E\_\; \{n\})\; =\; a\_\; \{1\}\; ^\; \{n\}.\}$

Циклическая группа C n

A циклическая группа, C n - группа вращений правильный n-угольник, то есть n элементов, равномерно распределенных по окружности. Эта группа имеет φ (d) элементов порядка d для каждого делителя d числа n, где φ (d) - это φ-функция Эйлера, дающая количество натуральных чисел меньше d, которые взаимно просты с d. В регулярном представлении C n перестановка порядка d имеет n / d циклов длины d, таким образом:

$Z\; (C\; n)\; =\; 1\; n\; \sum \; d\; |\; п\; \phi \; (г)\; а\; д\; н\; /\; д.\; \{\backslash \; displaystyle\; Z\; (C\_\; \{n\})\; =\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{d\; |\; n\}\; \backslash \; varphi\; (d)\; a\_\; \{d\}\; ^\; \{n\; /\; d\}.\}$

Двугранный группа D n

Группа диэдра подобна циклической группе, но также включает отражения. В своем естественном действии

$Z\; (D\; n)\; =\; 1\; 2\; Z\; (C\; n)\; +\; \{1\; 2\; a\; 1\; a\; 2\; (n\; -\; 1)\; /\; 2,\; n\; odd,\; 1\; 4\; (a\; 1\; 2\; a\; 2\; (n\; -\; 2)\; /\; 2\; +\; a\; 2\; n\; /\; 2),\; n\; четное.\; \{\backslash \; displaystyle\; Z\; (D\_\; \{n\})\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; Z\; (C\_\; \{n\})\; +\; \{\backslash \; begin\; \{cases\}\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; a\_\; \{1\}\; a\_\; \{2\}\; ^\; \{(n-1)\; /\; 2\},\; n\; \{\backslash \; t\_dv\; \{odd,\}\}\; \backslash \backslash \; \{\backslash \; frac\; \{1\}\; \{4\}\}\; \backslash \; left\; (a\_\; \{1\}\; ^\; \{2\}\; a\_\; \{2\}\; ^\; \{(n-2)\; /\; 2\}\; +\; a\_\; \{2\}\; ^\; \{n\; /\; 2\}\; \backslash \; right),\; n\; \{\backslash \; t\_dv\; \{even.\}\}\; \backslash \; end\; \{cases\}\}\}$

Альтернативная группа A n

Индекс цикла альтернированной группы в ее естественном действии как группы перестановок равен

$Z\; (A\; n)\; =\; \sum \; j\; 1\; +\; 2\; j\; 2\; +\; 3\; j\; 3\; +\; \cdots \; +\; njn\; =\; n\; 1\; +\; (-\; 1)\; j\; 2\; +\; j\; 4\; +\; \cdots \; \prod \; k\; знак\; равно\; 1\; nkjkjk!\; \prod \; К\; знак\; равно\; 1\; N\; а\; К\; Дж\; К.\; \{\backslash \; Displaystyle\; Z\; (A\_\; \{n\})\; =\; \backslash \; sum\; \_\; \{j\_\; \{1\}\; +\; 2j\_\; \{2\}\; +\; 3j\_\; \{3\}\; +\; \backslash \; cdots\; +\; nj\_\; \{n\}\; =\; n\}\; \{\backslash \; frac\; \{1\; +\; (-\; 1)\; ^\; \{j\_\; \{2\}\; +\; j\_\; \{4\}\; +\; \backslash \; cdots\}\}\; \{\backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; k\; ^\; \{j\_\; \{k\}\}\; j\_\; \{k\}!\}\}\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; a\_\; \{k\}\; ^\; \{j\_\; \{k\}\}.\}$

Числитель равен 2 для четных перестановок и 0 для нечетных перестановок. 2 необходимо, потому что $1\; |\; A\; n\; |\; =\; 2\; п!\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{|\; A\_\; \{n\}\; |\}\}\; =\; \{\backslash \; frac\; \{2\}\; \{n!\}\}\}$.

Симметричная группа S n

Индекс цикла симметрической группы Snв своем естественном действии задается формулой:

$Z\; (S\; n)\; =\; \sum \; j\; 1\; +\; 2\; j\; 2\; +\; 3\; j\; 3\; +\; \cdots \; +\; njn\; =\; n\; 1\; \prod \; k\; =\; 1\; nkjkjk!\; \prod \; К\; знак\; равно\; 1\; nakjk\; \{\backslash \; Displaystyle\; Z\; (S\_\; \{n\})\; =\; \backslash \; сумма\; \_\; \{j\_\; \{1\}\; +\; 2j\_\; \{2\}\; +\; 3j\_\; \{3\}\; +\; \backslash \; cdots\; +\; nj\_\; \{n\}\; =\; n\}\; \{\backslash \; гидроразрыва\; \{1\; \}\; \{\backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; k\; ^\; \{j\_\; \{k\}\}\; j\_\; \{k\}!\}\}\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; a\_\; \{k\}\; ^\; \{j\_\; \{k\; \}\}\}$

, что также может быть выражено в терминах полных полиномов Белла :

$Z\; (S\; n)\; =\; B\; n\; (0!\; A\; 1,\; 1!\; A\; 2,\dots ,\; (n\; -\; 1)!\; Энн\; !.\; \{\backslash \; displaystyle\; Z\; (S\_\; \{n\})\; =\; \{\backslash \; frac\; \{B\_\; \{n\}\; (0!\; \backslash ,\; a\_\; \{1\},\; 1!\; \backslash ,\; a\_\; \{2\},\; \backslash \; dots,\; (n-1)!\; \backslash ,\; a\_\; \{n\})\}\; \{n!\}\}.\}$

Эта формула получается путем подсчета того, сколько раз может встречаться данная форма перестановки. Есть три шага: сначала разделите набор из n меток на подмножества, где есть $j\; k\; \{\backslash \; displaystyle\; j\_\; \{k\}\}$подмножества размера k. Каждое такое подмножество порождает $k!\; /\; k\; \{\backslash \; displaystyle\; k!\; /\; k\}$циклов длины k. Но мы не различаем циклы одинакового размера, т.е. они переставляются $S\; j\; k\; \{\backslash \; displaystyle\; S\_\; \{j\_\; \{k\}\}\}$. Это дает

$n!\; \prod \; К\; знак\; равно\; 1\; N\; (К!)\; J\; К\; \prod \; К\; знак\; равно\; 1\; N\; (К!\; К)\; J\; К\; \prod \; К\; знак\; равно\; 1\; N\; 1\; J\; К!\; =\; п!\; \prod \; К\; знак\; равно\; 1\; N\; К\; J\; К\; J\; К!.\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{n!\}\; \{\backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; (k!)\; ^\; \{j\_\; \{k\}\}\}\}\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; \backslash \; left\; (\{\backslash \; frac\; \{k!\}\; \{k\}\}\; \backslash \; right)\; ^\; \{j\_\; \{k\}\}\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; \{\backslash \; frac\; \{1\}\; \{j\_\; \{k\}!\}\}\; =\; \{\; \backslash \; frac\; \{n!\}\; \{\backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; k\; ^\; \{j\_\; \{k\}\}\; j\_\; \{k\}!\}\}.\}$

Существует полезная рекурсивная формула для индекса цикла симметрическая группа. Установите $Z\; (S\; 0)\; =\; 1\; \{\backslash \; displaystyle\; Z\; (S\_\; \{0\})\; =\; 1\}$и рассмотрите размер l цикла, который содержит n, где $1\; \le \; l\; \le \; п.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; 1\; \backslash \; leq\; l\; \backslash \; leq\; n.\; \backslash \; end\; \{matrix\}\}\}$Есть $(n\; -\; 1\; l\; -\; 1)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{\; matrix\}\; \{n-1\; \backslash \; choose\; l-1\}\; \backslash \; end\; \{matrix\}\}\}$способы выбрать оставшиеся $l\; -\; 1\; \{\backslash \; displaystyle\; l-1\}$элементы цикла, и каждый такой выбор порождает $l!\; l\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; \{\backslash \; frac\; \{l!\}\; \{l\}\}\; \backslash \; end\; \{matrix\}\}\}$разных циклов.

Это дает повторение

$Z\; (S\; n)\; =\; 1\; n!\; \sum \; G\; \in \; S\; N\; \prod \; К\; знак\; равно\; 1\; N\; а\; К\; J\; К\; (г)\; знак\; равно\; 1\; N!\; \sum \; л\; знак\; равно\; 1\; п\; (п\; -\; 1\; л\; -\; 1)\; л!\; л\; а\; л\; (п\; -\; л)!\; Z\; (S\; n\; -\; l)\; \{\backslash \; displaystyle\; Z\; (S\_\; \{n\})\; =\; \{\backslash \; frac\; \{1\}\; \{n!\}\}\; \backslash \; Sum\; \_\; \{g\; \backslash \; in\; S\_\; \{n\}\}\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; a\_\; \{k\}\; ^\; \{j\_\; \{k\}\; (g)\}\; =\; \{\backslash \; frac\; \{1\}\; \{n!\}\}\; \backslash \; sum\; \_\; \{l\; =\; 1\}\; ^\; \{n\}\; \{n-1\; \backslash \; выбрать\; l-1\; \}\; \backslash ;\; \{\backslash \; frac\; \{l!\}\; \{l\}\}\; \backslash ;\; a\_\; \{l\}\; \backslash ;\; (nl)!\; \backslash ;\; Z\; (S\_\; \{nl\})\}$

или

$Z\; (S\; n)\; =\; 1\; n\; \sum \; l\; =\; 1\; конечный\; Z\; (S\; n\; -\; l).\; \{\backslash \; displaystyle\; Z\; (S\_\; \{n\})\; =\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{l\; =\; 1\}\; ^\; \{n\}\; a\_\; \{l\}\; \backslash ;\; Z\; (S\_\; \{nl\}).\}$

Приложения

В этом разделе мы немного изменим нотацию для индексов цикла, явно включив имена переменных. Таким образом, теперь для группы перестановок G запишем:

$Z\; (G)\; =\; Z\; (G;\; a\; 1,\; a\; 2,\dots ,\; a\; n).\; \{\backslash \; displaystyle\; Z\; (G)\; =\; Z\; (G;\; a\_\; \{1\},\; a\_\; \{2\},\; \backslash \; ldots,\; a\_\; \{n\}).\}$

Пусть G - группа, действующая на множестве X. G также индуцирует действие на k-подмножествах X и на наборах k различных элементов X (см. #Example для случая k = 2) для 1 ≤ k ≤ n. Пусть f k и F k обозначают количество орбит группы G в этих действиях соответственно. По соглашению мы устанавливаем f 0 = F 0 = 1. У нас есть:

a) Обычная производящая функция для f k определяется выражением:

$\sum \; k\; =\; 0\; nfktk\; =\; Z\; (G;\; 1\; +\; t,\; 1\; +\; t\; 2,\dots ,\; 1\; +\; tn),\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{\; n\}\; f\_\; \{k\}\; t\; ^\; \{k\}\; =\; Z\; (G;\; 1\; +\; t,\; 1\; +\; t\; ^\; \{2\},\; \backslash \; ldots,\; 1\; +\; t\; ^\; \{n\}),\}$и

b) экспоненциальная производящая функция для F k определяется как:

$\sum \; k\; =\; 0\; n\; F\; ktk\; /\; k!\; =\; Z\; (G;\; 1\; +\; t,\; 1,\; 1,\dots ,\; 1).\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; F\_\; \{k\}\; t\; ^\; \{k\}\; /\; k!\; =\; Z\; (G;\; 1\; +\; t,\; 1,1,\; \backslash \; ldots,\; 1).\}$

Пусть G - группа, действующая на множестве X, и ha функция от X до Y. Для любого g в G, h (x) также является функцией от X до Y. Таким образом, G индуцирует действие на множестве Y всех функций от X до Y. Число орбит этого действия равно Z (G; b, b,..., b), где b = | Y |.

Этот результат следует из подсчета орбит лемма (также известная как лемма Не Бернсайда, но традиционно называемая леммой Бернсайда), и взвешенная версия результата - теорема о перечислении Поли.

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

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

Примечания

Ссылки

• Brualdi, Richard A. (2010), «14. Pólya Counting», Introductory Combinatorics ( 5-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Прентис Холл, стр. 541–575, ISBN 978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), «15. Перечисление при групповом действии», Комбинаторика: темы, методы, алгоритмы, Кембридж: Cambridge University Press, стр. 245–256, ISBN 0-521-45761-0
• Диксон, Джон Д.; Мортимер, Брайан (1996), Группы перестановок, Нью-Йорк: Springer, ISBN 0-387-94599-7
• Roberts, Fred S.; Тесман, Барри (2009), «8.5 The Cycle Index», Applied Combinatorics (2-е изд.), Boca Raton: CRC Press, стр. 472–479, ISBN 978-1-4200- 9982-9
• Такер, Алан (1995), «9.3 The Cycle Index», Applied Combinatorics (3-е изд.), Нью-Йорк: Wiley, стр. 365–371, ISBN 0-471-59504-7
• ван Линт, JH; Уилсон, Р. (1992), «35.Pólya теория счета», Курс комбинаторики, Кембридж: Cambridge University Press, стр. 461–474, ISBN 0-521-42260-4

Внешние ссылки

• Марко Ридель, Теорема перечисления Поли и символический метод
• Марко Ридель, Индексы цикла оператора множества / мультимножества и экспоненциальной формулы
• Харальд Фрипертингер (1997). «Показатели цикла линейных, аффинных и проективных групп». Линейная алгебра и ее приложения. 263 : 133–156. doi : 10.1016 / S0024-3795 (96) 00530-7.
• Харальд Фрипертингер (1992). «Перечисление в музыкальной теории». Beiträge zur Elektronischen Musik. 1.