http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=195.209.248.4&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T14:56:35ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B0&diff=63716Заглавная страница2018-02-08T12:05:23Z<p>195.209.248.4: </p>
<hr />
<div>Добро пожаловать на сайт [[Вики-конспекты|вики-конспектов]]!<br />
<br />
= Проверяемые конспекты =<br />
<br />
== [[Дискретная математика | Дискретная математика]]==<br />
* [[Дискретная математика#Отношения| Отношения]]<br />
* [[Дискретная математика#Булевы функции| Булевы функции]]<br />
* [[Дискретная математика#Схемы из функциональных элементов| Схемы из функциональных элементов]]<br />
* [[Дискретная математика#Представление информации| Представление информации]]<br />
* [[Дискретная математика#Алгоритмы сжатия| Алгоритмы сжатия данных]]<br />
* [[Дискретная математика#Комбинаторика| Комбинаторика]]<br />
* [[Дискретная математика#Производящая функция|Производящая функция]]<br />
<br />
==[[Теория вероятностей | Теория вероятностей]]==<br />
* [[Теория вероятностей # Теория вероятностей| Базовые определения и формулы расчета вероятности]]<br />
* [[Теория вероятностей #Марковские цепи| Марковские цепи]]<br />
<br />
==[[Теория формальных языков|Теория формальных языков]]==<br />
* [[Теория формальных языков#Автоматы и регулярные языки|Автоматы и регулярные языки]]<br />
* [[Теория формальных языков#Контекстно-свободные грамматики|Контекстно-свободные грамматики]]<br />
<br />
== [[Теория матроидов | Теория матроидов]]==<br />
<br />
* [[Теория матроидов#Основные факты теории матроидов | Основные факты]]<br />
* [[Теория матроидов#Пересечение матроидов | Пересечение матроидов]]<br />
* [[Теория матроидов#Объединение матроидов | Объединение матроидов]]<br />
<br />
== [[Теория расписаний | Теория расписаний]]==<br />
<br />
*[[Теория расписаний#Задачи с одним станком | Задачи с одним станком]]<br />
*[[Теория расписаний#Специальные случаи задач для двух станков | Специальные случаи задач для двух станков]]<br />
*[[Теория расписаний#Задачи для произвольного числа станков | Задачи для произвольного числа станков]]<br />
<br />
== [[Теория вычислимости | Теория вычислимости]]==<br />
* [[Теория вычислимости#Разрешимые и перечислимые языки | Разрешимые и перечислимые языки]]<br />
* [[Теория вычислимости#Вычислительные формализмы | Вычислительные формализмы]]<br />
* [[Теория вычислимости#Примеры неразрешимых задач | Примеры неразрешимых задач]]<br />
<br />
==[[Теория сложности | Теория сложности]]==<br />
* [[Теория сложности#Детерминированные и недетерминированные вычисления, сложность по времени и по памяти | Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]<br />
* [[Теория сложности#Схемная сложность | Схемная сложность]]<br />
* [[Теория сложности#Вероятностные сложностные классы | Вероятностные сложностные классы]]<br />
<br />
== [[Алгоритмы и структуры данных | Алгоритмы и структуры данных]]==<br />
* [[Алгоритмы и структуры данных#Амортизационный анализ | Амортизационный анализ]]<br />
* [[Алгоритмы и структуры данных#Персистентные структуры данных | Персистентные структуры данных]]<br />
* [[Алгоритмы и структуры данных#Приоритетные очереди | Приоритетные очереди]]<br />
* [[Алгоритмы и структуры данных#Система непересекающихся множеств | Система непересекающихся множеств]]<br />
* [[Алгоритмы и структуры данных#Поисковые структуры данных | Поисковые структуры данных]]<br />
* [[Алгоритмы и структуры данных#Запросы на отрезках | Запросы на отрезках]]<br />
* [[Алгоритмы и структуры данных#Дерево Фенвика | Дерево Фенвика]]<br />
* [[Алгоритмы и структуры данных#Задача о наименьшем общем предке | Задача о наименьшем общем предке]]<br />
* [[Алгоритмы и структуры данных#Хеширование | Хеширование]]<br />
* [[Алгоритмы и структуры данных#Сортировки | Сортировки]]<br />
* [[Алгоритмы и структуры данных#Сортирующие сети | Сортирующие сети]]<br />
* [[Алгоритмы и структуры данных#Алгоритмы поиска | Алгоритмы поиска]]<br />
* [[Алгоритмы и структуры данных#Динамическое программирование | Динамическое программирование]]<br />
<br />
== [[Теория графов | Теория графов]]==<br />
* [[Теория графов#Основные определения теории графов | Основные определения теории графов]]<br />
* [[Теория графов#Связность в графах | Связность в графах]]<br />
* [[Теория графов#Остовные деревья | Остовные деревья]]<br />
* [[Теория графов#Обходы графов | Обходы графов]]<br />
* [[Теория графов# Укладки графов | Укладки графов]]<br />
* [[Теория графов#Раскраски графов | Раскраски графов]]<br />
* [[Теория графов#Обход в глубину | Обход в глубину]]<br />
* [[Теория графов#Кратчайшие пути в графах | Кратчайшие пути в графах]]<br />
* [[Теория графов#Задача о паросочетании | Задача о паросочетании]]<br />
* [[Теория графов#Задача о максимальном потоке | Задача о максимальном потоке]]<br />
* [[Теория графов#Задача о потоке минимальной стоимости | Задача о потоке минимальной стоимости]]<br />
== [[Алгоритмы на строках | Алгоритмы на строках]]==<br />
* [[Алгоритмы на строках# Поиск подстроки в строке | Поиск подстроки в строке]]<br />
* [[Алгоритмы на строках#Суффиксное дерево |Суффиксное дерево]]<br />
* [[Алгоритмы на строках#Суффиксный массив | Суффиксный массив]]<br />
<br />
== [[Методы трансляции | Методы трансляции]] ==<br />
* [[Методы трансляции#Нисходящий разбор|Нисходящий разбор]]<br />
* [[Методы трансляции#Восходящий разбор | Восходящий разбор]]<br />
<br />
== [[Вычислительная геометрия|Вычислительная геометрия ]]==<br />
* [[Вычислительная геометрия#Основание вычислительной геометрии|Основание вычислительной геометрии]]<br />
* [[Вычислительная геометрия#Вычисление геометрических предикатов|Вычисление геометрических предикатов]]<br />
* [[Вычислительная геометрия#Пересечение отрезков|Пересечение отрезков]]<br />
* [[Вычислительная геометрия#Выпуклые оболочки|Выпуклые оболочки]]<br />
* [[Вычислительная геометрия#Поиск|Поиск]]<br />
* [[Вычислительная геометрия#Триангуляция|Триангуляция]]<br />
* [[Вычислительная геометрия#ППЛГ и РСДС|ППЛГ и РСДС]]<br />
* [[Вычислительная геометрия#Алгоритмы локализации|Алгоритмы локализации]]<br />
* [[Вычислительная геометрия#Триангуляция Делоне и диаграмма Вороного|Триангуляция Делоне и диаграмма Вороного]]<br />
* [[Вычислительная геометрия#Планирование движения (Motion planning)|Планирование движения (Motion planning)]]<br />
<br />
== [[Язык программирования Java|Язык программирования Java]]==<br />
<br />
<br />
= Непроверяемые конспекты =<br />
<br />
*[[Алгебра и геометрия 1 курс | Алгебра и геометрия — 1, 2 семестр]]<br />
*[[Математический анализ 1 курс | Математический анализ — 1, 2 семестр]]<br />
*[[Математический анализ 2 курс | Математический анализ — 3, 4 семестр]]<br />
*[[Математическая логика|Математическая логика — 3 семестр]]<br />
*[[Участник:Qwerty787788/плюсы3сем | С++ — 2, 3 семестр]]<br />
*[[Дифференциальные уравнения | Дифференциальные уравнения — 3 семестр]]<br />
*[[Assembler|Assembler — 4 семестр]]<br />
*[[Алгоритмы алгебры и теории чисел|Алгоритмы алгебры и теории чисел — 4 семестр]]<br />
*[[Функциональный_анализ_3_курс | Функциональный анализ — 5, 6 семестр]]<br />
*[[Параллельное программирование|Параллельное программирование — 6 семестр]]<br />
*[[Базы данных|Базы данных — 7 семестр]]<br />
*[[Компьютерные сети|Компьютерные сети — 7, 8 семестр]]<br />
*[[Эволюционные алгоритмы|Эволюционные алгоритмы — 10 семестр]]</div>195.209.248.4http://neerc.ifmo.ru/wiki/index.php?title=%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_%D0%B8_%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0&diff=63704Лемма Бёрнсайда и Теорема Пойа2018-02-07T13:52:57Z<p>195.209.248.4: /* Лемма Бёрнсайда */</p>
<hr />
<div>Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.<br />
Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести<br />
с помощью Леммы Бернсайда.<br />
<br />
{{Определение<br />
|definition=<br />
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>, <br />
для которого <tex>gx=x</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Множество неподвижных точек элемента <tex>g</tex> называется его '''стабилизатором''' и обозначается <tex>St(g)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Пусть группа <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>.<br />
}}<br />
<br />
== Лемма Бёрнсайда ==<br />
<br />
{{Лемма<br />
|id=lemmaBerns. <br />
|author=Бернсайд, '''англ.''' Burnside's lemma<br />
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>. <math>|X/G| = \frac{1} {|G|}\sum\limits_{g \in G}|St(g)|</math>. <br />
|proof=<br />
Так как <tex>St(g)</tex> {{---}} стабилизатор элемента <tex>g</tex>, то по определению <math>\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</math>.<br />
<br />
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:<br />
<tex>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex><br />
<br />
Введем обозначение <tex>C=X/G</tex>.<br />
<br />
Рассмотрим правую часть равенства:<br />
<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><br />
<tex>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><br />
<br />
Заметим, что <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> Следовательно:<br />
<br />
<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>.<br />
<br />
Очевидно, что <tex>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</tex> Тогда получим:<br />
<br />
<tex>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</tex><br />
<br />
Откуда следует, что<br />
<br />
<tex>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</tex> ч.т.д.<br />
<br />
}}<br />
<br />
== Теорема Пойа ==<br />
<br />
Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].<br />
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.<br />
<br />
<br />
{{Теорема<br />
|id=teorPo. <br />
|author=Пойа, '''англ.''' Pólya enumeration theorem<br />
|statement= <tex> C =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{g \in G} l^{P(g)}</tex> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(g)</tex> {{---}} кол-во циклов в перестановке <tex>g</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.<br />
|proof=Для доказательства этой теоремы достаточно установить следующее равенство<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
<br />
<br />
Рассмотрим некоторую перестановку <tex>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
}}<br />
<br />
==Задача о числе раскрасок прямоугольника==<br />
{{Задача<br />
|definition=Выведите формулу для числа раскрасок прямоугольника <tex>[n \times m]</tex> в <tex>k</tex> цветов с точностью до отражения относительно горизонтальной и вертикальной оси. <br />
}}<br />
Решим данную задачу, воспользуясь леммой Бёрнсайда.<br />
<br />
'''Решение'''<br />
<br />
Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.<br />
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.<br />
<br />
Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <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>.<br />
<br />
Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:<br />
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.<br />
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.<br />
: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> нечетные).<br />
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.<br />
<br />
Количество неподвижных точек в случае с действием <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> соответственно. <br />
<br />
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.<br />
<br />
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \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><br />
<br />
==См. также==<br />
* [[Теорема Кэли|Теорема Кэли]]<br />
* [[Задача об ожерельях|Задача об Ожерельях]]<br />
<br />
==Источники информации==<br />
*[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 Википедия {{---}} Лемма Бёрнсайда]<br />
*[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 Википедия {{---}} Теорема Пойа]<br />
*[https://en.wikipedia.org/wiki/Burnside%27s_lemma Wikipedia {{---}} Burnside's lemma]<br />
*[https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]<br />
<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]<br />
[[Категория: Теория групп]]</div>195.209.248.4http://neerc.ifmo.ru/wiki/index.php?title=%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_%D0%B8_%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0&diff=63703Лемма Бёрнсайда и Теорема Пойа2018-02-07T13:52:25Z<p>195.209.248.4: /* Лемма Бёрнсайда */</p>
<hr />
<div>Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.<br />
Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести<br />
с помощью Леммы Бернсайда.<br />
<br />
{{Определение<br />
|definition=<br />
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>, <br />
для которого <tex>gx=x</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Множество неподвижных точек элемента <tex>g</tex> называется его '''стабилизатором''' и обозначается <tex>St(g)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Пусть группа <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>.<br />
}}<br />
<br />
== Лемма Бёрнсайда ==<br />
<br />
{{Лемма<br />
|id=lemmaBerns. <br />
|author=Бернсайд, '''англ.''' Burnside's lemma<br />
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>. <math>|X/G| = \frac{1} {|G|}\sum\limits_{g \in G}|St(g)|</math>. <br />
|proof=<br />
Так как <tex>St(g)</tex> {{---}} стабилизатор элемента <tex>g</tex>, то по определению <tex>\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.<br />
<br />
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:<br />
<tex>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex><br />
<br />
Введем обозначение <tex>C=X/G</tex>.<br />
<br />
Рассмотрим правую часть равенства:<br />
<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><br />
<tex>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><br />
<br />
Заметим, что <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> Следовательно:<br />
<br />
<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>.<br />
<br />
Очевидно, что <tex>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</tex> Тогда получим:<br />
<br />
<tex>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</tex><br />
<br />
Откуда следует, что<br />
<br />
<tex>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</tex> ч.т.д.<br />
<br />
}}<br />
<br />
== Теорема Пойа ==<br />
<br />
Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].<br />
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.<br />
<br />
<br />
{{Теорема<br />
|id=teorPo. <br />
|author=Пойа, '''англ.''' Pólya enumeration theorem<br />
|statement= <tex> C =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{g \in G} l^{P(g)}</tex> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(g)</tex> {{---}} кол-во циклов в перестановке <tex>g</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.<br />
|proof=Для доказательства этой теоремы достаточно установить следующее равенство<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
<br />
<br />
Рассмотрим некоторую перестановку <tex>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
}}<br />
<br />
==Задача о числе раскрасок прямоугольника==<br />
{{Задача<br />
|definition=Выведите формулу для числа раскрасок прямоугольника <tex>[n \times m]</tex> в <tex>k</tex> цветов с точностью до отражения относительно горизонтальной и вертикальной оси. <br />
}}<br />
Решим данную задачу, воспользуясь леммой Бёрнсайда.<br />
<br />
'''Решение'''<br />
<br />
Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.<br />
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.<br />
<br />
Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <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>.<br />
<br />
Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:<br />
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.<br />
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.<br />
: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> нечетные).<br />
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.<br />
<br />
Количество неподвижных точек в случае с действием <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> соответственно. <br />
<br />
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.<br />
<br />
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \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><br />
<br />
==См. также==<br />
* [[Теорема Кэли|Теорема Кэли]]<br />
* [[Задача об ожерельях|Задача об Ожерельях]]<br />
<br />
==Источники информации==<br />
*[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 Википедия {{---}} Лемма Бёрнсайда]<br />
*[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 Википедия {{---}} Теорема Пойа]<br />
*[https://en.wikipedia.org/wiki/Burnside%27s_lemma Wikipedia {{---}} Burnside's lemma]<br />
*[https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]<br />
<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]<br />
[[Категория: Теория групп]]</div>195.209.248.4http://neerc.ifmo.ru/wiki/index.php?title=%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_%D0%B8_%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0&diff=63702Лемма Бёрнсайда и Теорема Пойа2018-02-07T13:50:01Z<p>195.209.248.4: </p>
<hr />
<div>Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.<br />
Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести<br />
с помощью Леммы Бернсайда.<br />
<br />
{{Определение<br />
|definition=<br />
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>, <br />
для которого <tex>gx=x</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Множество неподвижных точек элемента <tex>g</tex> называется его '''стабилизатором''' и обозначается <tex>St(g)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Пусть группа <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>.<br />
}}<br />
<br />
== Лемма Бёрнсайда ==<br />
<br />
{{Лемма<br />
|id=lemmaBerns. <br />
|author=Бернсайд, '''англ.''' Burnside's lemma<br />
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>. <tex>|X/G| = \frac{1} {|G|}\sum\limits_{g \in G}|St(g)|</tex>. <br />
|proof=<br />
Так как <tex>St(g)</tex> {{---}} стабилизатор элемента <tex>g</tex>, то по определению <tex>\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.<br />
<br />
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:<br />
<tex>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex><br />
<br />
Введем обозначение <tex>C=X/G</tex>.<br />
<br />
Рассмотрим правую часть равенства:<br />
<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><br />
<tex>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><br />
<br />
Заметим, что <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> Следовательно:<br />
<br />
<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>.<br />
<br />
Очевидно, что <tex>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</tex> Тогда получим:<br />
<br />
<tex>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</tex><br />
<br />
Откуда следует, что<br />
<br />
<tex>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</tex> ч.т.д.<br />
<br />
}}<br />
<br />
== Теорема Пойа ==<br />
<br />
Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].<br />
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.<br />
<br />
<br />
{{Теорема<br />
|id=teorPo. <br />
|author=Пойа, '''англ.''' Pólya enumeration theorem<br />
|statement= <tex> C =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{g \in G} l^{P(g)}</tex> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(g)</tex> {{---}} кол-во циклов в перестановке <tex>g</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.<br />
|proof=Для доказательства этой теоремы достаточно установить следующее равенство<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
<br />
<br />
Рассмотрим некоторую перестановку <tex>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
}}<br />
<br />
==Задача о числе раскрасок прямоугольника==<br />
{{Задача<br />
|definition=Выведите формулу для числа раскрасок прямоугольника <tex>[n \times m]</tex> в <tex>k</tex> цветов с точностью до отражения относительно горизонтальной и вертикальной оси. <br />
}}<br />
Решим данную задачу, воспользуясь леммой Бёрнсайда.<br />
<br />
'''Решение'''<br />
<br />
Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.<br />
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.<br />
<br />
Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <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>.<br />
<br />
Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:<br />
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.<br />
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.<br />
: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> нечетные).<br />
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.<br />
<br />
Количество неподвижных точек в случае с действием <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> соответственно. <br />
<br />
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.<br />
<br />
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \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><br />
<br />
==См. также==<br />
* [[Теорема Кэли|Теорема Кэли]]<br />
* [[Задача об ожерельях|Задача об Ожерельях]]<br />
<br />
==Источники информации==<br />
*[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 Википедия {{---}} Лемма Бёрнсайда]<br />
*[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 Википедия {{---}} Теорема Пойа]<br />
*[https://en.wikipedia.org/wiki/Burnside%27s_lemma Wikipedia {{---}} Burnside's lemma]<br />
*[https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]<br />
<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]<br />
[[Категория: Теория групп]]</div>195.209.248.4http://neerc.ifmo.ru/wiki/index.php?title=%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_%D0%B8_%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0&diff=63701Лемма Бёрнсайда и Теорема Пойа2018-02-07T13:49:39Z<p>195.209.248.4: /* Лемма Бёрнсайда */</p>
<hr />
<div>Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.<br />
Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести<br />
с помощью Леммы Бернсайда.<br />
<br />
{{Определение<br />
|definition=<br />
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>, <br />
для которого <tex>gx=x</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Множество неподвижных точек элемента <tex>g</tex> называется его '''стабилизатором''' и обозначается <tex>St(g)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Пусть группа <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>.<br />
}}<br />
<br />
== Лемма Бёрнсайда ==<br />
<br />
{{Лемма<br />
|id=lemmaBerns. <br />
|author=Бернсайд, '''англ.''' Burnside's lemma<br />
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>.<br />
<tex>|X/G| = \frac{1} {|G|}\sum\limits_{g \in G}|St(g)|</tex>. <br />
|proof=<br />
Так как <tex>St(g)</tex> {{---}} стабилизатор элемента <tex>g</tex>, то по определению <tex>\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.<br />
<br />
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:<br />
<tex>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex><br />
<br />
Введем обозначение <tex>C=X/G</tex>.<br />
<br />
Рассмотрим правую часть равенства:<br />
<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><br />
<tex>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><br />
<br />
Заметим, что <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> Следовательно:<br />
<br />
<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>.<br />
<br />
Очевидно, что <tex>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</tex> Тогда получим:<br />
<br />
<tex>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</tex><br />
<br />
Откуда следует, что<br />
<br />
<tex>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</tex> ч.т.д.<br />
<br />
}}<br />
<br />
== Теорема Пойа ==<br />
<br />
Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].<br />
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.<br />
<br />
<br />
{{Теорема<br />
|id=teorPo. <br />
|author=Пойа, '''англ.''' Pólya enumeration theorem<br />
|statement= <tex> C =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{g \in G} l^{P(g)}</tex> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(g)</tex> {{---}} кол-во циклов в перестановке <tex>g</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.<br />
|proof=Для доказательства этой теоремы достаточно установить следующее равенство<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
<br />
<br />
Рассмотрим некоторую перестановку <tex>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
}}<br />
<br />
==Задача о числе раскрасок прямоугольника==<br />
{{Задача<br />
|definition=Выведите формулу для числа раскрасок прямоугольника <tex>[n \times m]</tex> в <tex>k</tex> цветов с точностью до отражения относительно горизонтальной и вертикальной оси. <br />
}}<br />
Решим данную задачу, воспользуясь леммой Бёрнсайда.<br />
<br />
'''Решение'''<br />
<br />
Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.<br />
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.<br />
<br />
Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <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>.<br />
<br />
Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:<br />
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.<br />
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.<br />
: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> нечетные).<br />
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.<br />
<br />
Количество неподвижных точек в случае с действием <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> соответственно. <br />
<br />
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.<br />
<br />
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \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><br />
<br />
==См. также==<br />
* [[Теорема Кэли|Теорема Кэли]]<br />
* [[Задача об ожерельях|Задача об Ожерельях]]<br />
<br />
==Источники информации==<br />
*[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 Википедия {{---}} Лемма Бёрнсайда]<br />
*[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 Википедия {{---}} Теорема Пойа]<br />
*[https://en.wikipedia.org/wiki/Burnside%27s_lemma Wikipedia {{---}} Burnside's lemma]<br />
*[https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]<br />
<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]<br />
[[Категория: Теория групп]]</div>195.209.248.4http://neerc.ifmo.ru/wiki/index.php?title=%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_%D0%B8_%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0&diff=63700Лемма Бёрнсайда и Теорема Пойа2018-02-07T13:49:23Z<p>195.209.248.4: /* Лемма Бёрнсайда */</p>
<hr />
<div>Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.<br />
Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести<br />
с помощью Леммы Бернсайда.<br />
<br />
{{Определение<br />
|definition=<br />
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>, <br />
для которого <tex>gx=x</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Множество неподвижных точек элемента <tex>g</tex> называется его '''стабилизатором''' и обозначается <tex>St(g)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Пусть группа <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>.<br />
}}<br />
<br />
== Лемма Бёрнсайда ==<br />
<br />
{{Лемма<br />
|id=lemmaBerns. <br />
|author=Бернсайд, '''англ.''' Burnside's lemma<br />
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>.<br />
<br />
<tex>|X/G| = \frac{1} {|G|}\sum\limits_{g \in G}|St(g)|</tex>. <br />
|proof=<br />
Так как <tex>St(g)</tex> {{---}} стабилизатор элемента <tex>g</tex>, то по определению <tex>\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.<br />
<br />
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:<br />
<tex>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex><br />
<br />
Введем обозначение <tex>C=X/G</tex>.<br />
<br />
Рассмотрим правую часть равенства:<br />
<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><br />
<tex>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><br />
<br />
Заметим, что <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> Следовательно:<br />
<br />
<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>.<br />
<br />
Очевидно, что <tex>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</tex> Тогда получим:<br />
<br />
<tex>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</tex><br />
<br />
Откуда следует, что<br />
<br />
<tex>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</tex> ч.т.д.<br />
<br />
}}<br />
<br />
== Теорема Пойа ==<br />
<br />
Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].<br />
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.<br />
<br />
<br />
{{Теорема<br />
|id=teorPo. <br />
|author=Пойа, '''англ.''' Pólya enumeration theorem<br />
|statement= <tex> C =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{g \in G} l^{P(g)}</tex> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(g)</tex> {{---}} кол-во циклов в перестановке <tex>g</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.<br />
|proof=Для доказательства этой теоремы достаточно установить следующее равенство<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
<br />
<br />
Рассмотрим некоторую перестановку <tex>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
}}<br />
<br />
==Задача о числе раскрасок прямоугольника==<br />
{{Задача<br />
|definition=Выведите формулу для числа раскрасок прямоугольника <tex>[n \times m]</tex> в <tex>k</tex> цветов с точностью до отражения относительно горизонтальной и вертикальной оси. <br />
}}<br />
Решим данную задачу, воспользуясь леммой Бёрнсайда.<br />
<br />
'''Решение'''<br />
<br />
Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.<br />
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.<br />
<br />
Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <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>.<br />
<br />
Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:<br />
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.<br />
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.<br />
: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> нечетные).<br />
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.<br />
<br />
Количество неподвижных точек в случае с действием <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> соответственно. <br />
<br />
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.<br />
<br />
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \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><br />
<br />
==См. также==<br />
* [[Теорема Кэли|Теорема Кэли]]<br />
* [[Задача об ожерельях|Задача об Ожерельях]]<br />
<br />
==Источники информации==<br />
*[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 Википедия {{---}} Лемма Бёрнсайда]<br />
*[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 Википедия {{---}} Теорема Пойа]<br />
*[https://en.wikipedia.org/wiki/Burnside%27s_lemma Wikipedia {{---}} Burnside's lemma]<br />
*[https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]<br />
<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]<br />
[[Категория: Теория групп]]</div>195.209.248.4http://neerc.ifmo.ru/wiki/index.php?title=%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_%D0%B8_%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%BE%D0%B9%D0%B0&diff=63699Лемма Бёрнсайда и Теорема Пойа2018-02-07T13:49:06Z<p>195.209.248.4: /* Лемма Бёрнсайда */</p>
<hr />
<div>Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.<br />
Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести<br />
с помощью Леммы Бернсайда.<br />
<br />
{{Определение<br />
|definition=<br />
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>, <br />
для которого <tex>gx=x</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Множество неподвижных точек элемента <tex>g</tex> называется его '''стабилизатором''' и обозначается <tex>St(g)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|definition=<br />
Пусть группа <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>.<br />
}}<br />
<br />
== Лемма Бёрнсайда ==<br />
<br />
{{Лемма<br />
|id=lemmaBerns. <br />
|author=Бернсайд, '''англ.''' Burnside's lemma<br />
|statement=Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex>.<br />
<br />
<tex> |X/G| = \frac{1} {|G|}\sum\limits_{g \in G}|St(g)|</tex>. <br />
|proof=<br />
Так как <tex>St(g)</tex> {{---}} стабилизатор элемента <tex>g</tex>, то по определению <tex>\sum\limits_{g \in G}|St(g)| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex>.<br />
<br />
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:<br />
<tex>|X/G|\cdot|G| = |\{(x, g) \in G\times X \mid g\cdot x = x\}|</tex><br />
<br />
Введем обозначение <tex>C=X/G</tex>.<br />
<br />
Рассмотрим правую часть равенства:<br />
<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><br />
<tex>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</tex><tex dpi = "180"> \frac{1}{|P|}</tex><br />
<br />
Заметим, что <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> Следовательно:<br />
<br />
<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>.<br />
<br />
Очевидно, что <tex>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</tex> Тогда получим:<br />
<br />
<tex>|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|.</tex><br />
<br />
Откуда следует, что<br />
<br />
<tex>\sum\limits_{g \in G}|St(g)| = |C|\cdot|G|.</tex> ч.т.д.<br />
<br />
}}<br />
<br />
== Теорема Пойа ==<br />
<br />
Теорема Пойа является обобщением леммы Бёрнсайда. Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].<br />
В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.<br />
<br />
<br />
{{Теорема<br />
|id=teorPo. <br />
|author=Пойа, '''англ.''' Pólya enumeration theorem<br />
|statement= <tex> C =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{g \in G} l^{P(g)}</tex> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(g)</tex> {{---}} кол-во циклов в перестановке <tex>g</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.<br />
|proof=Для доказательства этой теоремы достаточно установить следующее равенство<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
<br />
<br />
Рассмотрим некоторую перестановку <tex>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:<br />
<tex>|St(g)| = l^{P(g)}</tex><br />
}}<br />
<br />
==Задача о числе раскрасок прямоугольника==<br />
{{Задача<br />
|definition=Выведите формулу для числа раскрасок прямоугольника <tex>[n \times m]</tex> в <tex>k</tex> цветов с точностью до отражения относительно горизонтальной и вертикальной оси. <br />
}}<br />
Решим данную задачу, воспользуясь леммой Бёрнсайда.<br />
<br />
'''Решение'''<br />
<br />
Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.<br />
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.<br />
<br />
Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <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>.<br />
<br />
Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:<br />
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.<br />
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.<br />
: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> нечетные).<br />
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.<br />
<br />
Количество неподвижных точек в случае с действием <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> соответственно. <br />
<br />
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.<br />
<br />
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \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><br />
<br />
==См. также==<br />
* [[Теорема Кэли|Теорема Кэли]]<br />
* [[Задача об ожерельях|Задача об Ожерельях]]<br />
<br />
==Источники информации==<br />
*[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 Википедия {{---}} Лемма Бёрнсайда]<br />
*[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 Википедия {{---}} Теорема Пойа]<br />
*[https://en.wikipedia.org/wiki/Burnside%27s_lemma Wikipedia {{---}} Burnside's lemma]<br />
*[https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]<br />
<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]<br />
[[Категория: Теория групп]]</div>195.209.248.4