Лемма Бернсайда: число орбит через неподвижные точки

Лемма Бернсайда - самый короткий рецепт «как считать с точностью до симметрии». Сколько есть различных раскрасок граней куба в три цвета, если повороты куба между собой не различаются? Сколько ожерелий длины восемь из бусин двух цветов, если ожерелье можно поворачивать и переворачивать? Прямое перечисление сразу упирается в комбинаторный взрыв, а лемма Бернсайда сводит всё к подсчёту неподвижных точек у каждого элемента группы - обычно конечной и обозримой. Историческое имя сложилось не вполне справедливо: Огюстен Коши пользовался формулой ещё в 1845 году, Фердинанд Фробениус сформулировал её в общем виде в 1887-м, а Уильям Бернсайд лишь привёл её в своём учебнике 1897 года без претензии на авторство. В англоязычной литературе её и зовут «lemma that is not Burnside's» или формулой Коши-Фробениуса.

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

Пусть конечная группа $G$ действует на конечном множестве $X$. Это значит: задано отображение $G \times X \to X$, $(g, x) \mapsto g \cdot x$, согласованное с операцией в группе ($e \cdot x = x$, $(gh) \cdot x = g \cdot (h \cdot x)$).

Орбита элемента $x \in X$ - это множество $G \cdot x = \{g \cdot x : g \in G\}$. Орбиты разбивают $X$ на непересекающиеся подмножества; их число обозначают $|X/G|$ и читают как «количество орбит» или «количество классов эквивалентности относительно действия $G$».

Стабилизатор элемента $x$ - подгруппа $G_x = \{g \in G : g \cdot x = x\}$. Двойственно: множество неподвижных точек элемента $g$ - это $X^g = \{x \in X : g \cdot x = x\}$.

Лемма Бернсайда. Для конечной группы $G$, действующей на конечном множестве $X$:

$$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|.$$

Словами: число орбит равно среднему числу неподвижных точек по группе. Никакой явной структуры орбит знать не нужно - только сколько элементов каждый $g \in G$ оставляет на месте.

Хочешь применить лемму Бернсайда к конкретной комбинаторной задаче - выбери объект и число цветов, и мы соберём подсчёт неподвижных точек по каждому элементу группы симметрий и поделим на её порядок.

Доказательство двойным счётом

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

Рассмотрим множество пар $S = \{(g, x) \in G \times X : g \cdot x = x\}$ - пары «элемент группы и точка, которую он не двигает».

Считаем $|S|$ по первой координате:

$$|S| = \sum_{g \in G} |X^g|.$$

Считаем по второй координате:

$$|S| = \sum_{x \in X} |G_x|.$$

По теореме об орбите-стабилизаторе для каждого $x \in X$ выполнено $|G \cdot x| \cdot |G_x| = |G|$ (это прямое следствие теоремы Лагранжа для групп), откуда $|G_x| = |G|/|G \cdot x|$. Сумма по $x$ группируется по орбитам $O_1, \dots, O_k$:

$$\sum_{x \in X} |G_x| = \sum_{i=1}^{k} \sum_{x \in O_i} \frac{|G|}{|O_i|} = \sum_{i=1}^{k} |O_i| \cdot \frac{|G|}{|O_i|} = k \cdot |G|.$$

Здесь $k = |X/G|$. Приравниваем два выражения для $|S|$ и делим на $|G|$ - получаем формулу леммы. Доказательство закончено: ни одного слова про конкретную структуру действия, всё на двойном счёте и орбите-стабилизаторе.

Раскраски граней куба в три цвета

Классическая задача: сколько существует различных раскрасок шести граней куба в три цвета, если две раскраски считаются одинаковыми, если переходят друг в друга вращением куба?

Без учёта симметрий ответ - $3^6 = 729$. С учётом - нужно поделить на группу вращений куба, но не «просто на 24» (это даёт нецелое: $729/24 = 30{,}375$), а правильно - через лемму Бернсайда.

Группа вращений куба $G$ изоморфна симметрической группе $S_4$ (действует перестановками четырёх пространственных диагоналей куба), её порядок $|G| = 24$. Разобьём её на классы сопряжённости и для каждого посчитаем число неподвижных раскрасок.

