Редактирование: Лемма Бёрнсайда и Теорема Пойа

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>,  
+
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' (стабилизатором, ''англ.'' '''stabilizer''') для элемента <tex>g</tex> называется такой элемент <tex>x</tex>,  
 
для которого <tex>gx=x</tex>.
 
для которого <tex>gx=x</tex>.
 
}}
 
}}
  
{{Определение
 
|definition=
 
Множество неподвижных точек элемента <tex>g</tex> называется его '''стабилизатором''' и обозначается <tex>St(g)</tex>.
 
}}
 
 
{{Определение
 
|definition=
 
Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Будем называть два элемента <tex>x</tex> и <tex>y</tex> эквивалентными, если <tex>x = gy</tex> для некоторого <tex>g \in G</tex>. Классы эквивалентности данного отношения называются '''орбитами''', множество орбит обозначается как <tex>X/G</tex>.
 
}}
 
  
 
== Лемма Бёрнсайда  ==
 
== Лемма Бёрнсайда  ==
Строка 24: Строка 15:
 
|id=lemmaBerns.  
 
|id=lemmaBerns.  
 
|author=Бернсайд, '''англ.''' Burnside's lemma
 
|author=Бернсайд, '''англ.''' Burnside's lemma
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>. <math>|X/G| = \dfrac{1} {|G|}\sum\limits_{g \in G}|St(g)|</math>.
+
|statement=Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Будем называть два элемента <tex>x</tex> и <tex>y</tex> эквивалентными, если <tex>x = gy</tex> для некоторого <tex>g \in G</tex>. Тогда число [[Отношение эквивалентности|классов эквивалентности]] равно сумме числа стабилизаторов по всем элементам группы <tex>G</tex>, делённой на размер этой группы:
 +
 
 +
<tex> |C| = </tex> <tex  dpi = "180">\frac{1} {|G|}</tex><tex>\sum\limits_{k \in G}I(k)</tex>.  Где <tex>I(k)</tex> {{---}} количество стабилизаторов для элемента <tex>k</tex>.
 
|proof=
 
|proof=
Так как <tex>St(g)</tex> {{---}} стабилизатор элемента <tex>g</tex>, то по определению <math>\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</math>.
+
Так как <tex>I(k)</tex> {{---}} сумма стабилизаторов элемента <tex>k</tex>, то по определению <tex>\sum\limits_{k \in G}I(k) = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.
  
 
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:
 
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:
<math>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</math>
+
<tex>|C|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>
 
 
Введем обозначение <tex>C=X/G</tex>.
 
  
 
Рассмотрим правую часть равенства:
 
Рассмотрим правую часть равенства:
<math>|\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum\limits_{x \in X} |G_x| = \sum\limits_{x \in X}</math><math> \dfrac{|G|}{|Gx|} = |G| \sum\limits_{x \in X}\dfrac{1}{|Gx|} </math>
+
<tex>|\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum\limits_{x \in X} |G_x| = \sum\limits_{x \in X}</tex><tex dpi = "180"> \frac{|G|}{|Gx|}</tex><tex> = |G| \sum\limits_{x \in X}</tex><tex dpi = "180">\frac{1}{|Gx|} </tex>
<math>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</math><math> \dfrac{1}{|P|}</math>
+
<tex>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex>
  
Заметим, что <math>\sum\limits_{x\in P} \dfrac{1}{|P|} = \dfrac{1}{|P|}\sum\limits_{1}^{|P|}{1} = 1.</math> Следовательно:
+
Заметим, что <tex>\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><tex> = </tex><tex dpi = "180"> \frac{1}{|P|}</tex><tex>\sum\limits_{1}^{|P|}{1} = 1.</tex> Следовательно:
  
<math>|G|\sum\limits_{P\in C}\sum\limits_{x\in P} \dfrac{1}{|P|} = |G|\sum\limits_{P\in C} 1</math>.
+
<tex>|G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><tex> = |G|\sum\limits_{P\in C} 1</tex>.
  
Очевидно, что <math>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</math> Тогда получим:
+
Очевидно, что <tex>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</tex> Тогда получим:
  
<math>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</math>
+
<tex>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</tex>
  
 
Откуда следует, что
 
Откуда следует, что
  
<math>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</math>  
+
<tex>\sum\limits_{k \in G}I(k) = |C|\cdot|G|.</tex> ч.т.д.
 
   
 
   
 
}}
 
}}
Строка 60: Строка 51:
 
|id=teorPo.  
 
|id=teorPo.  
 
|author=Пойа, '''англ.''' Pólya enumeration theorem
 
|author=Пойа, '''англ.''' Pólya enumeration theorem
|statement= <math>C = \dfrac{1}{|G|}\sum\limits_{g \in G} l^{P(g)}</math>  ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(g)</tex> {{---}} кол-во циклов в перестановке <tex>g</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.
+
|statement= <tex> C =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{k \in G} l^{P(k)}</tex>  ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(k)</tex> {{---}} кол-во циклов в перестановке <tex>k</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.
 
|proof=Для доказательства этой теоремы достаточно установить следующее равенство
 
|proof=Для доказательства этой теоремы достаточно установить следующее равенство
<math>|St(g)| = l^{P(g)}</math>
+
<tex>I(k) = l^{P(k)}</tex>
  
  
Рассмотрим некоторую перестановку <tex>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:
+
Рассмотрим некоторую перестановку <tex>k</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>k</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fk = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>k</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:
<math>|St(g)| = l^{P(g)}</math>
+
<tex>I(k) = l^{P(k)}</tex>
 
}}
 
}}
  
Строка 88: Строка 79:
 
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.
 
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.
  
Количество неподвижных точек в случае с действием <tex>e</tex> равно <tex>k^{nm}</tex>, так как ни одна раскрашенная клетка не повторилась при действии нулевого действия. Для действий <tex>\alpha</tex> и <tex>\beta</tex> количество раскрасок будет <tex>k^{\lceil \dfrac{m}{2} \rceil n}</tex> и <tex>k^{{\lceil {\dfrac{n}{2}} \rceil}m}</tex> соответственно, для их композиции количество раскрасок <tex>k^{{\lceil {\dfrac{nm}{2}} \rceil}}</tex>, так как верхняя левая четверть прямоугольника однозначно задаёт правую нижнюю, аналогично с правой верхней.
+
Количество стабилизаторов в случае с действием <tex>e</tex> равно <tex>k^{nm}</tex>, так как ни одна раскрашенная клетка не повторилась при действии нулевого действия. Для действий <tex>\alpha</tex> и <tex>\beta</tex> количество раскрасок будет <tex>k^{\lceil \frac{m}{2} \rceil n}</tex> и <tex>k^{{\lceil {\frac{n}{2}} \rceil}m}</tex> соответственно.  
  
 
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.
 
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.
  
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \dfrac{I_1 + I_2 + I_3 + I_4}{4} = \dfrac{k^{nm}+k^{\lceil \dfrac{m}{2} \rceil n} + k^{{\lceil {\dfrac{n}{2}} \rceil}m} + k^{{\lceil {\dfrac{nm}{2}} \rceil}}}{4}</tex>
+
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{k \in G}I(k) = \dfrac{I_1 + I_2 + I_3 + I_4}{4} = \dfrac{k^{nm}+k^{\lceil \frac{m}{2} \rceil n} + k^{{\lceil {\frac{n}{2}} \rceil}m} + k^{{\lceil {\frac{n}{2}} \rceil}{\lceil \frac{m}{2} \rceil}}}{4}</tex>
 
 
==Задача о числе раскрасок граней куба==
 
{{Задача
 
|definition=Выведите формулу для числа раскрасок граней куба в <tex>k</tex> цветов с точностью до поворота.
 
}}
 
Как и в предыдущей задаче, будем использовать в решении лемму Бёрнсайда.
 
 
 
'''Решение'''
 
 
 
Рассмотрим группу вращений куба <tex>G</tex>:
 
 
 
''Последующие изображения с развертками будут подразумевать такое же соответствие вершин, как на рисунке ниже. На развертках будем показывать раскраски, а на самом кубе ребро, через которое мы будем вращать его.  Цвета на развертке лишь показывают то, что грани с одинаковым цветом должны быть одинаково раскрашены.''
 
[[Файл:burnside-intro.png|top]]
 
* <tex>1</tex> Тождественное вращение. Поскольку ничего не происходит, мы можем покрасить каждую грань в любой цвет <tex>\Rightarrow k^6 </tex>  раскрасок.
 
[[Файл:burnside-1.png|top]]
 
* <tex>4</tex> вращения на угол <tex>120^{\circ}</tex> и <tex>4</tex> вращения на угол <tex>240^{\circ}</tex> вдоль главных диагоналей куба (вращений четыре, поскольку главных диагоналей <tex>4</tex> шт.). При вращении, если одна грань переходит в другую, мы должны покрасить их в один цвет. Такие раскраски будут являться стабилизатором данного вращения. Из рисунка видно, что мы можем покрасить наш куб в <tex>k^2</tex> цветов (в <tex>k</tex> цветов одни три грани и в <tex>k</tex> цветов другие три грани).
 
[[Файл:burnside-2.png|top]]
 
* <tex>6</tex> вращений на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих середины противоположных ребер <tex>\Rightarrow k^3 </tex>  раскрасок.
 
[[Файл:burnside-3.png|top]]
 
* <tex>3</tex> вращения на угол <tex>90^{\circ}</tex> и <tex>3</tex> вращения на угол <tex>270^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней <tex>\Rightarrow k^3 </tex>  раскрасок.
 
[[Файл:burnside-4.png|top]]
 
* <tex>3</tex> вращения на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней <tex>\Rightarrow k^4 </tex>  раскрасок.
 
[[Файл:burnside-5.png|top]]
 
 
 
Итого <tex>1+(4+4)+6+(3+3)+3=24</tex> поворота, при которых куб переходит в себя. Других различных поворотов, которые переводят куб в себя, не существует, поскольку ''группа вращений'' [https://en.wikipedia.org/wiki/Octahedral_symmetry <tex>G</tex> изоморфна ''симметрической группе'' <tex>S_4</tex>], тогда из того, что <tex>|S_4|=24</tex> следует, что мы указали все преобразования, которые переводят куб в себя, причем различным образом.
 
 
 
Теперь с помощью Леммы Бёрнсайда найдем искомый ответ:
 
 
 
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \dfrac{1} {24} (k^6 + 8k^2 + 6k^3 + 6k^3 + 3k^4) = \dfrac{1} {24} (k^6 + 3k^4 + 12k^3 + 8k^2)</tex>
 
  
 
==См. также==
 
==См. также==
 
* [[Теорема Кэли|Теорема Кэли]]
 
* [[Теорема Кэли|Теорема Кэли]]
* [[Задача об ожерельях|Задача об ожерельях]]
+
* [[Задача об ожерельях|Задача об Ожерельях]]
  
 
==Источники информации==
 
==Источники информации==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)