Изменения

Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' (стабилизатором (англ.stabilizer)) для элемента <tex>g</tex> называется такой элемент <tex>x</tex>,

== Лемма Бёрнсайда (англ. Burnside's lemma) ==

|author=БёрнсайдБернсайд, '''англ.''' Burnside's lemma|statement=Пусть группа Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex> действует на множество . <texmath>|X</tex>. Будем называть два элемента <tex>x</tex> и <tex>y</tex> эквивалентными, если <tex>x = gy</tex> для некоторого <tex>g \in G</tex>. Тогда число классов эквивалентности (англ. equivalence classes) равно сумме числа стабилизаторов по всем элементам группы <tex>G</tex>, делённой на размер этой группы: <tex> |C| = </tex> <tex dpi = "180">\fracdfrac{1} {|G|}</tex><tex>\sum\limits_{k g \in G}I|St(kg)|</tex>. Где <tex>I(k)</tex> {{---}} количество стабилизаторов для элемента <tex>k</texmath>.

Так как <tex>ISt(kg)</tex> {{---}} сумма стабилизаторов стабилизатор элемента <tex>kg</tex>, то по определению <texmath>\sum\limits_{k g \in G}I|St(kg) | = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</texmath>.

<texmath>|CX/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</math> Введем обозначение <tex>C=X/G</tex>.

<texmath>|\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum\limits_{x \in X} |G_x| = \sum\limits_{x \in X}</texmath><tex dpi = "180"math> \fracdfrac{|G|}{|Gx|}</tex><tex> = |G| \sum\limits_{x \in X}</tex><tex dpi = "180">\fracdfrac{1}{|Gx|} </texmath><texmath>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</texmath><tex dpi = "180"math> \fracdfrac{1}{|P|}</texmath>

Заметим, что <texmath>\sum\limits_{x\in P}</tex><tex dpi = "180"> \fracdfrac{1}{|P|}</tex><tex> = </tex><tex dpi = "180"> \fracdfrac{1}{|P|}</tex><tex>\sum\limits_{1}^{|P|}{1} = 1.</texmath> Следовательно:

<texmath>|G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \fracdfrac{1}{|P|}</tex><tex> = |G|\sum\limits_{P\in C} 1</texmath>.

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

<texmath>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</texmath>

<texmath>\sum\limits_{k g \in G}I|St(kg) | = |C|\cdot|G|.</texmath> ч.т.д.

== Теорема Пойа (англ. Pólya enumeration theorem) ==

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

|author=Пойа, '''англ.''' Pólya enumeration theorem|statement= <texmath> C =</tex> <tex dpi = "180"> \fracdfrac{1} {|G|}</tex><tex>\sum\limits_{k g \in G} l^{P(kg)}</texmath> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(kg)</tex> {{---}} кол-во циклов в перестановке <tex>kg</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.|proof=Для доказательства этой теорем теоремы достаточно установить следующее равенство<texmath>I|St(kg) | = l^{P(kg)}</texmath>

Рассмотрим некоторую перестановку <tex>kg</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>kg</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fk fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>kg</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:<texmath>I|St(kg) | = l^{P(kg)}</texmath>

Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, и "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.

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

:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{k g \in G}I|St(kg) | = \dfrac{I_1 + I_2 + I_3 + I_4}{4} = \dfrac{k^{nm}+k^{\lceil \fracdfrac{m}{2} \rceil n} + k^{{\lceil {\fracdfrac{n}{2}} \rceil}m} + k^{{\lceil {\fracdfrac{nnm}{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^{\lceil circ}</tex> вдоль осей, соединяющих середины противоположных ребер <tex>\Rightarrow k^3 </tex> раскрасок.[[Файл:burnside-3.png|top]]* <tex>3</tex> вращения на угол <tex>90^{\fraccirc}</tex> и <tex>3</tex> вращения на угол <tex>270^{m\circ}</tex> вдоль осей, соединяющих центры противоположных граней <tex>\Rightarrow k^3 </tex> раскрасок.[[Файл:burnside-4.png|top]]* <tex>3</tex> вращения на угол <tex>180^{2\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| = \rceildfrac{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>

* [[Задача об ожерельях|Задача об Ожерельях]]* [[Действие перестановки на набор из элементов, представление в виде циклов|Циклы в перестановкахожерельях]]