Текущая версия |
Ваш текст |
Строка 37: |
Строка 37: |
| <math>= |G|\sum\limits_{P\in C}\sum\limits_{x\in P}</math><math> \dfrac{1}{|P|}</math> | | <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>. | | <math>|G|\sum\limits_{P\in C}\sum\limits_{x\in P} \dfrac{1}{|P|} = |G|\sum\limits_{P\in C} 1</math>. |
Строка 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>:
| |
− |
| |
− | ''Последующие изображения с развертками будут подразумевать такое же соответствие вершин, как на рисунке ниже. На развертках будем показывать раскраски, а на самом кубе ребро, через которое мы будем вращать его. Цвета на развертке лишь показывают то, что грани с одинаковым цветом должны быть одинаково раскрашены.''
| |
− | [[Файл: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>
| |
| | | |
| ==См. также== | | ==См. также== |