Индекс цикла

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

Каждая перестановка π конечного набора объектов разбивает это множество на циклы ; моном индекса цикла π — это моном от переменных 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]

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

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

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

Примечания

1. Dixon & Mortimer 1996, стр. 2, раздел 1.2 Симметрические группы
2. Кэмерон 1994, стр. 227–228.
3. Кэмерон 1994, стр. 231, раздел 14.3
4. Этот стиль записи часто встречается в литературе по информатике.
5. Циклические перестановки являются функциями, а термин «произведение» на самом деле означает композицию этих функций.
6. Вплоть до различных способов записи цикла и того факта, что непересекающиеся циклы коммутируют, поэтому их можно записывать в любом порядке.
7. Робертс и Тесман 2009, стр. 473
8. Технически мы используем понятие эквивалентности групповых действий, заменяя G , действующую на углы квадрата, на перестановочное представление G , действующей на X. Для целей изложения лучше пропустить эти детали.
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. Подсчет по методу Пойя», Вводная комбинаторика (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 .