Индекс цикла - Cycle index

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

Каждая перестановка π конечный набор предметов перегородки что установлено в циклы; в моном индекса цикла π является одночлен в переменных а₁, а₂,… Который описывает тип этого раздела ( тип цикла числа π): показатель степени а_я - количество циклов π размерая. В полином индекса цикла из группа перестановок является средним из циклических индексов мономов его элементов. Фраза индикатор цикла также иногда используется вместо индекс цикла.

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

Группы перестановок и групповые действия

А биективный карта из набора Икс на себя называется перестановкой Икс, а множество всех перестановок Икс образует группу в составе отображений, называемых симметричная группа из Икс, и обозначил Сим(Икс). Каждый подгруппа Сима (Икс) называется группа перестановок из степень |Икс|.^[1] Позволять грамм быть абстрактная группа с групповой гомоморфизм φ из грамм в Sym (Икс). В изображение, φ (грамм), является группой перестановок. Групповой гомоморфизм можно рассматривать как средство, позволяющее группе грамм "действовать" на съемочной площадке Икс (используя перестановки, связанные с элементами грамм). Такой групповой гомоморфизм формально называется групповое действие а образ гомоморфизма есть перестановочное представление из грамм. У данной группы может быть много разных представлений перестановок, соответствующих различным действиям.^[2]

Предположим, что группа грамм действует на съемочной площадке Икс (то есть существует групповое действие). В комбинаторных приложениях интерес представляет множество Икс; например, подсчет вещей в Икс и зная, какие структуры могут быть оставлены неизменными грамм. Мало что теряется при работе с группами перестановок в такой настройке, поэтому в этих приложениях, когда группа рассматривается, это перестановочное представление группы, с которой будет работать, и, следовательно, действие группы должно быть указано. С другой стороны, алгебраистов больше интересуют сами группы, и их больше интересуют ядра действий группы, которые измеряют, сколько теряется при переходе от группы к ее перестановочному представлению.^[3]

Непересекающееся циклическое представление перестановок

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

${displaystyle left({egin{matrix}1&2&3&4&52&3&4&5&1end{matrix}}ight)}$

соответствует биекция на Икс = {1, 2, 3, 4, 5}, который отправляет 1 → 2, 2 → 3, 3 → 4, 4 → 5 и 5 → 1. Это можно прочитать из столбцов обозначения. Когда верхний ряд понимается как элементы Икс в соответствующем порядке нужно писать только вторую строку. В этой однострочной записи наш пример будет [2 3 4 5 1].^[4] Этот пример известен как циклическая перестановка потому что он «циклически меняет» числа, и третье обозначение для него будет (1 2 3 4 5). Этот обозначение цикла следует читать так: каждый элемент отправляется элементу справа, но последний элемент отправляется первому (он "циклически" переходит в начало). В обозначении цикла не имеет значения, где начинается цикл, поэтому (1 2 3 4 5), (3 4 5 1 2) и (5 1 2 3 4) все представляют собой одну и ту же перестановку. В длина цикла - количество элементов в цикле.

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

${displaystyle left({egin{matrix}1&2&3&4&5&62&1&3&5&6&4end{matrix}}ight)=(12)(3)(456).}$

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

Циклическую структуру перестановки можно закодировать как алгебраический моном в нескольких (дурачок ) переменными следующим образом: переменная необходима для каждой отдельной длины цикла циклов, которые появляются в циклической декомпозиции перестановки. В предыдущем примере было три разных длины цикла, поэтому мы будем использовать три переменные, а₁, а₂ и а₃ (как правило, используйте переменную а_k соответствовать длине k циклы). Переменная а_я будет повышен до j_я(грамм) мощность где j_я(грамм) - количество циклов длины я в разложении цикла перестановки грамм. Затем мы можем связать моном индекса цикла

${displaystyle prod _{k=1}^{n}a_{k}^{j_{k}(g)}}$

