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

5.18.144.53: Перенаправление на Лемма Бёрнсайда и Теорема Пойа

2016-01-07T20:11:52Z

Перенаправление на Лемма Бёрнсайда и Теорема Пойа

RomanSatyukov в 10:57, 19 сентября 2010

2010-09-19T10:57:08Z

192.168.0.2 в 09:07, 19 сентября 2010

2010-09-19T09:07:37Z

192.168.0.2 в 09:07, 19 сентября 2010

2010-09-19T09:07:01Z

192.168.0.2 в 09:00, 19 сентября 2010

2010-09-19T09:00:50Z

Внесённые изменения

192.168.0.2 в 05:42, 19 сентября 2010

2010-09-19T05:42:36Z

RomanSatyukov в 23:23, 17 сентября 2010

2010-09-17T23:23:21Z

192.168.0.2 в 18:58, 10 августа 2010

2010-08-10T18:58:04Z

192.168.0.2: /* решение: */

2010-08-10T16:05:17Z

‎решение:

192.168.0.2 в 16:02, 10 августа 2010

2010-08-10T16:02:20Z

← Предыдущая		Версия 20:11, 7 января 2016
Строка 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>~~
−
−	~~[[Категория:Теория групп~~]]

@@ Строка 1: / Строка 1: @@
 == Постановка задачи ==
 Пусть [[группа]] <tex>G</tex> [[Действие группы на множестве|действует]] на множестве <tex>X</tex>. По свойствам орбит множество <tex>X</tex> разбивается на непересекающиеся орбиты. Требуется найти их количество.
@@ Строка 18: / Строка 14: @@
 <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>.
+Фиксируем точку 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>.
 }}
@@ Строка 27: / Строка 23: @@
 }}
-=== Задача о числе ожерелий ===
+=== Применение леммы Бернсайда на примере задачи о числе ожерелий ===
 Пусть есть сколь угодно много бусинок <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>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>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*m^{\frac{n+1}{2}}</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>.
 ''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}\frac{1+m}{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>.
@@ Строка 56: / Строка 52: @@
 Для числа орбит имеем: <tex>N=\frac{S+S_{ref}}{2n}</tex>.
-Для нечетного <tex>n</tex>: <tex>N=\frac{1}{2n}\sum_{q|n}\phi(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+\frac{m^{\frac{n+1}{2}}}{2}</tex>
-Для четного <tex>n</tex>: <tex>N=\frac{1}{2n}\sum_{q|n}\phi(n/q)m^q+m^{n/2}\frac{1+m}{4}</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>
 [[Категория:Теория групп]]

@@ Строка 21: / Строка 21: @@
 }}
-Преобразуем выражение для числа орбит, полученное из леммы Бернсайда. <br>
+Преобразуем выражение для числа орбит, указанное в формулировке леммы Бернсайда. <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>

@@ Строка 11: / Строка 11: @@
 |statement=
 Число [[орбита|орбит]] в группе <tex>G</tex> равно <tex>\frac { \sum_{g \in G} |Fix(g)| } { |G| } </tex>
-}}
+|proof=
 {{Утверждение
 |id=s1
@@ Строка 24: / Строка 24: @@
 <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.
+Последнее преобразование выполнено на основании утверждения 1. Выполняя теперь в последней сумме суммирование сначала внутри каждой орбиты, а затем по всем орбитам(помня о том, что множество <tex>X</tex> распадается на непересекающиеся орбиты), в сумме внутри орбиты получаем мощность орбиты, которая сокращается с <tex>\frac {1} { |Orb(x)| }</tex> и остается только сумма <tex>\sum 1</tex>, взятая по всем орбитам, и сводящаяся к числу орбит.
 === Задача о числе ожерелий ===

@@ Строка 16: / Строка 16: @@
 |about=1
 |statement=
-<tex> |Orb(x)| = \frac { |G| } { |St(x) } </tex>
+<tex> |Orb(x)| = \frac { |G| } { |St(x)| } </tex>
 }}

@@ Строка 2: / Строка 2: @@
 |item1=(исправлено)Надо решить задачу о числе ожерелий!
 }}
 {{Лемма
@@ Строка 7: / Строка 10: @@
 |about=Бернсайда
 |statement=
-Число орбит <tex> = \frac { \sum_{g \in G} |Fix(g)| } { |G| } </tex>
+Число [[орбита|орбит]] в группе <tex>G</tex> равно <tex>\frac { \sum_{g \in G} |Fix(g)| } { |G| } </tex>
 }}
 {{Утверждение

@@ Строка 1: / Строка 1: @@
 {{Требует доработки
-|item1=Надо решить задачу о числе ожерелий!
+|item1=(исправлено)Надо решить задачу о числе ожерелий!
 }}
@@ Строка 38: / Строка 38: @@
 рассмотрим поворот <tex> a_i</tex> на угол <tex>\frac {2i\pi} {k}</tex>, где <tex> i \in [1..k]</tex>. Количество его неподвижных точек равно количеству неподвижных точек <tex>a_1</tex>, если <tex> i</tex> взаимно просто с <tex>k</tex>. Количество взаимно простых с <tex>k</tex>(не превосходящих <tex>k</tex>) — является функцией Эйлера <tex>\phi(k)</tex>. Пусть <tex>S</tex> — сумма по всем поворотам, тогда <tex>S= \sum_{k} \phi(k) \cdot P(\frac {n_1} { k }, \frac {n_2} { k }, ..., \frac {n_m} { k })</tex>, где k пробегает множество общих делителей <tex>n_1, n_2, ..., n_m</tex>.
 '''рассмотрим симметрии относительно осей:'''
@@ Строка 52: / Строка 53: @@
 ''a)Пусть'' <tex>n_1, n_2</tex> ''— не четные'', <tex>n_i (i \in [3..m])</tex> — четные, <tex>d</tex> — симметрия относительно некой оси, проходящей через противоположные вершины. Тогда неподвижными точками для <tex>d'</tex> будут ожерелья, симметричные относительно оси, проходящей через вершины <tex>n_1</tex> и <tex>n_2</tex> сортов. По одну сторону находятся от оси находятся <tex>\frac {n-2} { 2 }</tex> бусин, где <tex>\frac {n_1-1} { 2 },</tex> бусин <tex>n_1</tex> цвета, <tex>\frac {n_2-1} { 2 },</tex> бусин <tex>n_2</tex> цвета <tex>\frac {n_i} { 2 },</tex> бусин <tex>[3..m]</tex> цвета. Бусины <tex>n_1</tex> и <tex>n_2</tex> цвета можно поменять местами <tex>\Rightarrow</tex> количество неподвижных точек <tex>t(d')=2P(\frac {n_1-1} { 2 }, \frac {n_2-1} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий <tex>\frac {n} {2}  \Rightarrow S'=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.
-''б)Пусть все'' <tex>n_i</tex> — ''четные''.
+''б)Пусть все'' <tex>n_i</tex> — ''четные''. Если <tex>d</tex> — симметрия относительно оси проходящей через 2 вершины, то неподвижными точками для <tex>d'</tex> будут симметричные ожерелья, у которых <tex>2</tex> бусины <tex>n_i (i \in [1..m])</tex> цвета расположены на данной оси. Их количество <tex>t(d')=P(\frac {n_1-2} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })+P(\frac {n_1} { 2 }, \frac {n_2-2} { 2 }, \frac {n_3} { 2 }, ..., \frac {n_m} { 2 })</tex><tex>+ ...+</tex><tex>P(\frac {n_1} { 2 }, ..., \frac {n_{m-1}} { 2 }, ..., \frac {n_m-2} { 2 })=P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий <tex> \frac {m} {2}</tex>. Если <tex>d</tex> — симметрия относительно оси, проходящей между бусинами, то количество неподвижных точек равно <tex>t(d')=P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий также <tex> \frac {m} {2}</tex>. Поэтому <tex>S'=m \cdot P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.
 [[Категория:Теория групп]]

@@ Строка 50: / Строка 50: @@
 <tex>n</tex> — четно. Ожерелья, симметричные относительно оси проходящей между бусинами, существуют только если все <tex>n_i (i \in [1..m])</tex> четные. Если ось проходит через <tex>2</tex> бусины, то симметричные ожерелья существуют только если все <tex>n_i (i \in [1..m])</tex> четные '''или''' если только <tex>2</tex> из <tex>n_i (i \in [1..m])</tex> не четные. Рассмотрим оба случая:
-Пусть <tex>n_1, n_2</tex> — не четные, <tex>n_i (i \in [3..m])</tex> — четные, <tex>d</tex> — симметрия относительно некой оси, проходящей через противоположные вершины. Тогда неподвижными точками для <tex>d'</tex> будут ожерелья, симметричные относительно оси, проходящей через вершины <tex>n_1</tex> и <tex>n_2</tex> сортов. По одну сторону находятся от оси находятся <tex>\frac {n-2} { 2 }</tex> бусин, где <tex>\frac {n_1-1} { 2 },</tex> бусин <tex>n_1</tex> цвета, <tex>\frac {n_2-1} { 2 },</tex> бусин <tex>n_2</tex> цвета <tex>\frac {n_i} { 2 },</tex> бусин <tex>[3..m]</tex> цвета. Бусины <tex>n_1</tex> и <tex>n_2</tex> цвета можно поменять местами <tex>\Rightarrow</tex> количество неподвижных точек <tex>t(d')=2P(\frac {n_1-1} { 2 }, \frac {n_2-1} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий <tex>\frac {n} {2}  \Rightarrow S'=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.
+''a)Пусть'' <tex>n_1, n_2</tex> ''— не четные'', <tex>n_i (i \in [3..m])</tex> — четные, <tex>d</tex> — симметрия относительно некой оси, проходящей через противоположные вершины. Тогда неподвижными точками для <tex>d'</tex> будут ожерелья, симметричные относительно оси, проходящей через вершины <tex>n_1</tex> и <tex>n_2</tex> сортов. По одну сторону находятся от оси находятся <tex>\frac {n-2} { 2 }</tex> бусин, где <tex>\frac {n_1-1} { 2 },</tex> бусин <tex>n_1</tex> цвета, <tex>\frac {n_2-1} { 2 },</tex> бусин <tex>n_2</tex> цвета <tex>\frac {n_i} { 2 },</tex> бусин <tex>[3..m]</tex> цвета. Бусины <tex>n_1</tex> и <tex>n_2</tex> цвета можно поменять местами <tex>\Rightarrow</tex> количество неподвижных точек <tex>t(d')=2P(\frac {n_1-1} { 2 }, \frac {n_2-1} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий <tex>\frac {n} {2}  \Rightarrow S'=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.
-Пусть все <tex>n_i</tex> — четные.
+''б)Пусть все'' <tex>n_i</tex> — ''четные''.
 [[Категория:Теория групп]]