Викиконспекты - Вклад участника [ru]

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

2013-01-14T21:26:19Z

178.66.245.81: /* Лемма Бёрнсайда */

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

2013-01-14T21:23:41Z

178.66.245.81: /* Лемма Бёрнсайда */

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

2013-01-14T20:24:53Z

178.66.245.81:

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

{{Определение
|definition=
Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>,
для которого <tex>gx=x</tex>.
}}

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

{{Лемма
|id=lemmaBerns.
|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>, делённой на размер этой группы:

<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=
Рассмотрим сумму в числителе дроби справа:
<tex>\sum\limits_{k \in G}I(k)</tex> {{---}} это ничто иное как количество "инвариантных пар".

{{Определение
|definition= Пара элементов '''инвариантна''', если они оба принадлежат к одному классу эквивалентности.
}}

Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества <tex>f</tex>, а внутри нее поставить величину <tex>J(f)</tex> {{---}} количество перестановок, относительно которых объект <tex>f</tex> инвариантен:

<tex >C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>

Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями <tex>f_i</tex>, строки {{---}} всеми перестановками <tex>k_j</tex>, а в клетках таблицы будут стоять их произведения. Тогда, если мы будем рассматривать столбцы этой таблицы как множества, то некоторые из них могут совпасть, и это будет означать, что соответствующие этим столбцам <tex>f</tex> также эквивалентны. Таким образом, количество различных как множество столбцов равно количеству классов эквивалентности.

Столбцы таблицы сами распадаются на классы эквивалентности; зафиксируем теперь какой-либо класс и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы <tex>f_i</tex> одного класса (иначе получилось бы, что некоторым эквивалентным преобразованием мы перешли в другой класс эквивалентности, что невозможно). Во-вторых, каждый элемент <tex>f_i</tex> будет встречаться одинаковое число раз во всех столбцах (это также следует из того, что столбцы соответствуют эквивалентным элементам). Отсюда можно сделать вывод, что все столбцы внутри одного класса эквивалентности совпадают друг с другом как мультимножества.

Теперь зафиксируем произвольный элемент <tex>f</tex>. С одной стороны, он встречается в своём столбце ровно <tex>J(f)</tex> раз (по самому определению). С другой стороны, все столбцы внутри одного класса эквивалентности одинаковы как мультимножества. Следовательно, внутри каждого столбца данного класса эквивалентности любой элемент <tex>g</tex> встречается ровно <tex>J(g)</tex> раз.

Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, <tex>C|G|</tex> (это получается, просто умножив количество столбцов на их размер), а с другой стороны {{---}} сумму величин <tex>J(f)</tex> по всем <tex>f</tex>(это следует из всех предыдущих рассуждений):
<tex> C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>
}}

== Теорема Пойа ==

В основе доказательства теоремы Пойа лежит лемма Бёрнсайда.

{{Теорема
|id=teorPo.
|author=Пойа
|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=Для доказательства этой теорем достаточно установить следующее равенство
<tex>I(k) = l^{P(k)}</tex>

Рассмотрим некоторую перестановку <tex>k</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>k</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>k</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:
<tex>I(k) = l^{P(k)}</tex>
}}

==См. также==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D1%8D%D0%BB%D0%B8 Теорема Кэли]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE%D0%B1_%D0%BE%D0%B6%D0%B5%D1%80%D0%B5%D0%BB%D1%8C%D1%8F%D1%85 Задача об Ожерельях]

==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 Теорема Пойа]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2013-01-14T14:37:48Z

178.66.245.81:

{{Определение
|definition=
'''Классом эквивалентности''' <tex>C(a)</tex> элемента <tex>a</tex> называется подмножество элементов, эквивалентных <tex>a</tex>.
}}

Одним и тем же объектам могут соответствовать различные представления, но, разумеется, любое представление соответствует ровно одному объекту. Следовательно, множество всех представлений разбивается на классы эквивалентности. Лемма Бёрнсайда позволяет посчитать в некотором множестве, основываясь на некоторой его внутренней симметрии, количество классов эквивалентности. Док-во этой леммы, приведенное ниже, опирается на следующие определения:

{{Определение
|definition=
'''Инвариантная перестановка''' {{---}} такая перестановка, которая по условию задачи не меняет сам объект, а только его представление.
}}

Заметим, что произведение любых инвариантных перестановок тоже является инвариантной перестановкой.

{{Определение
|definition=
'''Неподвижной точкой''' <tex>f</tex> для перестановки называется такой элемент, который инвариантен относительно этой перестановки.
}}

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

{{Лемма
|id=lemmaBerns.
|author=Бёрнсайд
|statement=Количество классов эквивалетности равно сумме количеств неподвижных точек по всем перестановкам из группы <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=
Рассмотрим сумму в числителе дроби справа:
<tex>\sum\limits_{k \in G}I(k)</tex> {{---}} это ничто иное как количество "инвариантных пар". Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества <tex>f</tex>, а внутри нее поставить величину <tex>J(f)</tex> {{---}} количество перестановок, относительно которых объект <tex>f</tex> инвариантен:

<tex >C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>

Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями <tex>f_i</tex>, строки {{---}} всеми перестановками <tex>k_j</tex>, а в клетках таблицы будут стоять их произведения. Тогда, если мы будем рассматривать столбцы этой таблицы как множества, то некоторые из них могут совпасть, и это будет означать, что соответствующие этим столбцам <tex>f</tex> также эквивалентны. Таким образом, количество различных как множество столбцов равно количеству классов эквивалентности.

Столбцы таблицы сами распадаются на классы эквивалентности; зафиксируем теперь какой-либо класс и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы <tex>f_i</tex> одного класса (иначе получилось бы, что некоторым эквивалентным преобразованием мы перешли в другой класс эквивалентности, что невозможно). Во-вторых, каждый элемент <tex>f_i</tex> будет встречаться одинаковое число раз во всех столбцах (это также следует из того, что столбцы соответствуют эквивалентным элементам). Отсюда можно сделать вывод, что все столбцы внутри одного класса эквивалентности совпадают друг с другом как мультимножества.

Теперь зафиксируем произвольный элемент <tex>f</tex>. С одной стороны, он встречается в своём столбце ровно <tex>J(f)</tex> раз (по самому определению). С другой стороны, все столбцы внутри одного класса эквивалентности одинаковы как мультимножества. Следовательно, внутри каждого столбца данного класса эквивалентности любой элемент <tex>g</tex> встречается ровно <tex>J(g)</tex> раз.

Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, <tex>C|G|</tex> (это получается, просто умножив количество столбцов на их размер), а с другой стороны {{---}} сумму величин <tex>J(f)</tex> по всем <tex>f</tex>(это следует из всех предыдущих рассуждений):
<tex> C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>
}}

== Теорема Пойа ==

Лемма Бёрнсайда лежит в основе доказательства теоремы Пойа.

{{Теорема
|id=teorPo.
|author=Пойа
|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=Для доказательства этой теорем достаточно установить следующее равенство
<tex>I(k) = l^{P(k)}</tex>

Рассмотрим некоторую перестановку <tex>k</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>k</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>k</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:
<tex>I(k) = l^{P(k)}</tex>
}}

==См. также==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE%D0%B1_%D0%BE%D0%B6%D0%B5%D1%80%D0%B5%D0%BB%D1%8C%D1%8F%D1%85 Задача об Ожерельях]

==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 Теорема Пойа]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Задача об ожерельях

2013-01-14T14:37:22Z

178.66.245.81: /* Алгоритм решения задачи про ожерелья */

{{Определение
|definition=
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}

Решение этой задачи опирается на [http://neerc.ifmo.ru/wiki/index.php?title=Лемма_Бёрнсайда_и_Теорема_Пойа Лемму Бёрнсайда и Теорему Пойа].

== Алгоритм решения задачи про ожерелья ==

Пусть нам даны бусинки <tex>k</tex> различных цветов, а ожерелье должно состоять из <tex>n</tex> бусинок.

Для решения воспользуемся формулой из теоремы Пойа.

<tex>C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{l \in G} k^{P(l)}</tex>

Заметим, что, по условию, перестановкой инвариантной данной в нашем случаем будет циклический сдвиг.
Очевидно, что для каждой перестановки длины <tex>n</tex> существует ровно <tex>n - 1</tex> инвариантная перестановка, то есть всего инвариантных перестановок в каждом классе <tex>n</tex>, теперь найдем <tex>P(i)</tex>. Заметим, что в <tex>i</tex>-ой перестановке на <tex>l</tex>-ой позиции стоит элемент <tex>(i + l)\mod n</tex>. Также, заметим, что элемент <tex>a</tex> переходит в элемент <tex>a + in</tex>, где <tex>i \in [1; k]</tex>. Из этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex>lcm(n, i)/i = n/gcd(i,n)</tex>.Откуда следует что:

<tex>C =</tex> <tex dpi = "180"> \frac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{gcd(i,n)}</tex>.

где <tex>C</tex> - кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex> различных цветов.

== См. также ==
* [http://neerc.ifmo.ru/wiki/index.php?title=Лемма_Бёрнсайда_и_Теорема_Пойа Лемма Бёрнсайда и Теорема Пойа]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]