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

Материал из Викиконспекты
Версия от 00:26, 15 января 2013; 178.66.245.81 (обсуждение) (Лемма Бёрнсайда)
Перейти к: навигация, поиск

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


Определение:
Пусть группа [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] = 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 = |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]f[/math]. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки [math]k[/math] мы выбираем по одному значению, и, тем самым, мы получим все представления [math]f[/math], инвариантные относительно этой перестановки, т.е.:

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


См. также

Cсылки