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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 59 промежуточных версий 16 участников)
Строка 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>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>\sum\limits_{k \in G}I(k)</tex> {{---}} это ничто иное как количество "инвариантных пар".
 
 
 
{{Определение
 
|definition= Пара элементов '''инвариантна''', если они оба принадлежат к одному классу эквивалентности.
 
}}
 
  
 +
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:
 +
<math>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</math>
  
Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества <tex>f</tex>, а внутри нее поставить величину <tex>J(f)</tex> {{---}} количество перестановок, относительно которых объект <tex>f</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>
 +
<math>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</math><math> \dfrac{1}{|P|}</math>
  
<tex >C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>
+
Заметим, что <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>.
  
Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями <tex>f_i</tex>, строки {{---}} всеми перестановками <tex>k_j</tex>, а в клетках таблицы будут стоять их произведения. Тогда, если мы будем рассматривать столбцы этой таблицы как множества, то некоторые из них могут совпасть, и это будет означать, что соответствующие этим столбцам <tex>f</tex> также эквивалентны. Таким образом, количество различных как множество столбцов равно количеству классов эквивалентности.
+
Очевидно, что <math>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</math> Тогда получим:
  
Столбцы таблицы сами распадаются на классы эквивалентности; зафиксируем теперь какой-либо класс и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы <tex>f_i</tex> одного класса (иначе получилось бы, что некоторым эквивалентным преобразованием  мы перешли в другой класс эквивалентности, что невозможно). Во-вторых, каждый элемент <tex>f_i</tex> будет встречаться одинаковое число раз во всех столбцах (это также следует из того, что столбцы соответствуют эквивалентным элементам). Отсюда можно сделать вывод, что все столбцы внутри одного класса эквивалентности совпадают друг с другом как мультимножества.
+
<math>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</math>
  
Теперь зафиксируем произвольный элемент <tex>f</tex>. С одной стороны, он встречается в своём столбце ровно <tex>J(f)</tex> раз (по самому определению). С другой стороны, все столбцы внутри одного класса эквивалентности одинаковы как мультимножества. Следовательно, внутри каждого столбца данного класса эквивалентности любой элемент <tex>g</tex> встречается ровно <tex>J(g)</tex> раз.
+
Откуда следует, что
  
Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, <tex>C|G|</tex> (это получается, просто умножив количество столбцов на их размер), а с другой стороны {{---}} сумму величин <tex>J(f)</tex> по всем <tex>f</tex>(это следует из всех предыдущих рассуждений):
+
<math>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</math>  
<tex> C =</tex> <tex  dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>
+
 
}}
 
}}
  
== Теорема Пойа ==
+
== Теорема Пойа   ==
 
 
  
 +
Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].
 
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.
 
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.
  
Строка 51: Строка 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]

См. также

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