1632
правки
Изменения
м
Одним и тем же объектам могут соответствовать различные представления, но, разумеется, любое представление соответствует ровно одному объекту. Следовательно, множество всех представлений разбивается на классы эквивалентности. Лемма Бёрнсайда позволяет посчитать в некотором множестве, основываясь на некоторой его внутренней симметрии, количество классов эквивалентности. Док-во этой леммы, приведенное ниже, опирается на следующие определения:
Заметим, что произведение любых инвариантных перестановок тоже является инвариантной перестановкой.
Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями <texmath>f_i</tex>, строки |G|\sum\limits_{P\in C}\sum\limits_{x\in P} \dfrac{1}{---|P|}= |G|\sum\limits_{P\in C} всеми перестановками <tex>k_j</tex>, а в клетках таблицы будут стоять их произведения. Тогда, если мы будем рассматривать столбцы этой таблицы как множества, то некоторые из них могут совпасть, и это будет означать, что соответствующие этим столбцам <tex>f1</texmath> также эквивалентны. Таким образом, количество различных как множество столбцов равно количеству классов эквивалентности.
Столбцы таблицы сами распадаются на классы эквивалентности; зафиксируем теперь какой-либо класс и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы <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>
Лемма Теорема Пойа является обобщением леммы Бёрнсайда лежит . Она также позволяет находить количество классов эквивалентности, но уже используя такую величину, как [[Действие перестановки на набор из элементов, представление в виде циклов|кол-во циклов в перестановке]].В основе доказательства теоремы Пойалежит лемма Бёрнсайда.
Рассмотрим некоторую перестановку ==Задача о числе раскрасок прямоугольника=={{Задача|definition=Выведите формулу для числа раскрасок прямоугольника <tex>k[n \times m]</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>
==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 Теорема Пойа]
rollbackEdits.php mass rollback
Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.Если это отношение является отношением "с точностью до [[Действие группы на множестве|действия элементом группы]]", то такой подсчет можно провестис помощью Леммы Бернсайда.
{{Определение
|definition=
Пусть [[Группа|группа]] <tex>G</tex> [[Действие группы на множестве|действует на множество]] <tex>X</tex>. '''Классом эквивалентностиНеподвижной точкой''' для элемента <tex>C(a)g</tex> элемента называется такой элемент <tex>ax</tex> называется подмножество элементов, эквивалентных для которого <tex>agx=x</tex>.
}}
{{Определение
|definition=
Множество неподвижных точек элемента <tex>g</tex> называется его '''Инвариантная перестановкастабилизатором''' {{---}} такая перестановка, которая по условию задачи не меняет сам объект, а только его представлениеи обозначается <tex>St(g)</tex>.
}}
{{Определение
|definition=
Пусть группа <tex>G</tex> действует на множество <tex>X</tex>. Будем называть два элемента <tex>x</tex> и <tex>y</tex> эквивалентными, если <tex>x = gy</tex> для некоторого <tex>g \in G</tex>. Классы эквивалентности данного отношения называются '''Неподвижной точкойорбитами''' , множество орбит обозначается как <tex>fX/G</tex> для перестановки называется такой элемент, который инвариантен относительно этой перестановки.
}}
== Лемма Бёрнсайда ==
{{Лемма
|id=lemmaBerns.
|author=БёрнсайдБернсайд, '''англ.''' Burnside's lemma|statement=Количество классов эквивалетности Число орбит равно сумме количеств неподвижных точек по всем перестановкам из средней мощности стабилизатора элементов группы <tex>G</tex>. <math>|X/G| = \dfrac{1} {|G|}\sum\limits_{g \in G}|St(g)|</math>. |proof=Так как <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>.
Следовательно для доказательства леммы необходимо и достаточно доказать следующее равенство:<texmath> C = <|X/tex> <tex dpi = "180">G|\frac{1} {cdot|G|}</tex><tex>\sum= |\limits_{k (x, g) \in G}I(k)</tex>. Где <tex>I(k)</tex> {{---}} количество неподвижных точек для перестановки <tex>k</tex>.|proof=Рассмотрим сумму в числителе дроби справа:<tex>\sumtimes X \mid g\limits_{k cdot x = x\in G}I(k)|</texmath> {{---}} это ничто иное как количество "инвариантных пар". Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества <tex>f</tex>, а внутри нее поставить величину <tex>J(f)</tex> {{---}} количество перестановок, относительно которых объект <tex>f</tex> инвариантен:
Введем обозначение <tex>C=X/G</tex>.
Рассмотрим правую часть равенства:<tex math>C |\{(x, g) \in G\times X \mid g\cdot x = x\}| = \sum\limits_{x \in X} |G_x| =\sum\limits_{x \in X}</texmath> <tex dpi math> \dfrac{|G|}{|Gx|} = "180"> |G| \sum\limits_{x \in X}\fracdfrac{1} {|GGx|}</texmath><texmath>= |G|\sum\limits_{fP\in C}\sum\limits_{x\in P}</math><math> \dfrac{1}{|P|} J(f)</texmath>
Заметим, что <math>\sum\limits_{x\in P} \dfrac{1}{|P|} = \dfrac{1}{|P|}\sum\limits_{1}^{|P|}{1} = 1.</math> Следовательно:
Очевидно, что <math>\sum\limits_{P\in C} 1 = \sum\limits_{1}^{|C|}{1} = |C|.</math> Тогда получим:
}}
== Теорема Пойа ==
{{Теорема
|id=teorPo.
|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>g</tex> и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>g</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что так как в результате должно получаться <tex>fg = f</tex>, то внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>g</tex> мы выбираем по одному значению, и, тем самым, мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:
<math>|St(g)| = l^{P(g)}</math>
}}
}}
Решим данную задачу, воспользуясь леммой Бёрнсайда.
'''Решение'''
Для начала определим, какие операции определены на группе <tex>G</tex> {{---}} это операция "отражение относительно горизонтальной оси", обозначим ее как <tex>\alpha</tex>, "отражение относительно вертикальной оси" {{---}} <tex>\beta</tex> и "переход из одного состояния в него же" {{---}} <tex>e</tex>.
Таким образом, <tex>G</tex> содержит 4 комбинации операций: <tex>G = \{e, \alpha, \beta, \alpha \circ \beta \}</tex>.
Стоит уделить особое внимание тому факту, что никакие иные комбинации функций <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>.
Отметим также то, что количество раскрасок прямоугольника <tex>[m \times n]</tex> в <tex>k</tex> цветов:
:1. С точностью до операции <tex>\alpha</tex> при нечетном <tex>m</tex> равно количеству раскрасок прямоугольника <tex>[m-1 \times n]</tex> в <tex>k</tex> цветов.
:2. С точностью до операции <tex>\beta</tex> при нечетном <tex>n</tex> равно количеству раскрасок прямоугольника <tex>[m \times n-1]</tex> в <tex>k</tex> цветов.
: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> нечетные).
Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.
Количество неподвижных точек в случае с действием <tex>e</tex> равно <tex>k^{nm}</tex>, так как ни одна раскрашенная клетка не повторилась при действии нулевого действия. Для действий <tex>\alpha</tex> и <tex>\beta</tex> количество раскрасок будет <tex>k^{\lceil \dfrac{m}{2} \rceil n}</tex> и <tex>k^{{\lceil {\dfrac{n}{2}} \rceil}m}</tex> соответственно, для их композиции количество раскрасок <tex>k^{{\lceil {\dfrac{nm}{2}} \rceil}}</tex>, так как верхняя левая четверть прямоугольника однозначно задаёт правую нижнюю, аналогично с правой верхней.
Тогда воспользуемся Леммой Бёрнсайда и определим количество таких раскрасок.
:<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 \dfrac{m}{2} \rceil n} + k^{{\lceil {\dfrac{n}{2}} \rceil}m} + k^{{\lceil {\dfrac{nm}{2}} \rceil}}}{4}</tex>
==Задача о числе раскрасок граней куба==
{{Задача
|definition=Выведите формулу для числа раскрасок граней куба в <tex>k</tex> цветов с точностью до поворота.
}}
Как и в предыдущей задаче, будем использовать в решении лемму Бёрнсайда.
'''Решение'''
Рассмотрим группу вращений куба <tex>G</tex>:
''Последующие изображения с развертками будут подразумевать такое же соответствие вершин, как на рисунке ниже. На развертках будем показывать раскраски, а на самом кубе ребро, через которое мы будем вращать его. Цвета на развертке лишь показывают то, что грани с одинаковым цветом должны быть одинаково раскрашены.''
[[Файл:burnside-intro.png|top]]
* <tex>1</tex> Тождественное вращение. Поскольку ничего не происходит, мы можем покрасить каждую грань в любой цвет <tex>\Rightarrow k^6 </tex> раскрасок.
[[Файл:burnside-1.png|top]]
* <tex>4</tex> вращения на угол <tex>120^{\circ}</tex> и <tex>4</tex> вращения на угол <tex>240^{\circ}</tex> вдоль главных диагоналей куба (вращений четыре, поскольку главных диагоналей <tex>4</tex> шт.). При вращении, если одна грань переходит в другую, мы должны покрасить их в один цвет. Такие раскраски будут являться стабилизатором данного вращения. Из рисунка видно, что мы можем покрасить наш куб в <tex>k^2</tex> цветов (в <tex>k</tex> цветов одни три грани и в <tex>k</tex> цветов другие три грани).
[[Файл:burnside-2.png|top]]
* <tex>6</tex> вращений на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих середины противоположных ребер <tex>\Rightarrow k^3 </tex> раскрасок.
[[Файл:burnside-3.png|top]]
* <tex>3</tex> вращения на угол <tex>90^{\circ}</tex> и <tex>3</tex> вращения на угол <tex>270^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней <tex>\Rightarrow k^3 </tex> раскрасок.
[[Файл:burnside-4.png|top]]
* <tex>3</tex> вращения на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней <tex>\Rightarrow k^4 </tex> раскрасок.
[[Файл:burnside-5.png|top]]
Итого <tex>1+(4+4)+6+(3+3)+3=24</tex> поворота, при которых куб переходит в себя. Других различных поворотов, которые переводят куб в себя, не существует, поскольку ''группа вращений'' [https://en.wikipedia.org/wiki/Octahedral_symmetry <tex>G</tex> изоморфна ''симметрической группе'' <tex>S_4</tex>], тогда из того, что <tex>|S_4|=24</tex> следует, что мы указали все преобразования, которые переводят куб в себя, причем различным образом.
Теперь с помощью Леммы Бёрнсайда найдем искомый ответ:
:<tex> |C| = \dfrac{1} {|G|} \sum\limits_{g \in G}|St(g)| = \dfrac{1} {24} (k^6 + 8k^2 + 6k^3 + 6k^3 + 3k^4) = \dfrac{1} {24} (k^6 + 3k^4 + 12k^3 + 8k^2)</tex>
==См. также==
* [[Теорема Кэли|Теорема Кэли]]* [[Задача об ожерельях|Задача об ожерельях]] ==Источники информации==* [http://neercru.ifmowikipedia.ruorg/wiki/index.php?title=%D0%979B%D0%B5%D0%BC%D0%BC%D0%B0B0_%D0%B491%D1%91%D1%80%D0%B0BD%D1%8781%D0%B0_B0%D0%BEB9%D0%B1_B4%D0%BEB0 Википедия {{---}} Лемма Бёрнсайда]*[http://ru.wikipedia.org/wiki/%D0%B6A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BBBC%D0%B0_%D0%9F%D1D0%BE%D0%B9%8CD0%D1B0 Википедия {{---}} Теорема Пойа]*[https://en.wikipedia.org/wiki/Burnside%8F27s_lemma Wikipedia {{---}} Burnside's lemma]*[https://en.wikipedia.org/wiki/P%D1C3%85 Задача об ОжерельяхB3lya_enumeration_theorem Wikipedia {{---}} Pólya enumeration theorem]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Теория групп]]
