Лемма Бёрнсайда и Теорема Пойа - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:31:24Z

rollbackEdits.php mass rollback

185.100.85.24 в 04:27, 1 сентября 2022

2022-09-01T04:27:53Z

176.59.54.3: /* Лемма Бёрнсайда */ Добавлено пропущенное равно

2021-10-13T05:31:14Z

‎Лемма Бёрнсайда: Добавлено пропущенное равно

176.59.11.230: /* Задача о числе раскрасок граней куба */

2019-12-25T20:32:44Z

‎Задача о числе раскрасок граней куба

Mishenkoil: Добавлены изображения для вращений и разверток куба.

2019-12-23T15:34:13Z

Добавлены изображения для вращений и разверток куба.

Mishenkoil: Исправлена опечатка

2019-12-17T12:13:08Z

Исправлена опечатка

Mishenkoil: Добавлен пример задачи про раскраски граней куба

2019-12-14T21:20:41Z

Добавлен пример задачи про раскраски граней куба

94.25.229.251: Ошибка в задаче про раскраску прямоугольниас

2019-12-06T12:09:46Z

Ошибка в задаче про раскраску прямоугольниас

I am dark black: /* См. также */

2018-03-13T15:57:40Z

‎См. также

Lapenok.aleksej в 15:08, 7 февраля 2018

2018-02-07T15:08:12Z

← Предыдущая		Версия 16:31, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.		Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.
	Если это отношение является отношением "с точностью до [[Действие группы на множестве\|действия элементом группы]]", то такой подсчет можно провести		Если это отношение является отношением "с точностью до [[Действие группы на множестве\|действия элементом группы]]", то такой подсчет можно провести

← Предыдущая		Версия 04:27, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.		Иногда требуется провести подсчет комбинаторных объектов с точностью до некоторого отношения эквивалетности.
	Если это отношение является отношением "с точностью до [[Действие группы на множестве\|действия элементом группы]]", то такой подсчет можно провести		Если это отношение является отношением "с точностью до [[Действие группы на множестве\|действия элементом группы]]", то такой подсчет можно провести

@@ Строка 37: / Строка 37: @@
 <math>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</math><math> \dfrac{1}{|P|}</math>
-Заметим, что <math>\sum\limits_{x\in P} \dfrac{1}{|P|} \dfrac{1}{|P|}\sum\limits_{1}^{|P|}{1} = 1.</math> Следовательно:
+Заметим, что <math>\sum\limits_{x\in P} \dfrac{1}{|P|} = \dfrac{1}{|P|}\sum\limits_{1}^{|P|}{1} = 1.</math> Следовательно:
 <math>|G|\sum\limits_{P\in C}\sum\limits_{x\in P} \dfrac{1}{|P|} = |G|\sum\limits_{P\in C} 1</math>.

