Теорема перечисления Полиа

Формула для числа орбит группового действия

Теорема о перечислении Полиа , также известная как теорема Редфилда–Полиа и подсчёт Полиа , — теорема в комбинаторике , которая одновременно следует из леммы Бернсайда о числе орбит действия группы на множестве и в конечном счёте её обобщает . Теорема была впервые опубликована Дж. Говардом Редфилдом в 1927 году. В 1937 году она была независимо переоткрыта Джорджем Полиа , который затем значительно популяризировал результат, применив его ко многим задачам подсчёта, в частности к перечислению химических соединений .

Теорема перечисления Полиа была включена в символическую комбинаторику и теорию комбинаторных видов .

Упрощенная, невзвешенная версия

Пусть X — конечное множество , а G — группа перестановок X (или конечная группа симметрии , действующая на X ). Множество X может представлять собой конечное множество бусин, а G — выбранную группу перестановок бусин. Например, если X — ожерелье из n бусин в круге, то имеет значение вращательная симметрия , поэтому G — циклическая группа C _n , а если X — браслет из n бусин в круге, то имеют значение вращения и отражения , поэтому G — диэдральная группа D _n порядка 2 n . Предположим далее, что Y — конечное множество цветов — цветов бусин — так что Y ^X — множество цветных расположений бусин (более формально: Y ^X — множество функций .) Тогда группа G действует на Y ^X . Теорема перечисления Полиа подсчитывает количество орбит под G цветных расположений бусин по следующей формуле: ${\displaystyle X\to Y}$

${\displaystyle \left|Y^{X}/G\right|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}}$

где — число цветов, а c ( g ) — число циклов элемента группы g, рассматриваемого как перестановка X. ${\displaystyle m=|Y|}$

Полная, утяжеленная версия

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

${\displaystyle f(t)=f_{0}+f_{1}t+f_{2}t^{2}+\cdots }$

— производящая функция набора цветов, так что для каждого целого числа w ≥ 0 имеется f _w цветов веса w. В многомерном случае вес каждого цвета представляет собой вектор целых чисел, и существует производящая функция f ( t ₁ , t ₂ , ...), которая табулирует количество цветов с каждым заданным вектором весов.

Теорема перечисления использует другую многомерную производящую функцию, называемую индексом цикла :

${\displaystyle Z_{G}(t_{1},t_{2},\ldots ,t_{n})={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{c_{1}(g)}t_{2}^{c_{2}(g)}\cdots t_{n}^{c_{n}(g)}}$

где n — число элементов X , а c _k ( g ) — число k -циклов элемента группы g как перестановки X.

Цветная расстановка — это орбита действия G на множестве Y ^X (где Y — множество цветов, а Y ^X обозначает множество всех функций φ: X → Y ). Вес такой расстановки определяется как сумма весов φ( x ) по всем x в X . Теорема утверждает, что производящая функция F числа цветных расстановок по весу определяется как:

${\displaystyle F(t)=Z_{G}(f(t),f(t^{2}),f(t^{3}),\ldots ,f(t^{n}))}$

или в многомерном случае:

${\displaystyle F(t_{1},t_{2},\ldots )=Z_{G}(f(t_{1},t_{2},\ldots ),f(t_{1}^{2},t_{2}^{2},\ldots ),f(t_{1}^{3},t_{2}^{3},\ldots ),\ldots ,f(t_{1}^{n},t_{2}^{n},\ldots )).}$

Если свести к упрощенной версии, приведенной ранее, если имеется m цветов и все они имеют вес 0, то f ( t ) =  m и

${\displaystyle \left|Y^{X}/G\right|=F(0)=Z_{G}(m,m,\ldots ,m)={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}.}$

В знаменитом применении счетных деревьев (см. ниже) и ациклических молекул расположение «цветных бусин» на самом деле является расположением расположений, например, ветвей корневого дерева. Таким образом, производящая функция f для цветов выводится из производящей функции F для расположений, а теорема перечисления Полиа становится рекурсивной формулой.

Примеры

Ожерелья и браслеты

Цветные кубики

Сколько существует способов раскрасить грани трехмерного куба в m цветов с точностью до поворота куба? Группа вращения C куба действует на шесть граней куба, которые эквивалентны бусинам. Ее индекс цикла равен

${\displaystyle Z_{C}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}\right)}$

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

Мы берем все цвета с весом 0 и обнаруживаем, что есть

${\displaystyle F(0)=Z_{C}(m,m,m,m)={\frac {1}{24}}\left(m^{6}+3m^{4}+12m^{3}+8m^{2}\right)}$

разные расцветки.

Графы на трех и четырех вершинах

