Лемма Бернсайда

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

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

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

\[ \text{Fix}(g) = |\{ x \in X \mid g \cdot x = x \}| \]

Тогда число орбит действия \( G \) на \( X \) (обозначаемое \( |X/G| \)) равно среднему арифметическому числа неподвижных точек по всем элементам группы:

\[ |X/G| = \frac{1}{|G|} \sum_{g \in G} \text{Fix}(g) \]

Здесь орбита — это множество элементов \( X \), которые могут быть переведены друг в друга действием группы. Таким образом, лемма даёт способ подсчёта количества классов эквивалентности, где два элемента эквивалентны, если один переводится в другой элементом группы.

История

Лемма названа в честь британского математика Уильяма Бернсайда, который опубликовал её в своей книге «Теория групп конечного порядка» (1897). Однако исторически она была известна ранее: её доказал Огюстен Луи Коши в 1845 году, а затем Фердинанд Георг Фробениус в 1887 году. Бернсайд не претендовал на авторство и ссылался на Фробениуса, но в англоязычной литературе название закрепилось. В русскоязычной традиции часто используется термин «лемма Коши — Фробениуса».

Доказательство

Доказательство основано на подсчёте количества пар \( (g, x) \in G \times X \), таких что \( g \cdot x = x \), двумя способами.

1. Первый способ: для каждого элемента группы \( g \) подсчитывается количество неподвижных точек \( \text{Fix}(g) \). Сумма по всем \( g \) даёт общее количество таких пар.

1. Второй способ: для каждого элемента множества \( x \) подсчитывается количество элементов группы \( g \), которые его оставляют неподвижным, то есть размер стабилизатора \( \text{Stab}(x) \). Сумма по всем \( x \) даёт то же самое число.

Известно, что для каждого \( x \) размер орбиты \( |\text{Orb}(x)| \) равен \( |G| / |\text{Stab}(x)| \). Тогда сумма стабилизаторов по всем элементам одной орбиты равна \( |G| \). Следовательно, общая сумма по всем \( x \in X \) равна \( |G| \cdot |X/G| \). Приравнивая два подсчёта, получаем:

\[ \sum_{g \in G} \text{Fix}(g) = |G| \cdot |X/G| \]

Отсюда следует формула леммы.

Применение в комбинаторике

Лемма Бернсайда широко применяется в комбинаторике для подсчёта количества различных объектов с учётом симметрий. Рассмотрим классический пример — подсчёт количества различных ожерелий из \( n \) бусин, каждая из которых может быть одного из \( k \) цветов. Два ожерелья считаются одинаковыми, если одно можно получить из другого поворотом (циклической перестановкой). В этом случае группа \( G \) — это циклическая группа порядка \( n \), действующая на множестве всех раскрасок \( X \) (всего \( k^n \) раскрасок). Для каждого поворота на \( d \) позиций (где \( d = 0, 1, \dots, n-1 \)) неподвижными будут те раскраски, которые инвариантны относительно этого поворота. Число таких раскрасок равно \( k^{\text{НОД}(n, d)} \). По лемме Бернсайда число различных ожерелий:

\[ \frac{1}{n} \sum_{d=0}^{n-1} k^{\text{НОД}(n, d)} \]

Аналогично лемма применяется для подсчёта числа графов, химических соединений, раскрасок граней куба и других задач, где важна симметрия.

Пример: раскраска граней куба

Пусть требуется подсчитать количество различных раскрасок граней куба в \( k \) цветов, причём два куба считаются одинаковыми, если один можно повернуть в пространстве так, чтобы он совпал с другим. Группа вращений куба (группа октаэдра) имеет порядок 24. Для каждого типа вращения (например, поворот вокруг оси, проходящей через центры противоположных граней, на 90°, 180° или 270°) подсчитывается количество неподвижных раскрасок. По лемме Бернсайда число различных раскрасок равно:

\[ \frac{1}{24} \left( k^6 + 3k^4 + 12k^3 + 8k^2 \right) \]

Связь с теоремой Пойа

Лемма Бернсайда является частным случаем более общей теоремы Пойа о перечислении (теоремы Пойа — Редфилда), которая, помимо подсчёта числа орбит, позволяет учитывать веса объектов и получать производящие функции. Теорема Пойа обобщает лемму на случай, когда каждому элементу множества \( X \) приписывается некоторый вес, и требуется подсчитать сумму весов по орбитам.

Критика и ограничения

Лемма Бернсайда является мощным инструментом, но её применение требует знания структуры группы и умения вычислять количество неподвижных точек для каждого элемента. В некоторых случаях, особенно при больших группах, это может быть трудоёмко. Кроме того, лемма не даёт явного перечисления орбит, а только их количество. Для получения самих орбит или их описания требуются дополнительные методы, например, построение представителей.

Обобщения

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

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

• Лемма Бернсайда часто используется в задачах олимпиадной математики и программирования, особенно при подсчёте комбинаторных объектов с симметриями.
• В химии лемма применяется для подсчёта числа изомеров органических соединений, например, для подсчёта числа различных структур бензольных колец с заместителями.
• В физике лемма используется в теории кристаллов для подсчёта числа различных типов узлов в кристаллической решётке с учётом симметрии.

Источники

• Бернсайд У. Теория групп конечного порядка. — М.: Наука, 1967.
• Кострикин А. И. Введение в алгебру. Часть III. Основные структуры. — М.: Физматлит, 2001.
• Холл М. Теория групп. — М.: Издательство иностранной литературы, 1962.
• Пойа Г., Рид Р. Комбинаторная перечислительная теория. — М.: Мир, 1972.