Лемма Бернсайда, задача о числе ожерелий

Постановка задачи

Пусть группа [math]G[/math] действует на множестве [math]X[/math]. По свойствам орбит множество [math]X[/math] разбивается на непересекающиеся орбиты. Требуется найти их количество.

Лемма (Бернсайда):

Число орбит в группе [math]G[/math] равно [math]\frac { \sum_{g \in G} |Fix(g)| } { |G| } [/math]

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

[math]\triangleright[/math]

Утверждение (1): [math] |Orb(x)| = \frac { |G| } { |St(x)| } [/math] [math]\triangleright[/math] Фиксируем точку x. Рассмотрим отображение [math]\phi:G\rightarrow X[/math], сопоставляющее элементу [math]g\in G[/math] точку [math]gx[/math]. Тогда верно следующее утверждение: [math]\phi(g_1)=\phi(g_2)[/math] тогда и только тогда, когда [math]g_1[/math] и [math]g_2[/math] лежат в одном смежном классе [math]G[/math] по [math]St(x)[/math]. Действительно, [math]g_1 x=g_2 x \Leftrightarrow {g_1}^{-1}g_2 x=x\Leftrightarrow {g_1}^{-1}g_2\in St(x)\Leftrightarrow g_2\in g_1 St(x)[/math]. Таким образом, образ каждого смежного класса — одна точка, причем разным смежным классам соответствуют разные точки. Поэтому мощность образа(который и представляет собой орбиту) равна числу смежных классов, т.е. [math]|Orb(x)|=\frac{|G|}{|St(x)|}[/math]. [math]\triangleleft[/math] Преобразуем выражение для числа орбит, указанное в формулировке леммы Бернсайда. [math]\frac { \sum_{g \in G} |Fix(g)| } { |G| } = \frac { \sum_{ g \in G } \sum_{ x \in X } \{gx = x\} } { |G| } = \frac { \sum_{ x \in X } \sum_{ g \in G } \{gx = x\} } { |G| } = \frac { \sum_{ x \in X } |St(x)| } { |G| } = \sum_{ x \in X } \frac {1} { |Orb(x)| } [/math] Последнее преобразование выполнено на основании утверждения 1. Выполняя теперь в последней сумме суммирование сначала внутри каждой орбиты, а затем по всем орбитам(помня о том, что множество [math]X[/math] распадается на непересекающиеся орбиты), в сумме внутри орбиты получаем мощность орбиты, которая сокращается с [math]\frac {1} { |Orb(x)| }[/math] и остается только сумма [math]\sum 1[/math], взятая по всем орбитам, и сводящаяся к числу орбит.

[math]\triangleleft[/math]

Применение леммы Бернсайда на примере задачи о числе ожерелий

Пусть есть сколь угодно много бусинок [math]m[/math] разных сортов. Необходимо найти число различных ожерелий длинны [math]n[/math], которые можно составить из этих бусинок. Ожерелья, полученные друг из друга поворотом или отражением, считаются одинаковыми.

Решение задачи

Эта задача равносильна следующей задаче: сколькими различными способами можно раскрасить вершины правильного [math]n[/math]-угольника в [math]m[/math] цветов. Две раскраски считаются разными, если из одной нельзя получить другую с помощью симметрии или вращения.

Пусть [math]M[/math] — множество всех возможных окрасок [math]n[/math]угольника, [math]D[/math] — группа симметрий [math]n[/math]угольника, состоящая из [math]2n[/math] преобразований. Зададим действие D на M — раскраска [math]dm\,(d\in D,\,m\in M)[/math] — это раскраска, получающаяся из [math]m[/math] при преобразовании раскрашенного по [math]m[/math] [math]n[/math]-угольника симметрией [math]d[/math]. Тогда две раскраски будут считаться одинаковыми, если принадлежат одной орбите(тогда одна получается из другой некоторым преобразованием симметрии). Таким образом задача сводится к задаче об определении числа орбит в [math]M[/math], которую можно решить, воспользовавшись леммой Бернсайда. Определим для этого число неподвижных точек для каждого элемента [math]D[/math].

Неподвижные точки поворотов

Рассмотрим поворот [math]d[/math] на угол [math]k,\,k\in [0..n-1][/math](поворотом на угол [math]k[/math] мы называем поворот на "реальный" угол [math]\frac{2\pi k}{n}[/math]). Мы хотим найти число раскрасок, инвариантных относительно этого поворота. Такая раскраска должна быть инвариантна относительно и всей подгруппы [math]G=\lbrace e,d,d^2,...,d^p\rbrace[/math]([math]p[/math] — порядок d). Это означает, что орбита вершины под действием [math]G[/math] должна быть окрашена в один цвет. Очевидно, что это требование является не только необходимым, но и достаточным. То есть, инвариантных раскрасок столько же, сколько и раскрасок орбит. Пользуясь леммой Бернсайда, можно определить число орбит: неподвижные точки есть только у тождественного поворота, при этом их [math]n[/math] штук. Тогда число орбит равно [math]n/p[/math]. Осталось найти число [math]p[/math] — минимальное число, при котором [math]kp[/math] делится на [math]n[/math]. В этом случае [math]kp[/math] будет наименьшим числом, делящимся и на [math]n[/math] и на [math]k[/math], поэтому [math]kp=\operatorname{lcm}(n,k)\Rightarrow p=\frac{\operatorname{lcm}(n,k)}{k}=\frac{n}{\operatorname{gcd}(n,k)}[/math]. Тогда число орбит равняется [math]n/p=\operatorname{gcd}(n,k)[/math] и число их раскрасок [math]N_k=m^{\operatorname{gcd}(n,k)}[/math]. Сумма же инвариантных раскрасок для всех поворотов: [math]S=\sum_{k=0}^{n-1}N_k=\sum_{k=0}^{n-1}m^{\operatorname{gcd}(n,k)}[/math]. В последней сумме [math]\phi(n)[/math] слагаемых, для которых [math]\operatorname{gcd}(n,k)=1[/math]. Если же [math]\operatorname{gcd}(n,k)=q[/math], то [math]\operatorname{gcd}(n/q,k/q)=1[/math]. Чтобы определить количество таких k, меньших n, нужно перебрать числа вида [math]k=lq,\,0\leq l\leq n/q[/math] и проверять их на условие [math]1=\operatorname{gcd}(n/q,k/q)=\operatorname{gcd}(n/q,l)[/math]. Таких чисел, очевидно, [math]\phi(n/q)[/math](по определению [math]\phi(n)[/math]). Поэтому сумму можно заменить: [math]S=\sum_{k=0}^{n-1}m^{\operatorname{gcd}(n,k)}=\sum_{q|n}\phi(n/q)m^q[/math].

Неподвижные точки отражений

1 случай:

[math]n[/math] — нечетно. Тогда оси всех отражений проходят через вершину и для инвариантности мы должны выбрать [math](n-1)/2+1[/math] вершин и раскрасить, а остальные дополнить по симметрии. Для каждого отражения получаем [math]m^{\frac{n+1}{2}}[/math]. Сумма же по всем отражениям, которых [math]n[/math] штук, [math]S_{ref}=n \cdot m^{\frac{n+1}{2}}[/math].

2 случай:

[math]n[/math] — четно. Тогда есть [math]m/2[/math] осей, проходящих через стороны [math]n[/math]-угольника, для каждой [math]m^{n/2}[/math] инвариантных раскрасок(половину точек раскрашиваем по желанию, половину дополняем по инвариантности). Для оставшихся [math]m/2[/math] осей, проходящих через 2 точки, имеем инвариантных раскрасок(свободно выбирается [math]n/2+1[/math] цвет) [math]m^{n/2+1}[/math]. Итоговая сумма по всем отражениям: [math]S_{ref}=nm^{n/2}\cdot\frac{1+m}{2}[/math].

Итак:

Для числа орбит имеем: [math]N=\frac{S+S_{ref}}{2n}[/math].

Для нечетного [math]n[/math]: [math]N=\frac{1}{2n}\sum_{q|n}\phi(\frac{n}{q})m^q+\frac{m^{\frac{n+1}{2}}}{2}[/math]

Для четного [math]n[/math]: [math]N=\frac{1}{2n}\sum_{q|n}\phi(\frac{n}{q})m^q+m^{n/2} \cdot \frac{1+m}{4}[/math]