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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перенаправление на Лемма Бёрнсайда и Теорема Пойа)
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
{{Требует доработки
+
#перенаправление [[Лемма Бёрнсайда и Теорема Пойа]]
|item1=Надо решить задачу о числе ожерелий!
 
}}
 
 
 
{{Лемма
 
|id=l1
 
|about=Бернсайда
 
|statement=
 
Число орбит <tex> = \frac { \sum_{g \in G} |Fix(g)| } { |G| } </tex>
 
}}
 
{{Утверждение
 
|id=s1
 
|about=1
 
|statement=
 
<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>n</tex> бусинок <tex>m</tex> разных сортов, <tex>n_i</tex> назовем количество бусинок <tex>i</tex>ого цвета<tex>(i \in [1;m])</tex>. Найти число ожерелий которые можно составить из этих бусинок. Ожерелья полученные поворотом друг из друга поворотом или отражением считаются одним ожерельем.
 
 
 
===='''решение:'''====
 
 
 
Эта задача равносильна следующей задаче: сколькими различными способами можно раскрасить вершины правильного <tex>n</tex>угольника вершины которого окрашены в цветов, а количество вершин каждого цвета равно <tex>n_i</tex>. Две расскраски считаются разными, если из одной нельзя получить другую с помощью симметрии или вращения.
 
 
 
Пусть <tex>M</tex> — множество всех возможных окрасок <tex>n</tex>угольника, <tex>D</tex> — группа симметрий <tex>n</tex>угольника, состоящая из <tex>2n</tex> преобразований. Группа <tex>G</tex> определяет группу перестановок на множестве <tex>M</tex>. Пусть <tex> g \in D</tex> — некое преобразование симметрии <tex> \Rightarrow </tex> для любого многоугольник <tex>x \in M</tex> можно сопоставить многоугольник получаемый из него симметрией <tex>g</tex>. Назовем сопоставление этой перестановки <tex>g'</tex>. Группу всех таких перестановок из <tex>D</tex> назовем <tex>D'</tex>.
 
 
 
Два многоугольника будут считаться разными, если из одного невозможно получить другой какой-либо перестановкой <tex>d' \in D'</tex> (они содержаться на разных орбитах группы <tex>D'</tex> действующей на множестве <tex>M</tex>). Поэтому для получения количества различных раскрасок вершин  <tex>n</tex>угольника достаточно найти количество орбит группы <tex>D'</tex> на множестве <tex>M</tex>. По лемме Бернсайда, для этого нужно посчитать число неподвижных точек каждой перестановки <tex> d' \in D'</tex>.
 
 
 
 
 
'''Рассмотрим повороты:'''
 
 
 
пусть <tex>k</tex> — общий делитель <tex>n_i</tex>ых<tex>(i \in [1..m]) \Rightarrow</tex> поворот <tex>a_1</tex> на угол <tex>\frac { 2\pi } { k }</tex> оставит неподвижными ожерелья из <tex>k</tex> одинаковых кусков длинны <tex>\frac {n} {k}</tex>. Каждый кусок состоит из <tex>\frac {n_i} { k } </tex> бусен <tex>i</tex>ого цвета, поэтому число неподвижных точек для поворота будет равно количеству способов расставить бусины на <tex>\frac {n} {k}</tex> местах.
 
 
 
рассмотрим поворот <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>.
 
 
 
 
 
'''рассмотрим симметрии относительно осей:'''
 
 
 
''1 случай:''
 
 
 
<tex>n</tex> — нечетно.
 
 
 
''2 случай:''
 
 
 
<tex>n</tex> — четно.
 
 
 
 
 
[[Категория:Теория групп]]
 

Текущая версия на 23:11, 7 января 2016