к перестановке грамм. Мономом индекса цикла в нашем примере будет а₁а₂а₃, а моном индекса цикла перестановки (1 2) (3 4) (5) (6 7 8 9) (10 11 12 13) (14) (15) будет а₁³а₂²а₄².

Определение

В индекс цикла из группа перестановок грамм - среднее значение одночленов индекса цикла всех перестановок грамм в грамм.

Более формально, пусть грамм группа перестановок порядка м и степень п.Каждая перестановка грамм в грамм имеет единственное разложение на непересекающиеся циклы, скажемc₁ c₂ c₃ ... .Пусть длина цикла c обозначим через |c|.

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

${displaystyle 0leq j_{k}(g)leq lfloor n/kfloor {mbox{ and }}sum _{k=1}^{n}k,j_{k}(g);=n.}$

Мы связываемся с грамм моном

${displaystyle prod _{cin g}a_{|c|}=prod _{k=1}^{n}a_{k}^{j_{k}(g)}}$

в переменных а₁, а₂, ..., а_п.

Тогда индекс цикла Z(грамм) из грамм дан кем-то

${displaystyle Z(G)={frac {1}{|G|}}sum _{gin G}prod _{k=1}^{n}a_{k}^{j_{k}(g)}.}$

Пример

Рассмотрим группу грамм из вращательная симметрия из квадрат в Евклидова плоскость. Такие симметрии полностью определяются изображениями только углов квадрата. Обозначив эти углы 1, 2, 3 и 4 (последовательно по часовой стрелке), мы можем представить элементы грамм как перестановки множества Икс = {1,2,3,4}.^[8] Перестановочное представление грамм состоит из четырех перестановок (1 4 3 2), (1 3) (2 4), (1 2 3 4) и e = (1) (2) (3) (4), которые представляют вращение против часовой стрелки на 90 °, 180 °, 270 ° и 360 ° соответственно. Обратите внимание, что тождественная перестановка e - единственная перестановка с неподвижными точками в этом представлении грамм. Как абстрактная группа, грамм известна как циклическая группа C₄, и это его перестановочное представление является его регулярное представительство. Мономы индекса цикла: а₄, а₂², а₄, и а₁⁴ соответственно. Таким образом, индекс цикла этой группы перестановок равен:

${displaystyle Z(C_{4})={frac {1}{4}}left(a_{1}^{4}+a_{2}^{2}+2a_{4}ight).}$

Группа C₄ также действует на неупорядоченные пары элементов Икс естественным образом. Любая перестановка грамм пошлет {Икс,у} → {Икс^грамм, у^грамм} (куда Икс^грамм это изображение элемента Икс при перестановке грамм).^[9] Набор Икс сейчас {А, B, C, D, E, F} куда А = {1,2}, B = {2,3}, C = {3,4}, D = {1,4}, E = {1,3} и F = {2,4}. Эти элементы можно рассматривать как стороны и диагонали квадрата или, в совершенно ином контексте, как края квадрата. полный график K₄. Действуя на этот новый набор, четыре элемента группы теперь представлены (А D C B)(E F), (А С)(B D)(E)(F), (А Б В Г)(E F) и e = (А)(B)(C)(D)(E)(F) и индекс цикла этого действия:

${displaystyle Z(C_{4})={frac {1}{4}}left(a_{1}^{6}+a_{1}^{2}a_{2}^{2}+2a_{2}a_{4}ight).}$

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

${displaystyle Z(C_{4})={frac {1}{4}}left(a_{1}^{16}+a_{2}^{8}+2a_{4}^{4}ight).}$

Виды действий

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

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

Симметричная группа S₃ в своем естественном действии имеет элементы^[10]

${displaystyle S_{3}={e,(23),(12),(123),(132),(13)}}$

Итак, его индекс цикла:

${displaystyle Z(S_{3})={frac {1}{6}}left(a_{1}^{3}+3a_{1}a_{2}+2a_{3}ight).}$

