Изменения
Нет описания правки
{{Определение
|definition=
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' ('''стабилизатором''', англ. ''stabilizer'') для элемента <tex>g</tex> называется такой элемент <tex>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.
|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>, делённой на размер этой группы:.
<tex> |CX/G| = </tex> <tex dpi = "180">\frac{1} {|G|}</tex><tex>\sum\limits_{k g \in G}I|St(kg)|</tex>. Где <tex>I(k)</tex> {{---}} количество стабилизаторов для элемента <tex>k</tex>.
|proof=
Так как <tex>ISt(kg)</tex> {{---}} сумма стабилизаторов стабилизатор элемента <tex>kg</tex>, то по определению <tex>\sum\limits_{k g \in G}I|St(kg) | = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:
<tex>|CX/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex> Введем обозначение <tex>C=X/G</tex>.
Рассмотрим правую часть равенства:
Откуда следует, что
<tex>\sum\limits_{k g \in G}I|St(kg) | = |C|\cdot|G|.</tex> ч.т.д.
}}
|id=teorPo.
|author=Пойа, '''англ.''' Pólya enumeration theorem
|statement= <tex> C =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{k g \in G} l^{P(kg)}</tex> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(kg)</tex> {{---}} кол-во циклов в перестановке <tex>kg</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.
|proof=Для доказательства этой теоремы достаточно установить следующее равенство
<tex>I|St(kg) | = l^{P(kg)}</tex>
Рассмотрим некоторую перестановку <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>, инвариантные относительно этой перестановки, т.е.:<tex>I|St(kg) | = l^{P(kg)}</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_{k g \in G}I|St(kg) | = \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>
==См. также==
