Изменения
Нет описания правки
{{Определение
|definition=
'''Классом эквивалентности''' <tex>C(a)</tex> элемента <tex>a</tex> называется подмножество элементов, эквивалентных <tex>a</tex>.
}}
Одним и тем же объектам могут соответствовать различные представления, но, разумеется, любое представление соответствует ровно одному объекту. Следовательно, множество всех представлений разбивается на классы эквивалентности. Лемма Бёрнсайда позволяет посчитать в некотором множестве, основываясь на некоторой его внутренней симметрии, количество классов эквивалентности. Док-во этой леммы, приведенное ниже, опирается на следующие определения:
{{Определение
|definition=
'''Инвариантная перестановка''' {{---}} такая перестановка, которая по условию задачи не меняет сам объект, а только его представление.
}}
Заметим, что произведение любых инвариантных перестановок тоже является инвариантной перестановкой.
{{Определение
}}
== Лемма Бернсайда Бёрнсайда ==
{{Лемма
|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>.
Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями <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>(это следует из всех предыдущих рассуждений):
== Теорема Пойа ==
Лемма Бёрнсайда лежит в основе доказательства теоремы Пойа.
{{Теорема
|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>
