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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 30: Строка 30:
 
Пусть <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>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>.
  
 +
Рассмотрим повороты:
  
  
 
[[Категория:Теория групп]]
 
[[Категория:Теория групп]]

Версия 18:13, 8 июля 2010

Эта статья требует доработки!
  1. Надо решить задачу о числе ожерелий!

Если Вы исправили некоторые из указанных выше замечаний, просьба дописать в начало соответствующего пункта (Исправлено).

Лемма (Бернсайда):
Число орбит [math] = \frac { \sum_{g \in G} |Fix(g)| } { |G| } [/math]
Утверждение (1):
[math] |Orb(x)| = \frac { |G| } { |St(x) } [/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]n[/math] бусинок [math]m[/math] разных сортов, [math]n_i[/math] назовем количество бусинок [math]i[/math]ого цвета[math](i \in [1;m])[/math]. Найти число ожерелий которые можно составить из этих бусинок. Ожерелья полученные поворотом друг из друга поворотом или отражением считаются одним ожерельем.

решение:

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

Пусть [math]M[/math] — множество всех возможных окрасок [math]n[/math]угольника, [math]D[/math] — группа симметрий [math]n[/math]угольника, состоящая из [math]2n[/math] преобразований. Группа [math]G[/math] определяет группу перестановок на множестве [math]M[/math]. Пусть [math] g \in D[/math] — некое преобразование симметрии [math] \Rightarrow [/math] для любого многоугольник [math]x \in M[/math] можно сопоставить многоугольник получаемый из него симметрией [math]g[/math]. Назовем сопоставление этой перестановки [math]g'[/math]. Группу всех таких перестановок из [math]D[/math] назовем [math]D'[/math].

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

Рассмотрим повороты: