Изменения

Фиксируем точку x. Рассмотрим отображение <tex>\phi:G\rightarrow X</tex>, сопоставляющее элементу <tex>g\in G</tex> точку <tex>gx</tex>. Тогда верно следующее утверждение: <tex>\phi(g_1)=\phi(g_2)</tex> тогда и только тогда, когда <tex>g_1</tex> и <tex>g_2</tex> лежат в одном смежном классе <tex>G</tex> по <tex>St(x)</tex>. Действительно, <tex>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)</tex>. Таким образом, образ каждого смежного класса - — одна точка, причем разным смежным классам соответствуют разные точки. Поэтому мощность образа(который и представляет собой орбиту) равна числу смежных классов, т.е. <tex>|Orb(x)|=\frac{|G|}{|St(x)|}</tex>.

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

===='''решение:'''Решение задачи ====

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

'''Рассмотрим повороты:Неподвижные точки поворотов'''

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

'''рассмотрим симметрии относительно осей:Неподвижные точки отражений'''

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

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

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

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