Сумма $|X^g|$:

$$1 \cdot 729 + 6 \cdot 27 + 3 \cdot 81 + 8 \cdot 9 + 6 \cdot 27 = 729 + 162 + 243 + 72 + 162 = 1368.$$

По лемме Бернсайда:

$$|X/G| = \frac{1368}{24} = 57.$$

Различных раскрасок граней куба в три цвета - 57. Прямой перебор по 729 раскраскам и слиянию орбит в принципе возможен, но требует на порядок больше работы; лемма даёт ответ через подсчёт пяти типов вращений.

Применение к ожерельям и бусинам

Та же логика работает для одномерных объектов с круговой или зеркальной симметрией.

Ожерелье из $n$ бусин на нити - без поворотов и переворотов, но с симметрией «развернуть нить наоборот». Группа - $\mathbb{Z}/2\mathbb{Z}$: тождество (одна неподвижная раскраска для каждой из $k^n$ возможных) и переворот (раскраска неподвижна, если симметрична относительно центра).

Бусины по кругу - группа диэдральная $D_n$ порядка $2n$: $n$ поворотов и $n$ отражений. Число неподвижных раскрасок при повороте на угол $2\pi d/n$ равно $k^{\gcd(n, d)}$ - раскраска должна быть периодической с периодом $\gcd(n, d)$. Сумма по поворотам $\sum_{d=0}^{n-1} k^{\gcd(n,d)}$ переписывается через функцию Эйлера: $\sum_{d | n} \varphi(d) \cdot k^{n/d}$. Это и есть формула Коши для числа круговых ожерелий до поворота. Добавление отражений даёт классический ответ через диэдральную группу.

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

Лемма Бернсайда считает только количество орбит, без учёта весов: все цвета входят на равных. Теорема Пойа (1937) - её прямое обобщение. Каждой раскраске сопоставляется моном, скажем $r^a b^c c^z$ по числу красных, синих и зелёных элементов, и теорема Пойа выписывает производящую функцию числа орбит через цикловой индекс группы:

$$Z(G; x_1, \dots, x_n) = \frac{1}{|G|} \sum_{g \in G} x_1^{c_1(g)} x_2^{c_2(g)} \dots x_n^{c_n(g)},$$

где $c_i(g)$ - число циклов длины $i$ в подстановке $g$ на $X$. Подставляя в $Z$ суммы $f(t^i) = \sum_k r_k^i$ по «инвентарной функции» цветов, получаем многочлен, коэффициенты которого - числа орбит с фиксированной палитрой.

Подставив $x_i = k$ для всех $i$ (то есть «$k$ равноправных цветов»), теорема Пойа сворачивается обратно в лемму Бернсайда: $|X^g| = k^{c(g)}$, где $c(g)$ - полное число циклов, а $Z(G; k, k, \dots) = (1/|G|)\sum_g k^{c(g)} = |X/G|$. Лемма Бернсайда - это «теорема Пойа без раскрашивающего веса».

Изомеры в химии

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

Конкретный пример: производные бензола $\mathrm{C_6H_{6-k}X_k}$, где $k$ позиций из шести заняты заместителем $X$, остальные - водородом. Группа симметрии шестичленного кольца - $D_6$ порядка 12. Для $k = 2$ (дизамещённый бензол) лемма Бернсайда даёт число изомеров:

$$\frac{1}{12}\left(\binom{6}{2} \cdot 1 + 0 \cdot 2 + 0 \cdot 2 + \dots\right)$$

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

Перечисление графов

Сколько существует неэквивалентных простых графов на $n$ помеченных вершинах? Если различать вершины - $2^{\binom{n}{2}}$ (для каждого ребра отдельный бит). Если не различать - нужно факторизовать по симметрической группе $S_n$, действующей перестановками вершин.

Применяя лемму Бернсайда к множеству $X = \{\text{подмножества рёбер}\}$ под действием $S_n$ на парах вершин, получаем формулу:

$$g(n) = \frac{1}{n!} \sum_{\sigma \in S_n} 2^{c(\sigma)},$$