Граф на m вершинах можно интерпретировать как расположение цветных бусин. Множество X «бусин» — это множество возможных ребер, в то время как множество цветов Y = {черный, белый} соответствует ребрам, которые присутствуют (черный) или отсутствуют (белый). Теорема перечисления Полиа может быть использована для вычисления числа графов с точностью до изоморфизма с фиксированным числом вершин или производящей функции этих графов в соответствии с числом имеющихся у них ребер. Для последней цели можно сказать, что черное или присутствующее ребро имеет вес 1, а отсутствующее или белое ребро имеет вес 0. Таким образом, это производящая функция для множества цветов. Соответствующая группа симметрии — это симметрическая группа на m буквах. Эта группа действует на множество X возможных ребер: перестановка φ превращает ребро {a, b} в ребро {φ(a), φ(b)}. При этих определениях класс изоморфизма графов с m вершинами совпадает с орбитой действия G на множестве Y ^X цветных расположений; число ребер графа равно весу расположения. ${\displaystyle {\binom {m}{2}}}$ ${\displaystyle f(t)=1+t}$ ${\displaystyle G=S_{m},}$

Все графы на трех вершинах

Неизоморфные графы на трех вершинах

Восемь графов на трех вершинах (до определения изоморфных графов) показаны справа. Существует четыре класса изоморфизма графов, также показанных справа.

Индекс цикла группы S _{3 ,} действующей на множестве из трех ребер, равен

${\displaystyle Z_{G}(t_{1},t_{2},t_{3})={\frac {1}{6}}\left(t_{1}^{3}+3t_{1}t_{2}+2t_{3}\right)}$

(получено путем проверки структуры цикла действия элементов группы; см. здесь ). Таким образом, согласно теореме о перечислении, производящая функция графов на 3 вершинах с точностью до изоморфизма равна

${\displaystyle F(t)=Z_{G}\left(t+1,t^{2}+1,t^{3}+1\right)={\frac {1}{6}}\left((t+1)^{3}+3(t+1)(t^{2}+1)+2(t^{3}+1)\right),}$

что упрощается до

${\displaystyle F(t)=t^{3}+t^{2}+t+1.}$

Таким образом, существует один граф, имеющий от 0 до 3 ребер.

Классы изоморфизма графов на четырех вершинах.

Индекс цикла группы S _{4 ,} действующей на множестве из 6 ребер, равен

${\displaystyle Z_{G}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}t_{4}\right)}$

(см. здесь .) Следовательно

${\displaystyle F(t)=Z_{G}\left(t+1,t^{2}+1,t^{3}+1,t^{4}+1\right)={\frac {(t+1)^{6}+9(t+1)^{2}(t^{2}+1)^{2}+8(t^{3}+1)^{2}+6(t^{2}+1)(t^{4}+1)}{24}}}$

что упрощается до

${\displaystyle F(t)=t^{6}+t^{5}+2t^{4}+3t^{3}+2t^{2}+t+1.}$

Эти графики показаны справа.

Укорененные тройчатые деревья

Множество T ₃ корневых тернарных деревьев состоит из корневых деревьев, где каждый узел (или нелистовая вершина) имеет ровно три потомка (листья или поддеревья). Маленькие тернарные деревья показаны справа. Обратите внимание, что корневые тернарные деревья с n узлами эквивалентны корневым деревьям с n вершинами степени не более 3 (игнорируя листья). В общем случае два корневых дерева изоморфны, когда одно может быть получено из другого путем перестановки потомков его узлов. Другими словами, группа, которая действует на потомков узла, является симметрической группой S ₃ . Мы определяем вес такого тернарного дерева как количество узлов (или нелистовых вершин).

Укорененные тернарные деревья на 0, 1, 2, 3 и 4 узлах (=нелистовые вершины). Корень показан синим цветом, листья не показаны. Каждый узел имеет столько листьев, чтобы число его потомков было равно 3.

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

${\displaystyle Z_{S_{3}}(t_{1},t_{2},t_{3})={\frac {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.}$

Теорема перечисления Полиа переводит рекурсивную структуру корневых тернарных деревьев в функциональное уравнение для производящей функции F(t) корневых тернарных деревьев по числу узлов. Это достигается путем «раскрашивания» трех дочерних элементов корневыми тернарными деревьями, взвешенными по числу узлов, так что функция, производящая цвет, задается с помощью которой по теореме перечисления получается ${\displaystyle f(t)=F(t)}$

${\displaystyle {\frac {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}}$

как производящая функция для корневых троичных деревьев, взвешенная на единицу меньше номера узла (поскольку сумма весов дочерних узлов не учитывает корень), так что

${\displaystyle F(t)=1+t\cdot {\frac {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}.}$

Это эквивалентно следующей рекуррентной формуле для числа t _n корневых троичных деревьев с n узлами:

${\displaystyle {\begin{aligned}t_{0}&=1\\t_{n+1}&={\frac {1}{6}}\left(\sum _{a+b+c=n}t_{a}t_{b}t_{c}+3\sum _{a+2b=n}t_{a}t_{b}+2\sum _{3a=n}t_{a}\right)\end{aligned}}}$

где a , b и c — неотрицательные целые числа.

Первые несколько значений : ${\displaystyle t_{n}}$

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (последовательность A000598 в OEIS ).

Доказательство теоремы

Упрощенная форма теоремы о перечислении Полиа следует из леммы Бернсайда , которая гласит, что число орбит раскрасок является средним числом элементов, зафиксированных перестановкой g группы G, по всем перестановкам g . Взвешенная версия теоремы имеет по сути то же доказательство, но с уточненной формой леммы Бернсайда для взвешенного перечисления. Это эквивалентно применению леммы Бернсайда отдельно к орбитам разного веса. ${\displaystyle Y^{X}}$

Для более ясной записи, пусть будут переменными производящей функции f для . Для данного вектора весов пусть обозначает соответствующий мономиальный член f . Применяя лемму Бернсайда к орбитам веса , число орбит этого веса равно ${\displaystyle x_{1},x_{2},\ldots }$ ${\displaystyle Y}$ ${\displaystyle \omega }$ ${\displaystyle x^{\omega }}$ ${\displaystyle \omega }$

${\displaystyle {\frac {1}{|G|}}\sum _{g\in G}\left|(Y^{X})_{\omega ,g}\right|}$

где — множество раскрасок веса , которые также фиксируются g . Если затем просуммировать по всем возможным весам, то получим ${\displaystyle (Y^{X})_{\omega ,g}}$ ${\displaystyle \omega }$

${\displaystyle F(x_{1},x_{2},\ldots )={\frac {1}{|G|}}\sum _{g\in G,\omega }x^{\omega }\left|(Y^{X})_{\omega ,g}\right|.}$

Между тем элемент группы g с циклической структурой будет вносить вклад в член ${\displaystyle j_{1}(g),j_{2}(g),\ldots ,j_{n}(g)}$

${\displaystyle t_{1}^{j_{1}(g)}t_{2}^{j_{2}(g)}\cdots t_{n}^{j_{n}(g)}}$

индексу цикла G . Элемент g фиксирует элемент тогда и только тогда, когда функция φ постоянна на каждом цикле q из g . Для каждого такого цикла q производящая функция по весу | q | одинаковых цветов из множества, перечисленного f , равна ${\displaystyle \phi \in Y^{X}}$

${\displaystyle f\left(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots \right).}$

Отсюда следует, что производящая функция по весу точек, зафиксированных g, является произведением вышеуказанного члена по всем циклам g , т.е.

${\displaystyle {\begin{aligned}\sum _{\omega }x^{\omega }\left|(Y^{X})_{\omega ,g}\right|&=\prod _{q{\text{ cycle of }}g}f\left(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots \right)\\&=f(x_{1},x_{2},\ldots )^{j_{1}(g)}f\left(x_{1}^{2},x_{2}^{2},\ldots \right)^{j_{2}(g)}\cdots f\left(x_{1}^{n},x_{2}^{n},\ldots \right)^{j_{n}(g)}\end{aligned}}}$

Подстановка этого в сумму по всем g дает подставленный индекс цикла, как и заявлено.

Смотрите также

• Теорема о маркированном перечислении

Ссылки

• Редфилд, Дж. Говард (1927). «Теория распределений с редукцией групп». American Journal of Mathematics . 49 (3): 433–455. doi :10.2307/2370675. JSTOR  2370675. MR  1506633.
• Фрэнк Харари ; Эд Палмер (1967). «Методы перечисления Редфилда». Американский журнал математики . 89 (2): 373–384. doi :10.2307/2373127. JSTOR  2373127. MR  0214487.
• Г. Полиа (1937). «Комбинаторный препарат для групп, графен и химия». Акта Математика . 68 (1): 145–254. дои : 10.1007/BF02546665 .
• G. Pólya; RC Read (1987). Комбинаторное перечисление групп, графов и химических соединений . Нью-Йорк: Springer-Verlag . ISBN 0-387-96413-4. МР  0884155.

Внешние ссылки

• Применение теоремы о перечислении Пойа-Бернсайда Гектора Зенила и Александра Павлика, Проект демонстраций Вольфрама .
• Вайсштейн, Эрик В. «Теорема перечисления Полиа». MathWorld .
• Фредерик Чизак Перечисление спиртов и других классов химических молекул, пример теории Пойа.