Индекс цикла

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

Каждая перестановка π конечного набора объектов разбивает это множество на циклы ; моном индекса цикла π — это моном от переменных a ₁ , a ₂ , … , который описывает тип цикла этого разбиения: показатель степени a _i — это количество циклов π размера  i . Полином индекса цикла группы перестановок — это среднее арифметическое мономов индекса цикла ее элементов. Иногда вместо индекса цикла используется также фраза индикатор цикла .

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

Биективное отображение множества X на себя называется перестановкой X , а множество всех перестановок X образует группу относительно композиции отображений, называемую симметрической группой X , и обозначается Sym( X  ). Каждая подгруппа Sym( X  ) называется группой перестановок степени | X  |. ^[1] Пусть G — абстрактная группа с групповым гомоморфизмом φ из G в Sym( X  ). Образ , φ( G ), является группой перестановок. Групповой гомоморфизм можно рассматривать как средство, позволяющее группе G «действовать» на множестве X (используя перестановки , связанные с элементами G ). Такой групповой гомоморфизм формально называется представлением перестановки G . Данная группа может иметь много различных представлений перестановок, соответствующих различным действиям. ^[2]

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

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

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

соответствует биекции на X = {1, 2, 3, 4, 5}, которая отправляет 1 ↦ 2, 2 ↦ 3, 3 ↦ 4, 4 ↦ 5 и 5 ↦ 1. Это можно прочитать из столбцов нотации. Когда верхняя строка понимается как элементы X в соответствующем порядке, нужно записать только вторую строку. В этой однострочной нотации наш пример будет [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({\begin{matrix}1&2&3&4&5&6\\2&1&3&5&6&4\end{matrix}}\right)=(12)(3)(456).}$

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

Структура цикла перестановки может быть закодирована как алгебраический моном в нескольких ( фиктивных ) переменных следующим образом: переменная необходима для каждой отдельной длины цикла циклов, которые появляются в разложении цикла перестановки. В предыдущем примере было три различных длины цикла, поэтому мы будем использовать три переменные, a ₁ , a ₂ и a ₃ (в общем случае, используйте переменную a _k для соответствия циклам длины k ). Переменная a _i будет возведена в степень j _i  ( g ), где j _i  ( g ) — это количество циклов длины i в разложении цикла перестановки g . Затем мы можем связать моном индекса цикла

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

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

Индекс цикла группы перестановок G — это среднее арифметическое мономов индекса цикла всех перестановок g в G.

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

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

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

Связываем с g одночлен

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

в переменных a ₁ , a ₂ , ..., a _n .

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

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

Рассмотрим группу G вращательных симметрий квадрата в евклидовой плоскости . Ее элементы полностью определяются образами только углов квадрата. Обозначив эти углы 1, 2, 3 и 4 (последовательно идя по часовой стрелке, скажем), мы можем представить элементы G как перестановки множества X = {1,2,3,4}. ^[8] Перестановочное представление 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 ₄ , и это ее перестановочное представление является ее регулярным представлением . Индексные мономы цикла равны a ₄ , a ₂ ² , a ₄ и a ₁ ⁴ соответственно. Таким образом, индекс цикла этой перестановочной группы равен:

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

Группа C ₄ также действует на неупорядоченные пары элементов X естественным образом. Любая перестановка g переведет { x , y } → { x ^g , y ^g } (где x ^g — образ элемента x при перестановке g ). ^[9] Множество 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}. Эти элементы можно рассматривать как стороны и диагонали квадрата или, в совершенно иной обстановке, как ребра полного графа K ₄ . Действуя на этот новый набор, четыре элемента группы теперь представлены как ( A D C B )( E F ), ( AC )( BD )( E )( F ), ( ABCD )( EF ) и e = ( A )( 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}\right).}$

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

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

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

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

Симметрическая группа 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}\right).}$

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

Конечная транзитивная группа перестановок G на множестве X является регулярной тогда и только тогда, когда | G | = | X  |. ^[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}\right).}$

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

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

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

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

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

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

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

• Тождество: эта перестановка отображает все вершины (и, следовательно, ребра) в себя, и вклад равен${\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 градусов.

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

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

Рассмотрим обычный куб в трехмерном пространстве и его группу симметрий, назовем ее 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}\right).}$

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

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

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

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

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

${\displaystyle Z(D_{n})={\frac {1}{2}}Z(C_{n})+{\begin{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}\right),&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 _n в ее естественном действии определяется формулой:

${\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!}}.}$

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

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

Формулу можно еще больше упростить, если мы просуммируем индексы циклов по каждому , используя при этом дополнительную переменную для отслеживания общего размера циклов:${\displaystyle n}$${\displaystyle y}$

${\displaystyle \sum \limits _{n\geq 1}y^{n}Z(S_{n})=\sum \limits _{n\geq 1}\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}\prod _{k=1}^{n}{\frac {a_{k}^{j_{k}}y^{kj_{k}}}{k^{j_{k}}j_{k}!}}=\prod \limits _{k\geq 1}\sum \limits _{j_{k}\geq 0}{\frac {(a_{k}y^{k})^{j_{k}}}{k^{j_{k}}j_{k}!}}=\prod \limits _{k\geq 1}\exp \left({\frac {a_{k}y^{k}}{k}}\right),}$

таким образом, давая упрощенную форму для индекса цикла :${\displaystyle S_{n}}$

${\displaystyle {\begin{aligned}Z(S_{n})&=[y^{n}]\prod \limits _{k\geq 1}\exp \left({\frac {a_{k}y^{k}}{k}}\right)\\&=[y^{n}]\exp \left(\sum \limits _{k\geq 1}{\frac {a_{k}y^{k}}{k}}\right).\end{aligned}}}$

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

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

${\displaystyle Z(S_{n})={\frac {1}{n!}}\sum _{g\in S_{n}}\prod _{k=1}^{n}a_{k}^{j_{k}(g)}={\frac {1}{n!}}\sum _{l=1}^{n}{n-1 \choose l-1}\;(l-1)!\;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}).}$

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

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

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

а) Обычная производящая функция для f _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).}$

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

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

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

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

• Бруальди, Ричард А. (2010), «14. Подсчет по методу Пойя», Вводная комбинаторика (5-е изд.), Аппер Сэдл Ривер, Нью-Джерси: Prentice Hall, стр. 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
• ван Линт, Дж. Х.; Уилсон, Р. М. (1992), "35. Теория подсчета Пойя", Курс комбинаторики , Кембридж: Издательство Кембриджского университета, стр. 461–474, ISBN 0-521-42260-4

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