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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Пойа)
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|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>.
 
}}
 
}}
Строка 15: Строка 15:
 
|id=lemmaBerns.  
 
|id=lemmaBerns.  
 
|author=Бёрнсайд
 
|author=Бёрнсайд
|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> действует на множество <tex>X</tex>. Будем называть два элемента <tex>x</tex> и <tex>y</tex> эквивалентными, если <tex>x = gy</tex> для некоторого <tex>g \in G</tex>. Тогда число классов эквивалентности равно сумме числа стабилизаторов по всем элементам группы <tex>G</tex>, делённой на размер этой группы:
  
<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>.
+
<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>I(k)</tex> - сумма неподвижных точек для элемента <tex>k</tex>, то по определению <tex>\sum\limits_{k \in G}I(k) = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.
+
Так как <tex>I(k)</tex> - сумма стабилизаторов элемента <tex>k</tex>, то по определению <tex>\sum\limits_{k \in G}I(k) = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.
  
 
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:
 
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:
Строка 59: Строка 59:
 
<tex>I(k) = l^{P(k)}</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>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 \frac{m}{2} \rceil n}</tex> и <tex>k^{{\lceil {\frac{n}{2}} \rceil}m}</tex> соответственно.
 +
 +
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.
 +
 +
:<tex dpi = "180"> |C| = </tex> <tex>\frac{1} {|G|}</tex><tex>\sum\limits_{k \in G}I(k) = \frac{I_1 + I_2 + I_3 + I_4}{4} = </tex>
 +
:<tex dpi = "180"> = \frac{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>
  
 
==См. также==
 
==См. также==

Версия 00:08, 27 декабря 2013

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


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


Лемма Бёрнсайда

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

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

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

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

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

[math]|G|\sum_{P\in C}\sum_{x\in P}[/math][math] \frac{1}{|P|}[/math][math] = |G|\sum_{P\in C} 1[/math].

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

[math]|G|\sum_{P\in C} 1 = |C|\cdot|G|.[/math]

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

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

Теорема Пойа

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


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

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


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

[math]I(k) = l^{P(k)}[/math]
[math]\triangleleft[/math]

Задача о раскрашивании прямоугольника

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

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

Решение

Для начала определим, какие операции определены на группе [math]G[/math] --- это операция "отражение относительно горизонтальной оси", обозначим ее как [math]\alpha[/math] и "отражение относительно вертикальной оси" - [math]\beta[/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 \frac{m}{2} \rceil n}[/math] и [math]k^{{\lceil {\frac{n}{2}} \rceil}m}[/math] соответственно.

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

[math] |C| = [/math] [math]\frac{1} {|G|}[/math][math]\sum\limits_{k \in G}I(k) = \frac{I_1 + I_2 + I_3 + I_4}{4} = [/math]
[math] = \frac{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}[/math]

См. также

Cсылки