Теорема перечисления Полиа , также известная как теорема Редфилда – Полиа и подсчет Полиа , является теоремой комбинаторики, которая следует из леммы Бернсайда о числе орбит действия группы на множестве и в конечном итоге обобщает ее . Теорема была впервые опубликована Дж. Ховардом Редфилдом в 1927 году. В 1937 году она была независимо заново открыта Джорджем Полиа , который затем значительно популяризировал результат, применив его ко многим задачам подсчета, в частности, к подсчету химических соединений .
Теорема перечисления Полиа была включена в символическую комбинаторику и теорию комбинаторных видов .
Упрощенная, невзвешенная версия
Пусть X быть конечное множество , и пусть G является группой из перестановок из X (или конечной группы симметрии , которая действует на X ). Набор X может представлять конечный набор бусинок, а G может быть выбранной группой перестановок бусинок. Например, если X - это ожерелье из n бусинок в круге, тогда важна вращательная симметрия, поэтому G - это циклическая группа C n , в то время как если X - браслет из n бусинок в круге, повороты и отражения имеют значение, поэтому G является группа диэдра D п порядка 2 п . Предположим далее, что Y - конечный набор цветов - цветов бусинок - так что Y X - это набор цветных комбинаций бусинок (более формально: Y X - это набор функций.) Тогда группа G действует на Y X . Теорема перечисления Полиа подсчитывает количество орбит под G раскрашенных бусинок по следующей формуле:
где это количество цветов и гр ( г ) есть число циклов группового элемента г , когда рассматриваются как перестановки X .
Полная, взвешенная версия
В более общей и более важной версии теоремы цвета также взвешиваются одним или несколькими способами, и может быть бесконечное количество цветов при условии, что набор цветов имеет производящую функцию с конечными коэффициентами. В одномерном случае предположим, что
является производящей функцией набора цветов, так что существует f w цветов веса w для каждого целого числа w ≥ 0. В многомерном случае вес каждого цвета является вектором целых чисел и существует производящая функция f ( t 1 , t 2 , ...), который табулирует количество цветов с каждым заданным вектором весов.
Теорема перечисления использует другую многомерную производящую функцию, называемую индексом цикла :
где п есть число элементов X и гр к ( г ) является количество к -циклам группового элемента г в качестве перестановки X .
Раскрашенная компоновка - это орбита действия G на множестве Y X (где Y - множество цветов, а Y X обозначает множество всех функций φ: X → Y ). Вес такого устройства определяется как сумма весов ф ( х ) по всем х в Х . Теорема утверждает, что производящая функция F числа раскрашенных по весу расстановок определяется выражением:
или в многомерном случае:
Чтобы перейти к упрощенной версии, данной ранее, если есть m цветов и все имеют вес 0, тогда f ( t ) = m и
В знаменитом применении подсчета деревьев (см. Ниже) и ациклических молекул расположение «цветных бусинок» на самом деле является расположением композиций, таких как ветви дерева с корнями. Таким образом, производящая функция f для цветов получается из производящей функции F для расположений, и теорема перечисления Полиа становится рекурсивной формулой.
Примеры
Ожерелья и браслеты
Цветные кубики
Сколько существует способов раскрасить стороны трехмерного куба m цветами, вплоть до вращения куба? Группа вращения C куба действует на шесть сторон куба, которые эквивалентны бусинкам. Его индекс цикла
который получается путем анализа действия каждого из 24 элементов C на 6 сторонах куба, подробности см. здесь .
Мы берем все цвета, чтобы они имели вес 0, и находим, что есть
разные расцветки.
Графы на трех и четырех вершинах
Граф на m вершинах можно интерпретировать как расположение разноцветных бусинок. Набор X "бусинок" - это наборвозможных краев, а набор цветов Y = {черный, белый} соответствует краям, которые присутствуют (черный) или отсутствуют (белый). Теорема перечисления Полиа может использоваться для вычисления количества графов с точностью до изоморфизма с фиксированным числом вершин или производящей функции этих графов в соответствии с количеством ребер, которые у них есть. Для последней цели мы можем сказать, что черное или существующее ребро имеет вес 1, а отсутствующее или белое ребро имеет вес 0. Таким образом,- производящая функция для набора цветов. Соответствующая группа симметриисимметрическая группа на м букв. Эта группа действует на множестве возможных ребер X : перестановка φ превращает ребро {a, b} в ребро {φ (a), φ (b)}. С этими определениями класс изоморфизма графов с m вершинами совпадает с орбитой действия G на множестве Y X раскрашенных расположений; количество ребер графа равно весу компоновки.
Восемь графов на трех вершинах (до определения изоморфных графов) показаны справа. Существует четыре класса изоморфизма графов, которые также показаны справа.
Индекс цикла группы S 3, действующей на множестве трех ребер, равен
(получено путем проверки структуры цикла действия элементов группы; см. здесь ). Таким образом, согласно теореме перечисления производящая функция графов на 3 вершинах с точностью до изоморфизма равна
что упрощает
Таким образом, есть по одному графу от 0 до 3 ребер.
Индекс цикла группы S 4, действующей на множестве из 6 ребер, равен
(см. здесь .) Следовательно
что упрощает
Эти графики показаны справа.
Укоренившиеся тройные деревья
Множество T 3 корневых троичных деревьев состоит из корневых деревьев, в которых каждый узел (или нелистовая вершина) имеет ровно три дочерних элемента (листья или поддеревья). Справа показаны маленькие тройные деревья. Обратите внимание, что корневые троичные деревья с n узлами эквивалентны корневым деревьям с n вершинами степени не выше 3 (без учета листьев). В общем, два корневых дерева изоморфны, когда одно может быть получено из другого путем перестановки дочерних элементов его узлов. Другими словами, группа, которая действует на потомков узла, является симметрической группой S 3 . Мы определяем вес такого троичного дерева как количество узлов (или нелистовых вершин).
Можно рассматривать троичное дерево с корнем как рекурсивный объект, который является либо листом, либо узлом с тремя дочерними элементами, которые сами являются корневыми троичными деревьями. Эти дети эквивалентны бусам; индекс цикла действующей на них симметрической группы S 3 равен
Теорема перечисления Пойа переводит рекурсивную структуру троичных корневых деревьев в функциональное уравнение для производящей функции F (t) корневых троичных деревьев по количеству узлов. Это достигается «раскрашиванием» трех дочерних элементов троичными корневыми деревьями, взвешенными по номеру узла, так что функция генерации цвета задается следующим образом: что по теореме перечисления дает
в качестве производящей функции для корневых троичных деревьев, взвешенных на единицу меньше, чем номер узла (поскольку сумма весов дочерних элементов не принимает во внимание корень), так что
Это эквивалентно следующей формуле рекурсии для числа t n корневых троичных деревьев с n узлами:
где a , b и c - неотрицательные целые числа.
Первые несколько значений находятся
Доказательство теоремы
Упрощенная форма теоремы о перечислении Полиа следует из леммы Бернсайда , которая гласит, что количество орбит раскраски является средним числом элементовфиксируется перестановкой g группы G по всем перестановкам g . Взвешенная версия теоремы имеет по существу такое же доказательство, но с уточненной формой леммы Бернсайда для взвешенного перечисления. Это равносильно применению леммы Бернсайда отдельно к орбитам разного веса.
Для наглядности обозначим быть переменные производящая функция F из. Учитывая вектор весов, позволять обозначим соответствующий мономиальный член f . Применение леммы Бернсайда к орбитам веса, количество орбит этого веса равно
где это набор раскрасок веса которые также фиксируются g . Если затем просуммировать все возможные веса, мы получим
Между тем, групповой элемент g со структурой цикла внесет срок
к индексу цикла G . Элемент g фиксирует элементтогда и только тогда, когда функция φ постоянна на каждом цикле q функции g . Для каждого такого цикла q производящая функция по весу | q | идентичных цветов из набора, перечисленного f ,
Отсюда следует, что производящая функция по весу точек, фиксированных g, является произведением указанного выше члена по всем циклам g , т. Е.
Подстановка этого в сумму по всем g дает замененный индекс цикла, как заявлено.
Смотрите также
Рекомендации
- Редфилд, Дж. Ховард (1927). "Теория групповых редуцированных распределений". Американский журнал математики . 49 (3): 433–455. DOI : 10.2307 / 2370675 . JSTOR 2370675 . Руководство по ремонту 1506633 .
- Фрэнк Харари ; Эд Палмер (1967). «Перечислительные методы Редфилда». Американский журнал математики . 89 (2): 373–384. DOI : 10.2307 / 2373127 . JSTOR 2373127 . Руководство по ремонту 0214487 .
- Г. Полиа (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen" . Acta Mathematica . 68 (1): 145–254. DOI : 10.1007 / BF02546665 .
- Г. Полиа; RC Read (1987). Комбинаторное перечисление групп, графов и химических соединений . Нью-Йорк: Springer-Verlag . ISBN 0-387-96413-4. Руководство по ремонту 0884155 .
Внешние ссылки
- Применение теоремы Пойи-Бернсайда о перечислении Гектора Зенила и Александра Павлика, The Wolfram Demonstrations Project .
- Вайсштейн, Эрик В. "Перечислительная теорема Поля" . MathWorld .
- Фредерик Чизак Перечисление спиртов и других классов химических молекул, пример теории Полиа .