@@ Строка 117: / Строка 117: @@
 [[Файл: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>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>
 ==См. также==

@@ Строка 103: / Строка 103: @@
 Рассмотрим группу вращений куба <tex>G</tex>:
-Итого <tex>1+(4+4)+6+(3+3)+3=24</tex> поворота, при которых куб переходит в себя. Других различных поворотов, которые переводят куб в себя не существует, поскольку ''группа вращений'' <tex>G</tex> изоморфна ''симметрической группе'' <tex>S_4</tex> ''(без доказательства)'', тогда из того, что <tex>|S_4|=24</tex> следует, что мы указали все преобразования, которые переводят куб в себя, причем различным образом.
+''Последующие изображения с развертками будут подразумевать такое же соответствие вершин, как на рисунке ниже. На развертках будем показывать раскраски, а на самом кубе ребро, через которое мы будем вращать его.  Цвета на развертке лишь показывают то, что грани с одинаковым цветом должны быть одинаково раскрашены.''
-Давайте введем обозначения для наших вращений, в том же порядке, в котором они были указаны: <tex> \{ e , \alpha , \beta , \gamma , \xi \} </tex>, тогда с помощью Леммы Бёрнсайда найдем искомый ответ:
+Итого <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> следует, что мы указали все преобразования, которые переводят куб в себя, причем различным образом.
 ==См. также==

@@ Строка 104: / Строка 104: @@
 Рассмотрим группу вращений куба <tex>G</tex>:
 * <tex>1</tex> Тождественное вращение.
-* <tex>4</tex> вращения на угол <tex>120^{\circ}</tex> и <tex>4</tex> вращения на угол <tex>120^{\circ}</tex> вдоль главных диагоналей куба, имеющих по <tex>2</tex> орбиты на гранях (<tex>k^2</tex> орбит на раскрасках соответственно).
+* <tex>4</tex> вращения на угол <tex>120^{\circ}</tex> и <tex>4</tex> вращения на угол <tex>240^{\circ}</tex> вдоль главных диагоналей куба, имеющих по <tex>2</tex> орбиты на гранях (<tex>k^2</tex> орбит на раскрасках соответственно).
 * <tex>6</tex> вращений на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих середины противоположных ребер, имеющих по <tex>3</tex> орбиты на гранях (<tex>k^3</tex> орбит на раскрасках соответственно).
 * <tex>3</tex> вращения на угол <tex>90^{\circ}</tex> и <tex>3</tex> вращения на угол <tex>270^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней, имеющих по <tex>3</tex> орбиты на гранях (<tex>k^3</tex> орбит на раскрасках соответственно).

← Предыдущая		Версия 21:20, 14 декабря 2019
Строка 93:		Строка 93:

	:<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>		:<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>:
		+	* <tex>1</tex> Тождественное вращение.
		+	* <tex>4</tex> вращения на угол <tex>120^{\circ}</tex> и <tex>4</tex> вращения на угол <tex>120^{\circ}</tex> вдоль главных диагоналей куба, имеющих по <tex>2</tex> орбиты на гранях (<tex>k^2</tex> орбит на раскрасках соответственно).
		+	* <tex>6</tex> вращений на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих середины противоположных ребер, имеющих по <tex>3</tex> орбиты на гранях (<tex>k^3</tex> орбит на раскрасках соответственно).
		+	* <tex>3</tex> вращения на угол <tex>90^{\circ}</tex> и <tex>3</tex> вращения на угол <tex>270^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней, имеющих по <tex>3</tex> орбиты на гранях (<tex>k^3</tex> орбит на раскрасках соответственно).
		+	* <tex>3</tex> вращения на угол <tex>180^{\circ}</tex> вдоль осей, соединяющих центры противоположных граней, имеющих по <tex>4</tex> орбиты на гранях (<tex>k^4</tex> орбит на раскрасках соответственно).
		+
		+	Итого <tex>1+(4+4)+6+(3+3)+3=24</tex> поворота, при которых куб переходит в себя. Других различных поворотов, которые переводят куб в себя не существует, поскольку ''группа вращений'' <tex>G</tex> изоморфна ''симметрической группе'' <tex>S_4</tex> ''(без доказательства)'', тогда из того, что <tex>\|S_4\|=24</tex> следует, что мы указали все преобразования, которые переводят куб в себя, причем различным образом.
		+
		+	Давайте введем обозначения для наших вращений, в том же порядке, в котором они были указаны: <tex> \{ e , \alpha , \beta , \gamma , \xi \} </tex>, тогда с помощью Леммы Бёрнсайда найдем искомый ответ:
		+
		+	:<tex> \|C\| = \dfrac{1} {\|G\|} \sum\limits_{g \in G}\|St(g)\| = \dfrac{1} {\|G\|} (\|St(e)\| + \|St( \alpha )\| + \|St( \beta )\| + \|St( \gamma )\| + \|St( \xi )\|) =</tex>
		+	:<tex> \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>

	==См. также==		==См. также==

@@ Строка 88: / Строка 88: @@
 Данное множество фактов объясняется тем, что мы можем как бы "слить" вместе два столбика (и\или) столбца, при этом с точностью до нужного действия количество раскрасок не уменьшится.
-Количество неподвижных точек в случае с действием <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>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{n}{2}} \rceil}{\lceil \dfrac{m}{2} \rceil}}}{4}</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>
 ==См. также==

@@ Строка 96: / Строка 96: @@
 ==См. также==
 * [[Теорема Кэли|Теорема Кэли]]
-* [[Задача об ожерельях|Задача об Ожерельях]]
+* [[Задача об ожерельях|Задача об ожерельях]]
 ==Источники информации==