Группа перестановок грамм на съемочной площадке Икс является переходный если для каждой пары элементов Икс и у в Икс есть хотя бы один грамм в грамм такой, что у = Икс^грамм. Транзитивная группа перестановок - это обычный (или иногда упоминается как резко переходный), если единственная перестановка в группе, имеющая неподвижные точки, - это тождественная перестановка.

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

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

[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).

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

${displaystyle Z(C_{6})={frac {1}{6}}left(a_{1}^{6}+a_{2}^{3}+2a_{3}^{2}+2a_{6}ight).}$

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

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

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

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

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

${displaystyle Z(G)={frac {1}{6}}left(a_{1}^{3}+3a_{1}a_{2}+2a_{3}ight).}$

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

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

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

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

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

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

Индекс цикла группы перестановок ребер грамм из K₄ является:

${displaystyle Z(G)={frac {1}{24}}left(a_{1}^{6}+9a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}a_{4}ight).}$

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

Куб с цветными гранями

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

• Личность:

Есть одна такая перестановка, и ее вклад ${displaystyle a_{1}^{6}.}$

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

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

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

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

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

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

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

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

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

${displaystyle Z(C)={frac {1}{24}}left(a_{1}^{6}+6a_{1}^{2}a_{4}+3a_{1}^{2}a_{2}^{2}+8a_{3}^{2}+6a_{2}^{3}ight).}$

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

Идентификационная группа E_п

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

${displaystyle Z(E_{n})=a_{1}^{n}.}$

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

А циклическая группа, C_п группа поворотов регулярного п-гон, то есть п элементы, равномерно распределенные по кругу. Эта группа имеет φ (d) элементы порядка d для каждого делителя d из п, где φ (d) это Φ-функция Эйлера, что дает количество натуральных чисел меньше, чем d которые относительно просты с d. В регулярном представлении C_п, перестановка порядка d имеет п/d циклы длины d, таким образом:^[12]

${displaystyle Z(C_{n})={frac {1}{n}}sum _{d|n}varphi (d)a_{d}^{n/d}.}$

Группа диэдра D_п

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

${displaystyle Z(D_{n})={frac {1}{2}}Z(C_{n})+{egin{cases}{frac {1}{2}}a_{1}a_{2}^{(n-1)/2},&n{mbox{ odd, }}{frac {1}{4}}left(a_{1}^{2}a_{2}^{(n-2)/2}+a_{2}^{n/2}ight),&n{mbox{ even.}}end{cases}}}$

Чередующаяся группа А_п

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

${displaystyle Z(A_{n})=sum _{j_{1}+2j_{2}+3j_{3}+cdots +nj_{n}=n}{frac {1+(-1)^{j_{2}+j_{4}+cdots }}{prod _{k=1}^{n}k^{j_{k}}j_{k}!}}prod _{k=1}^{n}a_{k}^{j_{k}}.}$

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

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

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

${displaystyle Z(S_{n})=sum _{j_{1}+2j_{2}+3j_{3}+cdots +nj_{n}=n}{frac {1}{prod _{k=1}^{n}k^{j_{k}}j_{k}!}}prod _{k=1}^{n}a_{k}^{j_{k}}}$

это можно также выразить в терминах полного Полиномы Белла:

${displaystyle Z(S_{n})={frac {B_{n}(0!,a_{1},1!,a_{2},dots ,(n-1)!,a_{n})}{n!}}.}$

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

${displaystyle {frac {n!}{prod _{k=1}^{n}(k!)^{j_{k}}}}prod _{k=1}^{n}left({frac {k!}{k}}ight)^{j_{k}}prod _{k=1}^{n}{frac {1}{j_{k}!}}={frac {n!}{prod _{k=1}^{n}k^{j_{k}}j_{k}!}}.}$

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

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

${displaystyle Z(S_{n})={frac {1}{n!}}sum _{gin S_{n}}prod _{k=1}^{n}a_{k}^{j_{k}(g)}={frac {1}{n!}}sum _{l=1}^{n}{n-1 choose l-1};{frac {l!}{l}};a_{l};(n-l)!;Z(S_{n-l})}$

