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

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

См. также

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