Изменения

Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провести

Пусть [[Группа|группа ]] <tex>G</tex> [[Действие группы на множестве|действует на множество ]] <tex>X</tex>. '''Неподвижной точкой''' для элемента <tex>g</tex> называется такой элемент <tex>x</tex>,

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

|author=БёрнсайдБернсайд, '''англ.''' Burnside's lemma|statement=Пусть группа Число орбит равно средней мощности стабилизатора элементов группы <tex>G</tex> действует на множество . <texmath>|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">\fracdfrac{1} {|G|}</tex><tex>\sum\limits_{k g \in G}I|St(kg)|</tex>. Где <tex>I(k)</tex> {{---}} количество неподвижных точек для элемента <tex>k</texmath>.

Рассмотрим сумму в числителе дроби справа:Так как <tex>\sum\limits_{k \in G}ISt(kg)</tex> {{---}} это ничто иное как количество "инвариантных пар". стабилизатор элемента <tex>g</tex>, то по определению <math>\sum\limits_{{Определениеg \in G}|St(g)|definition= Пара элементов '''инвариантна'''|\{(x, если они оба принадлежат к одному классу эквивалентностиg) \in G\times X \mid g\cdot x = x\}|</math>.}}

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

Заметим, что <tex math>C =</tex> <tex dpi \sum\limits_{x\in P} \dfrac{1}{|P|} = "180"> \fracdfrac{1} {|GP|}</tex><tex>\sum\limits_{f1}^{|P|} J(f){1} = 1.</texmath>Следовательно:

Для доказательства этой формулы составим таблицуОчевидно, столбцы которой будут подписаны всеми значениями что <texmath>f_i</tex>, строки \sum\limits_{P\in C} 1 = \sum\limits_{1}^{---|C|}{1} всеми перестановками <tex>k_j= |C|.</texmath>, а в клетках таблицы будут стоять их произведения. Тогда, если мы будем рассматривать столбцы этой таблицы как множества, то некоторые из них могут совпасть, и это будет означать, что соответствующие этим столбцам <tex>f</tex> также эквивалентны. Таким образом, количество различных как множество столбцов равно количеству классов эквивалентности. получим:

Столбцы таблицы сами распадаются на классы эквивалентности; зафиксируем теперь какой-либо класс и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы <tex>f_i</texmath> одного класса (иначе получилось бы, что некоторым эквивалентным преобразованием мы перешли в другой класс эквивалентности, что невозможно)|G|\sum\limits_{P\in C} 1 = |C|\cdot|G|. Во-вторых, каждый элемент <tex>f_i</texmath> будет встречаться одинаковое число раз во всех столбцах (это также следует из того, что столбцы соответствуют эквивалентным элементам). Отсюда можно сделать вывод, что все столбцы внутри одного класса эквивалентности совпадают друг с другом как мультимножества.

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

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

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

|author=Пойа, '''англ.''' Pólya enumeration theorem|statement= <texmath> C =</tex> <tex dpi = "180"> \fracdfrac{1} {|G|}</tex><tex>\sum\limits_{k g \in G} l^{P(kg)}</texmath> ,где <tex>C</tex> {{---}} кол-во различных классов эквивалентности, <tex>P(kg)</tex> {{--- }} кол-во циклов в перестановке <tex>kg</tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элемента.|proof=Для доказательства этой теорем теоремы достаточно установить следующее равенство<texmath>I|St(kg) | = l^{P(kg)}</texmath>

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

* [[Теорема Кэли|Теорема Кэли]]* [[Задача об ожерельях|Задача об ожерельях]] ==Источники информации==* [http://neercru.ifmowikipedia.ruorg/wiki/index.php?title=%D0%A29B%D0%B5%D0%BEBC%D1D0%80BC%D0%B5B0_%D0%BC91%D1%91%D1%80%D0%B0_BD%D1%81%D0%9AB0%D1D0%8DB9%D0%BBB4%D0%B8 Теорема КэлиB0 Википедия {{---}} Лемма Бёрнсайда]* [http://neercru.ifmowikipedia.ruorg/wiki/index.php?title=%D0%97A2%D0%B0B5%D0%B4%D0%B0BE%D1%8780%D0%B0_B5%D0%BEBC%D0%B1_B0_%D0%BE9F%D0%B6BE%D0%B5%D1%80B9%D0%B5B0 Википедия {{---}} Теорема Пойа]*[https://en.wikipedia.org/wiki/Burnside%D0%BB%D127s_lemma Wikipedia {{---}} Burnside's lemma]*[https://en.wikipedia.org/wiki/P%8CC3%D1%8F%D1%85 Задача об ОжерельяхB3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]