Редактирование: Лемма Бёрнсайда и Теорема Пойа
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности. | Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности. | ||
− | Если это отношение является отношением "с точностью до | + | Если это отношение является отношением "с точностью до действия элементом группы", то такой подсчет можно провести |
с помощью Леммы Бернсайда. | с помощью Леммы Бернсайда. | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Пусть | + | Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. '''Неподвижной точкой''' (стабилизатором) для элемента <tex>g</tex> называется такой элемент <tex>x</tex>, |
для которого <tex>gx=x</tex>. | для которого <tex>gx=x</tex>. | ||
}} | }} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == Лемма Бёрнсайда | + | == Лемма Бёрнсайда == |
{{Лемма | {{Лемма | ||
|id=lemmaBerns. | |id=lemmaBerns. | ||
− | |author= | + | |author=Бёрнсайд |
− | |statement= | + | |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>. | ||
|proof= | |proof= | ||
− | Так как <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>. |
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство: | Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство: | ||
− | < | + | <tex>|C|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex> |
− | |||
− | |||
Рассмотрим правую часть равенства: | Рассмотрим правую часть равенства: | ||
− | < | + | <tex>|\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum\limits_{x \in X} |G_x| = \sum\limits_{x \in X}</tex><tex dpi = "180"> \frac{|G|}{|Gx|}</tex><tex> = |G| \sum\limits_{x \in X}</tex><tex dpi = "180">\frac{1}{|Gx|} </tex> |
− | < | + | <tex>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex> |
− | Заметим, что < | + | Заметим, что <tex>\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><tex> = </tex><tex dpi = "180"> \frac{1}{|P|}</tex><tex>\sum\limits_{1}^{|P|}{1} = 1.</tex> Следовательно: |
− | < | + | <tex>|G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><tex> = |G|\sum\limits_{P\in C} 1</tex>. |
− | Очевидно, что < | + | Очевидно, что <tex>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</tex> Тогда получим: |
− | < | + | <tex>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</tex> |
Откуда следует, что | Откуда следует, что | ||
− | < | + | <tex>\sum\limits_{k \in G}I(k) = |C|\cdot|G|.</tex> ч.т.д. |
}} | }} | ||
− | == Теорема Пойа | + | == Теорема Пойа == |
− | Теорема Пойа является обобщением | + | Теорема Пойа является обобщением теоремы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как кол-во циклов в перестановке. |
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда. | В основе доказательства теоремы Пойа лежит лемма Бёрнсайда. | ||
Строка 59: | Строка 50: | ||
{{Теорема | {{Теорема | ||
|id=teorPo. | |id=teorPo. | ||
− | |author=Пойа | + | |author=Пойа |
− | |statement= < | + | |statement= <tex> C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{k \in G} l^{P(k)}</tex> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(k)</tex> {{---}} кол-во циклов в перестановке <tex>k</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента. |
− | |proof=Для доказательства этой | + | |proof=Для доказательства этой теорем достаточно установить следующее равенство |
− | < | + | <tex>I(k) = l^{P(k)}</tex> |
− | Рассмотрим некоторую перестановку <tex> | + | Рассмотрим некоторую перестановку <tex>k</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>k</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fk = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>k</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.: |
− | < | + | <tex>I(k) = l^{P(k)}</tex> |
}} | }} | ||
Строка 77: | Строка 68: | ||
'''Решение''' | '''Решение''' | ||
− | Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta | + | Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, и "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex>. |
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>. | Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>. | ||
Строка 88: | Строка 79: | ||
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится. | Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится. | ||
− | Количество | + | Количество стабилизаторов в случае с действием <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| = \ | + | :<tex dpi = "160"> |C| = \frac{1} {|G|} \sum\limits_{k \in G}I(k) = \frac{I_1 + I_2 + I_3 + I_4}{4} = \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> |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==См. также== | ==См. также== | ||
* [[Теорема Кэли|Теорема Кэли]] | * [[Теорема Кэли|Теорема Кэли]] | ||
− | * [[Задача об | + | * [[Задача об Ожерельях|Задача об Ожерельях]] |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | ==Cсылки== | ||
+ | *[http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%91%D1%91%D1%80%D0%BD%D1%81%D0%B0%D0%B9%D0%B4%D0%B0 Лемма Бёрнсайда] | ||
+ | *[http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0 Теорема Пойа] | ||