Индекс цикла

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

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

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

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

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

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

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

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

$\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]. Этот пример известен как циклическая перестановка , потому что он «циклирует» числа, и третье обозначение для него будет (1 2 3 4 5). Это обозначение цикла следует читать так: каждый элемент отправляется элементу справа от него, но последний элемент отправляется первому (он «циклически» переходит в начало). При обозначении цикла не имеет значения, где начинается цикл, поэтому (1 2 3 4 5), (3 4 5 1 2) и (5 1 2 3 4) представляют собой одну и ту же перестановку. Длина цикла — это количество элементов в цикле.

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

$\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 циклов). Переменная ai _ji будет возведена в ( _ji g ) , где ( _g степень ) — количество циклов длины i в циклическом разложении перестановки g . Затем мы можем связать моном индекса цикла

$\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 ₄ ² .

Определение

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

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

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

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

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

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

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

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

$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}. Представление перестановок 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 ₂ ² , 4 _​ и 1 _​ ⁴ соответственно. Таким образом, индекс цикла этой группы перестановок равен:

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

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

$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 ^г , и ^г ) (в этом случае мы также имели бы упорядоченные пары вида ( x , x )). Элементы X можно рассматривать как дуги полного орграфа D ₄ (с петлями в каждой вершине). Индекс цикла в этом случае будет:

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

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

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

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

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

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

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

$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 на множестве X регулярна тогда и только тогда, когда | г | = | Х |. Теорема Кэли утверждает, что каждая абстрактная группа имеет регулярное представление перестановок, заданное группой, действующей на себя (как множество) путем (правого) умножения. Это называется регулярным представлением группы.

Циклическая группа 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Личность:

Существует одна такая перестановка, и ее вклад равен $a_{1}^{6}.$

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

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

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

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

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

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

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

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

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

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

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

Группа En _{идентификации}

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

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

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

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

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

Группа диэдра D _n

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

$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}}$

Переменная группа А _н

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

$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 нужно, потому что ${\frac {1}{|A_{n}|}}={\frac {2}{n!}}$.

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

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

$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}}$

это также можно сформулировать в терминах полных полиномов Белла :

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

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

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

Формулу можно еще упростить, если просуммировать индексы цикла за каждый $n$, используя дополнительную переменную $y$ чтобы отслеживать общий размер циклов:

$\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),$

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

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

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

Это приводит к повторению

$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})$

или

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

Приложения

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

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

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

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

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

б) Экспоненциальная производящая функция для F _k определяется выражением:

$\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 ^г является функцией от X до Y. ) также Таким образом, G индуцирует действие на множестве Y ^Х всех функций X до Y. от Число орбит этого действия равно Z( G ; b , b , ..., b ), где b = | Ю |.

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

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

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

Ссылки

• Бруальди, Ричард А. (2010), «14. Подсчет Полиа», Вводная комбинаторика (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
• Робертс, Фред С.; Тесман, Барри (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. дои : 10.1016/S0024-3795(96)00530-7 .
• Харальд Фрипертингер (1992). «Счет в теории музыки» . Вклад в электронную музыку . 1 .