Индекс цикла

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

Каждая перестановка π конечного набора объектов разбивает набор на циклы ; индекс цикла мономиальной П является мономиальной в переменных ₁ , ₂ , ... , который описывает тип этого раздел ( тип цикла П): показатель в _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) (14) (15) будет ₁ ¹ ₂ ⁴ ₄ ² .

Определение [ править ]

Индекс цикла из группы перестановок 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 ° соответственно. Обратите внимание , что тождественная перестановка е единственная перестановка с фиксированными точками в этом представлении G . Как абстрактная группа G известна как циклическая группа C ₄ , и это ее перестановочное представление является ее регулярным представлением . Индекс цикла мономы ₄ , ₂ ² , ₄ и ₁ ⁴ соответственно. Таким образом, индекс цикла этой группы перестановок равен:

${\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 существует, по крайней мере , один г в 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 ₃ в его естественном действии, приведенные выше) индуцирует ребро перестановки. Это перестановки:

• Тождество: никакие вершины и ребра не переставляются; вклад${\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 _3, а индекс цикла равен Z ( S ₃ ). Это не так для полных графов с более чем тремя вершинами, поскольку у них строго больше ребер ( ), чем вершин ( n ).${\displaystyle {\binom {n}{2}}}$

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

Это полностью аналогично случаю трех вершин. Это перестановки вершин ( 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).}$

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

Идентификационная группа E _n [ править ]

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

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

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

Группа диэдра D _n [ править ]

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

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

Альтернативная группа A _n [ править ]

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

${\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 [ править ]

Индекс цикла симметрической группы 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}!}}.}$

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

Приложения [ править ]

В этом разделе мы немного изменим обозначение индексов цикла, явно включив имена переменных. Таким образом, теперь для группы перестановок 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 и ч функцию из X в Y . Для любого г в G , ч ( х ^г ) также является функцией от X к Y . Таким образом, G индуцирует действие на множестве Y ^X всех функций из X в Y . Число орбит этого действия равно Z ( G ; b , b , ..., b ), где b = | Y |,^[14]

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

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

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

Примечания [ править ]

Ссылки [ править ]

• Brualdi, Ричард А. (2010), "14. Pólya Counting", Введение в комбинаторику (5-е изд.), Верхняя Сэдл-Ривер, Нью-Джерси: Prentice Hall, стр. 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 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 .