где $c(\sigma)$ - число циклов перестановки $\sigma$ на парах вершин (вычисляется через структуру циклов $\sigma$ на вершинах). Группируя по типам циклов, формула даёт OEIS-последовательность A000088: 1, 2, 4, 11, 34, 156, 1044, … Этот же приём считает количество неизоморфных деревьев, турниров, гиперграфов, простых функциональных графов - везде, где есть группа симметрий вершин.

Частые ошибки

• Путают $|X^g|$ и $|G_x|$. $X^g$ - точки, неподвижные под действием фиксированного $g$ (бегает $x$). $G_x$ - элементы группы, оставляющие на месте фиксированную точку $x$ (бегает $g$). В лемме Бернсайда суммируется именно $|X^g|$ - индекс снизу обозначает группу, а $X^g$ читается «множество $X$, инвариантное относительно $g$».
• Применяют лемму без указания группы. «Сколько раскрасок куба с точностью до симметрии» - неоднозначный вопрос. Если речь о вращениях - группа порядка 24. Если о вращениях + отражениях (полная группа симметрии куба) - порядок 48, и ответ другой. Перед подсчётом надо явно зафиксировать $G$ и его действие.
• Забывают тождественный элемент. В сумме $\sum_g |X^g|$ член $g = e$ даёт $|X^e| = |X|$ - все точки. Иногда об этом забывают и считают только нетривиальные повороты, занижая ответ.
• Считают $|X^g|$ как порядок группы циклов, а не степень. Для подстановки с $c$ циклами и палитры из $k$ цветов число неподвижных раскрасок - именно $k^c$, не $kc$ и не $c!$. Внутри каждого цикла все элементы должны быть одного цвета, цвет выбирается независимо для каждого цикла.
• Применяют формулу к бесконечной группе. Классическая лемма Бернсайда требует конечной группы, иначе $|G|$ не определено. Для компактных топологических групп есть обобщение через интеграл Хаара, но это уже другая теорема.

FAQ

Чем лемма Бернсайда отличается от формулы орбит-стабилизаторов? Формула орбит-стабилизаторов $|G \cdot x| \cdot |G_x| = |G|$ - поточечное утверждение для одного $x$. Лемма Бернсайда - глобальное: считает число орбит по всему $X$. Доказательство леммы пользуется орбит-стабилизатором как леммой, но сама формула живёт в терминах суммы по группе, а не по точке.

Когда удобнее использовать теорему Пойа, а когда - лемму Бернсайда? Лемма Бернсайда - когда нужно посчитать общее число классов эквивалентности при равноправных цветах. Теорема Пойа - когда интересует распределение по конкретным цветам: сколько ожерелий с тремя красными бусинами и пятью синими, сколько молекул с одной хлор- и одной бром-группой. Формальный мостик: подставляя в цикловой индекс константы вместо переменных, теорема Пойа превращается в лемму Бернсайда.

Кто всё-таки автор формулы? Огюстен Луи Коши применил формулу около 1845 года для счёта классов сопряжённости. Фердинанд Фробениус доказал её в общем виде в 1887 году. Уильям Бернсайд воспроизвёл её в учебнике «Theory of Groups of Finite Order» (1897) со ссылкой на Фробениуса, но имя «лемма Бернсайда» закрепилось из-за частого цитирования именно его книги. В академической литературе чаще используют название «формула Коши-Фробениуса» - оно историчнее.

Коротко

Лемма Бернсайда: для конечной группы $G$, действующей на конечном множестве $X$, число орбит равно $|X/G| = (1/|G|)\sum_{g \in G} |X^g|$, где $X^g$ - точки, неподвижные под действием $g$. Доказывается двойным счётом пар $(g, x)$ с $g \cdot x = x$ через теорему об орбите-стабилизаторе. Стандартные применения - раскраски куба и других правильных многогранников с учётом вращений (57 раскрасок граней куба в 3 цвета), бусины на круге и нити, перечисление изомеров органических соединений и неизоморфных графов на $n$ вершинах. Обобщение с весовыми инвентарями - теорема Пойа; лемма Бернсайда получается из неё подстановкой равноправных цветов.