Теорема Пойа

Теорема Пойа (также известная как лемма Бернсайда, лемма Коши — Фробениуса или лемма Бернсайда — Пойа) — это фундаментальный результат комбинаторики, который позволяет подсчитывать количество различных комбинаторных объектов (например, раскрасок, графов, молекулярных структур) с точностью до действия заданной группы симметрий. Теорема даёт явную формулу для числа орбит действия конечной группы на множестве, что эквивалентно числу классов эквивалентности объектов, которые считаются одинаковыми, если один может быть получен из другого применением некоторого преобразования симметрии.

История

Теорема имеет долгую историю, связанную с именами нескольких математиков. Первоначальный результат, известный как лемма Бернсайда, был сформулирован и доказан независимо друг от друга Августом Фердинандом Мёбиусом в 1832 году и Фредериком Уильямом Генри в 1897 году. Однако широкую известность она получила после публикации книги Уильяма Бернсайда «Теория групп конечного порядка» (1897), где он привёл её без ссылок на предшественников. Позднее, в 1937 году, венгерский математик Дьёрдь Пойа (George Pólya) значительно обобщил этот результат, создав мощный инструмент для подсчёта числа неизоморфных графов, химических соединений и других структур. Его работа «Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen» («Комбинаторные определения количества для групп, графов и химических соединений») заложила основы современной перечислительной комбинаторики. В честь Пойа обобщённая версия часто называется теоремой Пойа или теоремой Пойа — Редфилда (Редфилд также внёс вклад в 1927 году, но его работа осталась незамеченной).

Формулировка

Лемма Бернсайда (частный случай)

Пусть \( G \) — конечная группа, действующая на конечном множестве \( X \). Для каждого элемента \( g \in G \) обозначим через \( \operatorname{Fix}(g) \) количество элементов множества \( X \), которые остаются неподвижными под действием \( g \) (то есть \( g(x) = x \)). Тогда число орбит действия \( G \) на \( X \) (обозначаемое \( N \)) равно среднему арифметическому числа неподвижных точек по всем элементам группы:

\[ N = \frac{1}{|G|} \sum_{g \in G} \operatorname{Fix}(g). \]

Теорема Пойа (обобщение)

Теорема Пойа позволяет подсчитывать число орбит не просто для множества \( X \), а для множества функций из одного множества в другое, с учётом действия группы на области определения. Пусть \( D \) — множество «мест» (например, вершин или граней), \( R \) — множество «цветов» (или меток), и \( G \) — группа перестановок на \( D \). Рассмотрим множество всех функций \( f: D \to R \). Группа \( G \) действует на этом множестве по правилу: \( (g \cdot f)(d) = f(g^{-1}(d)) \). Теорема Пойа даёт формулу для числа орбит этого действия, то есть числа различных раскрасок с точностью до симметрий.

Формула использует цикловой индекс группы \( G \):

\[ Z(G) = \frac{1}{|G|} \sum_{g \in G} \prod_{i=1}^{n} s_i^{c_i(g)}, \]

где \( n = |D| \), \( c_i(g) \) — число циклов длины \( i \) в перестановке \( g \), а \( s_i \) — переменные.

Тогда число орбит \( N \) для раскраски в \( |R| = m \) цветов равно:

\[ N = Z(G) \left( s_1 = m, s_2 = m, \dots, s_n = m \right) = \frac{1}{|G|} \sum_{g \in G} m^{c(g)}, \]

где \( c(g) \) — общее число циклов в перестановке \( g \) (включая циклы длины 1).

Более общая версия, теорема Пойа — Редфилда, позволяет подсчитывать количество раскрасок с заданным числом цветов каждого типа, используя производящие функции.

Примеры применения

Пример 1: Раскраска квадрата

Рассмотрим квадрат, вершины которого можно раскрашивать в два цвета (например, чёрный и белый). Группа симметрий квадрата — диэдральная группа \( D_4 \), состоящая из 8 элементов: 4 поворота (на 0°, 90°, 180°, 270°) и 4 отражения (относительно осей симметрии). Необходимо найти число различных раскрасок вершин, считая одинаковыми те, которые можно совместить поворотом или отражением.

Применим лемму Бернсайда. Множество \( X \) — все возможные раскраски вершин (их \( 2^4 = 16 \)). Для каждого элемента группы подсчитаем число неподвижных раскрасок:

• Тождественное преобразование: все 16 раскрасок неподвижны.
• Поворот на 90°: неподвижны только те раскраски, где все вершины одного цвета (2 варианта: все чёрные или все белые).
• Поворот на 180°: неподвижны раскраски, где противоположные вершины одинаковы. Это даёт \( 2^2 = 4 \) варианта (цвета для двух пар).
• Поворот на 270°: аналогично повороту на 90° — 2 варианта.
• Отражения относительно осей, проходящих через середины противоположных сторон: неподвижны раскраски, где вершины, симметричные относительно оси, одинаковы. Таких раскрасок \( 2^2 = 4 \) для каждого из двух таких отражений.
• Отражения относительно диагоналей: неподвижны раскраски, где вершины на диагонали одинаковы, а две другие — произвольны. Это даёт \( 2^3 = 8 \) вариантов для каждого из двух таких отражений.

Сумма неподвижных точек: \( 16 + 2 + 4 + 2 + 4 + 4 + 8 + 8 = 48 \). Делим на \( |G| = 8 \), получаем \( N = 6 \). Таким образом, существует 6 различных раскрасок вершин квадрата двумя цветами с точностью до симметрий.

Пример 2: Химические изомеры

Теорема Пойа широко применяется в химии для подсчёта числа изомеров органических соединений. Например, для подсчёта числа различных структур бензольного кольца \( C_6H_6 \) с заместителями. Группа симметрий правильного шестиугольника (диэдральная группа \( D_6 \)) позволяет определить, сколько различных химических соединений может быть получено при замене атомов водорода на другие группы.

Связь с другими областями

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

Интересные факты

• Лемма Бернсайда часто ошибочно приписывается только Бернсайду, хотя он сам ссылался на Фробениуса. Историки математики установили, что первым её доказал Мёбиус.
• Дьёрдь Пойа, эмигрировавший в США, был не только математиком, но и популяризатором науки. Его книга «Как решать задачу» стала классикой педагогики.
• Теорема Пойа используется в кристаллографии для подсчёта числа возможных кристаллических решёток и в компьютерной графике для генерации симметричных текстур.
• В 2020 году российские математики из МГУ имени М. В. Ломоносова применили обобщение теоремы Пойа для подсчёта числа состояний в квантовых системах с симметриями.

Источники

• Бернсайд У. «Теория групп конечного порядка». — М.: Наука, 1969.
• Пойа Д., Редфилд Дж. «Комбинаторная математика». — М.: Мир, 1975.
• Харари Ф., Палмер Э. «Перечисление графов». — М.: Мир, 1977.
• Сачков В. Н. «Введение в комбинаторные методы дискретной математики». — М.: Наука, 1982.
• Голдман Дж. «Теория перечисления Пойа». — В сб.: «Прикладная комбинаторика». — М.: Мир, 1968.