Лемма Бёрнсайда и Теорема Пойа

Материал из Викиконспекты
Перейти к: навигация, поиск

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


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


Содержание

[править] Лемма Бёрнсайда

Лемма (Бернсайд, англ. Burnside's lemma):
Пусть группа G действует на множество X. Будем называть два элемента x и y эквивалентными, если x = gy для некоторого g \in G. Тогда число классов эквивалентности равно сумме числа стабилизаторов по всем элементам группы G, делённой на размер этой группы: |C| = \frac{1} {|G|}\sum\limits_{k \in G}I(k). Где I(k) — количество стабилизаторов для элемента k.
Доказательство:
\triangleright

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

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

Рассмотрим правую часть равенства: |\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum\limits_{x \in X} |G_x| = \sum\limits_{x \in X}\frac{|G|}{|Gx|}= |G| \sum\limits_{x \in X}\frac{1}{|Gx|} = |G|\sum\limits_{P\in C}\sum\limits_{x\in P}\frac{1}{|P|}

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

|G|\sum\limits_{P\in C}\sum\limits_{x\in P}\frac{1}{|P|}= |G|\sum\limits_{P\in C} 1.

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

|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.

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

\sum\limits_{k \in G}I(k) = |C|\cdot|G|. ч.т.д.
\triangleleft

[править] Теорема Пойа

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


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

Для доказательства этой теоремы достаточно установить следующее равенство I(k) = l^{P(k)}


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

I(k) = l^{P(k)}
\triangleleft

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

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

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

Решение

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

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

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

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

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

Количество стабилизаторов в случае с действием e равно k^{nm}, так как ни одна раскрашенная клетка не повторилась при действии нулевого действия. Для действий \alpha и \beta количество раскрасок будет k^{\lceil \frac{m}{2} \rceil n} и k^{{\lceil {\frac{n}{2}} \rceil}m} соответственно.

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

|C| = \dfrac{1} {|G|} \sum\limits_{k \in G}I(k) = \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}

[править] См. также

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты