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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма Бёрнсайда)
м (rollbackEdits.php mass rollback)
 
(не показано 56 промежуточных версий 15 участников)
Строка 1: Строка 1:
 
Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.
 
Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.
Если это отношение является отношением "с точностью до действия элементом группы", то такой подсчет можно провести
+
Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести
 
с помощью Леммы Бернсайда.
 
с помощью Леммы Бернсайда.
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>,  
+
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <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>.
 +
}}
  
== Лемма Бёрнсайда ==
+
== Лемма Бёрнсайда ==
  
 
{{Лемма
 
{{Лемма
 
|id=lemmaBerns.  
 
|id=lemmaBerns.  
|author=Бёрнсайд
+
|author=Бернсайд, '''англ.''' Burnside's lemma
|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>, делённой на размер этой группы:
+
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>. <math>|X/G| = \dfrac{1} {|G|}\sum\limits_{g \in G}|St(g)|</math>.
 
 
<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>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>.
+
Так как <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>|C|\cdot|G| = |\{(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=X/G</tex>.
  
 
Рассмотрим правую часть равенства:
 
Рассмотрим правую часть равенства:
<tex>|\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum_{x \in X} |G_x| = \sum_{x \in X}</tex><tex dpi = "180"> \frac{|G|}{|Gx|}</tex><tex> = |G| \sum_{x \in X}</tex><tex dpi = "180">\frac{1}{|Gx|} </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>= |G|\sum_{P\in C}\sum_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex>
+
<math>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</math><math> \dfrac{1}{|P|}</math>
  
Заметим, что <tex>\sum_{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>\sum\limits_{x\in P} \dfrac{1}{|P|} = \dfrac{1}{|P|}\sum\limits_{1}^{|P|}{1} = 1.</math> Следовательно:
  
<tex>|G|\sum_{P\in C}\sum_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><tex> = |G|\sum_{P\in C} 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>\sum_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|</tex>. Тогда получим:
+
Очевидно, что <math>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</math> Тогда получим:
  
<tex>|G|\sum_{P\in C} 1 = |C|\cdot|G|.</tex>
+
<math>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</math>
  
 
Откуда следует, что
 
Откуда следует, что
  
<tex>\sum\limits_{k \in G}I(k) = |C|\cdot|G|.</tex> ч.т.д.
+
<math>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</math>  
 
   
 
   
 
}}
 
}}
  
== Теорема Пойа ==
+
== Теорема Пойа   ==
 
 
  
 +
Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].
 
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.
 
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.
  
Строка 50: Строка 59:
 
{{Теорема
 
{{Теорема
 
|id=teorPo.  
 
|id=teorPo.  
|author=Пойа
+
|author=Пойа, '''англ.''' Pólya enumeration theorem
|statement= <tex> C =</tex> <tex dpi = "180"> \frac{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> {{---}} кол-во различных состояний одного элемента.
+
|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> {{---}} кол-во различных состояний одного элемента.
|proof=Для доказательства этой теорем достаточно установить следующее равенство
+
|proof=Для доказательства этой теоремы достаточно установить следующее равенство
<tex>I(k) = l^{P(k)}</tex>
+
<math>|St(g)| = l^{P(g)}</math>
  
  
Рассмотрим некоторую перестановку <tex>k</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>k</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>k</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</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>I(k) = l^{P(k)}</tex>
+
<math>|St(g)| = l^{P(g)}</math>
 
}}
 
}}
  
 +
==Задача о числе раскрасок прямоугольника==
 +
{{Задача
 +
|definition=Выведите формулу для числа раскрасок прямоугольника <tex>[n \times m]</tex> в <tex>k</tex> цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
 +
}}
 +
Решим данную задачу, воспользуясь леммой Бёрнсайда.
 +
 +
'''Решение'''
 +
 +
Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.
 +
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.
 +
 +
Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <tex>\alpha</tex> и <tex>\beta</tex> не были включены в <tex>G</tex>. Это объясняется довольно просто: очевидно то, что операции коммутативны, то есть <tex>\alpha \circ \beta = \beta \circ \alpha</tex>, а также то, что <tex>\alpha \circ \alpha = \beta \circ \beta = e</tex>, тогда любая комбинация данных функций может быть упрощена до вышеперечисленных (в <tex>G</tex>) путем совмещения одинаковых и замены их на <tex>e</tex>.
 +
 +
Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:
 +
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.
 +
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.
 +
:3. С точностью до операции <tex>\alpha \circ \beta</tex> при нечетных <tex>n</tex> и <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n-1]</tex> в <tex>k</tex> цветов (а также частные случаи, когда <tex>n</tex> или <tex>m</tex> нечетные).
 +
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.
 +
 +
Количество неподвижных точек в случае с действием <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> |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>
 +
 +
==Задача о числе раскрасок граней куба==
 +
{{Задача
 +
|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>
  
 
==См. также==
 
==См. также==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D1%8D%D0%BB%D0%B8 Теорема Кэли]
+
* [[Теорема Кэли|Теорема Кэли]]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE%D0%B1_%D0%BE%D0%B6%D0%B5%D1%80%D0%B5%D0%BB%D1%8C%D1%8F%D1%85 Задача об Ожерельях]
+
* [[Задача об ожерельях|Задача об ожерельях]]
 +
 
 +
==Источники информации==
 +
*[http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%91%D1%91%D1%80%D0%BD%D1%81%D0%B0%D0%B9%D0%B4%D0%B0 Википедия {{---}} Лемма Бёрнсайда]
 +
*[http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0 Википедия {{---}} Теорема Пойа]
 +
*[https://en.wikipedia.org/wiki/Burnside%27s_lemma Wikipedia {{---}} Burnside's lemma]
 +
*[https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]
  
==Cсылки==
 
*[http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%91%D1%91%D1%80%D0%BD%D1%81%D0%B0%D0%B9%D0%B4%D0%B0 Лемма Бёрнсайда]
 
*[http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0 Теорема Пойа]
 
  
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]
 +
[[Категория: Теория групп]]

Текущая версия на 19:31, 4 сентября 2022

Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности. Если это отношение является отношением "с точностью до действия элементом группы", то такой подсчет можно провести с помощью Леммы Бернсайда.


Определение:
Пусть группа [math]G[/math] действует на множество [math]X[/math]. Неподвижной точкой для элемента [math]g[/math] называется такой элемент [math]x[/math], для которого [math]gx=x[/math].


Определение:
Множество неподвижных точек элемента [math]g[/math] называется его стабилизатором и обозначается [math]St(g)[/math].


Определение:
Пусть группа [math]G[/math] действует на множество [math]X[/math]. Будем называть два элемента [math]x[/math] и [math]y[/math] эквивалентными, если [math]x = gy[/math] для некоторого [math]g \in G[/math]. Классы эквивалентности данного отношения называются орбитами, множество орбит обозначается как [math]X/G[/math].


Лемма Бёрнсайда

Лемма (Бернсайд, англ. Burnside's lemma):
Число орбит равно средней мощности стабилизатора элементов группы [math]G[/math]. [math]|X/G| = \dfrac{1} {|G|}\sum\limits_{g \in G}|St(g)|[/math].
Доказательство:
[math]\triangleright[/math]

Так как [math]St(g)[/math] — стабилизатор элемента [math]g[/math], то по определению [math]\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|[/math].

Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство: [math]|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|[/math]

Введем обозначение [math]C=X/G[/math].

Рассмотрим правую часть равенства: [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] [math]= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}[/math][math] \dfrac{1}{|P|}[/math]

Заметим, что [math]\sum\limits_{x\in P} \dfrac{1}{|P|} = \dfrac{1}{|P|}\sum\limits_{1}^{|P|}{1} = 1.[/math] Следовательно:

[math]|G|\sum\limits_{P\in C}\sum\limits_{x\in P} \dfrac{1}{|P|} = |G|\sum\limits_{P\in C} 1[/math].

Очевидно, что [math]\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.[/math] Тогда получим:

[math]|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.[/math]

Откуда следует, что

[math]\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.[/math]
[math]\triangleleft[/math]

Теорема Пойа

Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как кол-во циклов в перестановке. В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.


Теорема (Пойа, англ. Pólya enumeration theorem):
[math]C = \dfrac{1}{|G|}\sum\limits_{g \in G} l^{P(g)}[/math] ,где [math]C[/math] — кол-во различных классов эквивалентности, [math]P(g)[/math] — кол-во циклов в перестановке [math]g[/math], [math]l[/math] — кол-во различных состояний одного элемента.
Доказательство:
[math]\triangleright[/math]

Для доказательства этой теоремы достаточно установить следующее равенство [math]|St(g)| = l^{P(g)}[/math]


Рассмотрим некоторую перестановку [math]g[/math] и некоторый элемент [math]f[/math]. Под действием перестановки [math]g[/math] элементы [math]f[/math] передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться [math]fg = f[/math], то внутри каждого цикла перестановки должны находиться одинаковые элементы [math]f[/math]. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки [math]g[/math] мы выбираем по одному значению, и, тем самым, мы получим все представления [math]f[/math], инвариантные относительно этой перестановки, т.е.:

[math]|St(g)| = l^{P(g)}[/math]
[math]\triangleleft[/math]

Задача о числе раскрасок прямоугольника

Задача:
Выведите формулу для числа раскрасок прямоугольника [math][n \times m][/math] в [math]k[/math] цветов с точностью до отражения относительно горизонтальной и вертикальной оси.

Решим данную задачу, воспользуясь леммой Бёрнсайда.

Решение

Для начала определим, какие операции определены на группе [math]G[/math] — это операция "отражение относительно горизонтальной оси", обозначим ее как [math]\alpha[/math], "отражение относительно вертикальной оси" — [math]\beta[/math] и "переход из одного состояния в него же" — [math]e[/math]. Таким образом, [math]G[/math] содержит 4 комбинации операций: [math]G = \{e, \alpha, \beta, \alpha \circ \beta \}[/math].

Стоит уделить особое внимание тому факту, что никакие иные комбинации функций [math]\alpha[/math] и [math]\beta[/math] не были включены в [math]G[/math]. Это объясняется довольно просто: очевидно то, что операции коммутативны, то есть [math]\alpha \circ \beta = \beta \circ \alpha[/math], а также то, что [math]\alpha \circ \alpha = \beta \circ \beta = e[/math], тогда любая комбинация данных функций может быть упрощена до вышеперечисленных (в [math]G[/math]) путем совмещения одинаковых и замены их на [math]e[/math].

Отметим также то, что количество раскрасок прямоугольника [math][m \times n][/math] в [math]k[/math] цветов:

1. С точностью до операции [math]\alpha[/math] при нечетном [math]m[/math] равно количеству раскрасок прямоугольника [math][m-1 \times n][/math] в [math]k[/math] цветов.
2. С точностью до операции [math]\beta[/math] при нечетном [math]n[/math] равно количеству раскрасок прямоугольника [math][m \times n-1][/math] в [math]k[/math] цветов.
3. С точностью до операции [math]\alpha \circ \beta[/math] при нечетных [math]n[/math] и [math]m[/math] равно количеству раскрасок прямоугольника [math][m-1 \times n-1][/math] в [math]k[/math] цветов (а также частные случаи, когда [math]n[/math] или [math]m[/math] нечетные).

Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.

Количество неподвижных точек в случае с действием [math]e[/math] равно [math]k^{nm}[/math], так как ни одна раскрашенная клетка не повторилась при действии нулевого действия. Для действий [math]\alpha[/math] и [math]\beta[/math] количество раскрасок будет [math]k^{\lceil \dfrac{m}{2} \rceil n}[/math] и [math]k^{{\lceil {\dfrac{n}{2}} \rceil}m}[/math] соответственно, для их композиции количество раскрасок [math]k^{{\lceil {\dfrac{nm}{2}} \rceil}}[/math], так как верхняя левая четверть прямоугольника однозначно задаёт правую нижнюю, аналогично с правой верхней.

Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.

[math] |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}[/math]

Задача о числе раскрасок граней куба

Задача:
Выведите формулу для числа раскрасок граней куба в [math]k[/math] цветов с точностью до поворота.

Как и в предыдущей задаче, будем использовать в решении лемму Бёрнсайда.

Решение

Рассмотрим группу вращений куба [math]G[/math]:

Последующие изображения с развертками будут подразумевать такое же соответствие вершин, как на рисунке ниже. На развертках будем показывать раскраски, а на самом кубе ребро, через которое мы будем вращать его. Цвета на развертке лишь показывают то, что грани с одинаковым цветом должны быть одинаково раскрашены. Burnside-intro.png

  • [math]1[/math] Тождественное вращение. Поскольку ничего не происходит, мы можем покрасить каждую грань в любой цвет [math]\Rightarrow k^6 [/math] раскрасок.

Burnside-1.png

  • [math]4[/math] вращения на угол [math]120^{\circ}[/math] и [math]4[/math] вращения на угол [math]240^{\circ}[/math] вдоль главных диагоналей куба (вращений четыре, поскольку главных диагоналей [math]4[/math] шт.). При вращении, если одна грань переходит в другую, мы должны покрасить их в один цвет. Такие раскраски будут являться стабилизатором данного вращения. Из рисунка видно, что мы можем покрасить наш куб в [math]k^2[/math] цветов (в [math]k[/math] цветов одни три грани и в [math]k[/math] цветов другие три грани).

Burnside-2.png

  • [math]6[/math] вращений на угол [math]180^{\circ}[/math] вдоль осей, соединяющих середины противоположных ребер [math]\Rightarrow k^3 [/math] раскрасок.

Burnside-3.png

  • [math]3[/math] вращения на угол [math]90^{\circ}[/math] и [math]3[/math] вращения на угол [math]270^{\circ}[/math] вдоль осей, соединяющих центры противоположных граней [math]\Rightarrow k^3 [/math] раскрасок.

Burnside-4.png

  • [math]3[/math] вращения на угол [math]180^{\circ}[/math] вдоль осей, соединяющих центры противоположных граней [math]\Rightarrow k^4 [/math] раскрасок.

Burnside-5.png

Итого [math]1+(4+4)+6+(3+3)+3=24[/math] поворота, при которых куб переходит в себя. Других различных поворотов, которые переводят куб в себя, не существует, поскольку группа вращений [math]G[/math] изоморфна симметрической группе [math]S_4[/math], тогда из того, что [math]|S_4|=24[/math] следует, что мы указали все преобразования, которые переводят куб в себя, причем различным образом.

Теперь с помощью Леммы Бёрнсайда найдем искомый ответ:

[math] |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)[/math]

См. также

Источники информации