|
|
| Строка 1: |
Строка 1: |
| − | == Постановка задачи ==
| + | #перенаправление [[Лемма Бёрнсайда и Теорема Пойа]] |
| − | Пусть [[группа]] <tex>G</tex> [[Действие группы на множестве|действует]] на множестве <tex>X</tex>. По свойствам орбит множество <tex>X</tex> разбивается на непересекающиеся орбиты. Требуется найти их количество.
| |
| − | | |
| − | {{Лемма
| |
| − | |id=l1
| |
| − | |about=Бернсайда
| |
| − | |statement=
| |
| − | Число [[орбита|орбит]] в группе <tex>G</tex> равно <tex>\frac { \sum_{g \in G} |Fix(g)| } { |G| } </tex>
| |
| − | |proof=
| |
| − | {{Утверждение
| |
| − | |id=s1
| |
| − | |about=1
| |
| − | |statement=
| |
| − | <tex> |Orb(x)| = \frac { |G| } { |St(x)| } </tex>
| |
| − | |proof=
| |
| − | Фиксируем точку 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>.
| |
| − | }}
| |
| − | | |
| − | Преобразуем выражение для числа орбит, указанное в формулировке леммы Бернсайда. <br>
| |
| − | <tex>\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)| } </tex> <br>
| |
| − | Последнее преобразование выполнено на основании утверждения 1. Выполняя теперь в последней сумме суммирование сначала внутри каждой орбиты, а затем по всем орбитам(помня о том, что множество <tex>X</tex> распадается на непересекающиеся орбиты), в сумме внутри орбиты получаем мощность орбиты, которая сокращается с <tex>\frac {1} { |Orb(x)| }</tex> и остается только сумма <tex>\sum 1</tex>, взятая по всем орбитам, и сводящаяся к числу орбит.
| |
| − | }}
| |
| − | | |
| − | === Применение леммы Бернсайда на примере задачи о числе ожерелий ===
| |
| − | Пусть есть сколь угодно много бусинок <tex>m</tex> разных сортов. Необходимо найти число различных ожерелий длинны <tex>n</tex>, которые можно составить из этих бусинок. Ожерелья, полученные друг из друга поворотом или отражением, считаются одинаковыми.
| |
| − | | |
| − | ==== Решение задачи ====
| |
| − | | |
| − | Эта задача равносильна следующей задаче: сколькими различными способами можно раскрасить вершины правильного <tex>n</tex>-угольника в <tex>m</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>.
| |
| − | | |
| − | '''Неподвижные точки отражений'''
| |
| − | | |
| − | ''1 случай:''
| |
| − | | |
| − | <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>.
| |
| − | | |
| − | | |
| − | ''2 случай:''
| |
| − | | |
| − | <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=\frac{S+S_{ref}}{2n}</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>
| |
| − | | |
| − | [[Категория:Теория групп]]
| |