или же

${displaystyle Z(S_{n})={frac {1}{n}}sum _{l=1}^{n}a_{l};Z(S_{n-l}).}$

Приложения

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

${displaystyle Z(G)=Z(G;a_{1},a_{2},ldots ,a_{n}).}$

Позволять грамм группа, действующая на множестве Икс. грамм также вызывает действие на k-подмножества Икс и на k-наборы различных элементов Икс (видеть #Пример для случая k = 2), для 1 ≤ k ≤ п. Позволять ж_k и F_k обозначить количество орбиты из грамм в этих действиях соответственно. По соглашению мы полагаем ж₀ = F₀ = 1. Имеем:^[13]

а) обычная производящая функция за ж_k дан кем-то:

${displaystyle sum _{k=0}^{n}f_{k}t^{k}=Z(G;1+t,1+t^{2},ldots ,1+t^{n}),}$ и

б) экспоненциальная производящая функция за F_k дан кем-то:

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

Позволять грамм группа, действующая на множестве Икс и час функция от Икс к Y. Для любого грамм в грамм, час(Икс^грамм) также является функцией от Икс к Y. Таким образом, грамм индуцирует действие на множестве Y^Икс всех функций из Икс к Y. Число орбит этого действия равно Z (грамм; б, б, ...,б) куда б = |Y|.^[14]

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

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

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

Примечания

1. Диксон и Мортимер 1996, стр. 2, раздел 1.2 Симметричные группы
2. Кэмерон 1994, стр. 227–228
3. Кэмерон 1994, стр. 231, раздел 14.3
4. Этот стиль обозначений часто встречается в литературе по информатике.
5. Циклические перестановки - это функции, а термин товар действительно означает сочинение этих функций.
6. Вплоть до различных способов записи цикла и того факта, что непересекающиеся циклы коммутируют, поэтому их можно записывать в любом порядке.
7. Робертс и Тесман 2009, стр. 473
8. Технически мы используем понятие эквивалентности действий группы, заменяя грамм действуя на углы квадрата перестановочным представлением грамм действующий на Икс. Для наглядности эти детали лучше промазать.
9. Это обозначение распространено среди геометров и комбинатористов. Он используется вместо более распространенного g (x) по традиционным причинам.
10. Существует соглашение не записывать фиксированные точки в обозначении цикла для перестановки, но они должны быть представлены в индексе цикла.
11. Диксон и Мортимер 1996, стр. 9, следствие 1.4A (iii)
12. ван Линт и Уилсон 1992, стр. 464, Пример 35.1
13. Кэмерон 1994, стр. 248, Предложение 15.3.1
14. ван Линт и Уилсон 1992, стр. 463, теорема 35.1

Рекомендации

• Бруальди, Ричард А. (2010), «14. Pólya Counting», Вводная комбинаторика (5-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Прентис Холл, стр. 541–575, ISBN  978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), «15. Перечисление при групповом действии», Комбинаторика: темы, методы, алгоритмы, Кембридж: Издательство Кембриджского университета, стр. 245–256, ISBN  0-521-45761-0
• Диксон, Джон Д .; Мортимер, Брайан (1996), Группы перестановок, Нью-Йорк: Springer, ISBN  0-387-94599-7
• Робертс, Фред С .; Тесман, Барри (2009), «Индекс цикла 8.5», Прикладная комбинаторика (2-е изд.), Бока-Ратон: CRC Press, стр. 472–479, ISBN  978-1-4200-9982-9
• Такер, Алан (1995), «9.3 Индекс цикла», Прикладная комбинаторика (3-е изд.), Нью-Йорк: Wiley, стр. 365–371, ISBN  0-471-59504-7
• van Lint, J.H .; Уилсон, Р. (1992), "35.Pólya теории счета", Курс комбинаторики, Кембридж: Издательство Кембриджского университета, стр. 461–474, ISBN  0-521-42260-4

внешняя ссылка

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