|
|
| (не показаны 4 промежуточные версии 2 участников) |
| Строка 1: |
Строка 1: |
| − | {{Требует доработки
| + | #перенаправление [[Лемма Бёрнсайда и Теорема Пойа]] |
| − | |item1=(исправлено)Надо решить задачу о числе ожерелий!
| |
| − | }}
| |
| − | | |
| − | == Постановка задачи ==
| |
| − | Пусть [[группа]] <tex>G</tex> [[Действие группы на множестве|действует]] на множестве <tex>X</tex>. По свойствам орбит множество <tex>X</tex> разбивается на непересекающиеся орбиты. Требуется найти их количество.
| |
| − | | |
| − | {{Лемма
| |
| − | |id=l1
| |
| − | |about=Бернсайда
| |
| − | |statement=
| |
| − | Число [[орбита|орбит]] в группе <tex>G</tex> равно <tex>\frac { \sum_{g \in G} |Fix(g)| } { |G| } </tex>
| |
| − | }}
| |
| − | {{Утверждение
| |
| − | |id=s1
| |
| − | |about=1
| |
| − | |statement=
| |
| − | <tex> |Orb(x)| = \frac { |G| } { |St(x)| } </tex>
| |
| − | |proof=
| |
| − | Фиксируем точку x. Рассмотрим отображение <tex>\phi:G\rightarrow X</tex>, сопоставляющее элементу <tex>g\in G</tex> точку <tex>gx</tex>. Тогда верно следующее утверждение: <tex>\phi(g_1)=\phi(g_2)</tex> тогда и только тогда, когда <tex>g_1</tex> и <tex>g_2</tex> лежат в одном смежном классе <tex>G</tex> по <tex>St(x)</tex>. Действительно, <tex>g_1 x=g_2 x \Leftrightarrow {g_1}^{-1}g_2 x=x\Leftrightarrow {g_1}^{-1}g_2\in St(x)\Leftrightarrow g_2\in g_1 St(x)</tex>. Таким образом, образ каждого смежного класса - одна точка, причем разным смежным классам соответствуют разные точки. Поэтому мощность образа(который и представляет собой орбиту) равна числу смежных классов, т.е. <tex>|Orb(x)|=\frac{|G|}{|St(x)|}</tex>.
| |
| − | }}
| |
| − | | |
| − | Преобразуем выражение для числа орбит, полученное из леммы Бернсайда. <br>
| |
| − | <tex>\frac { \sum_{g \in G} |Fix(g)| } { |G| } = \frac { \sum_{ g \in G } \sum_{ x \in X } \{gx = x\} } { |G| } = \frac { \sum_{ x \in X } \sum_{ g \in G } \{gx = x\} } { |G| }
| |
| − | = \frac { \sum_{ x \in X } |St(x)| } { |G| } = \sum_{ x \in X } \frac {1} { |Orb(x)| } </tex> <br>
| |
| − | Последнее преобразование выполнено на основании утверждения 1.
| |
| − | | |
| − | === Задача о числе ожерелий ===
| |
| − | Пусть есть <tex>n</tex> бусинок <tex>m</tex> разных сортов, <tex>n_i</tex> назовем количество бусинок <tex>i</tex>ого цвета<tex>(i \in [1;m])</tex> (так же для удобства будем называть <tex>n_i</tex> цвет, цвет которому соответствует данное число бусин). Найти число ожерелий которые можно составить из этих бусинок. Ожерелья полученные поворотом друг из друга поворотом или отражением считаются одним ожерельем.
| |
| − | | |
| − | ===='''решение:'''====
| |
| − | | |
| − | Эта задача равносильна следующей задаче: сколькими различными способами можно раскрасить вершины правильного <tex>n</tex>угольника вершины которого окрашены в цветов, а количество вершин каждого цвета равно <tex>n_i</tex>. Две расскраски считаются разными, если из одной нельзя получить другую с помощью симметрии или вращения.
| |
| − | | |
| − | Пусть <tex>M</tex> — множество всех возможных окрасок <tex>n</tex>угольника, <tex>D</tex> — группа симметрий <tex>n</tex>угольника, состоящая из <tex>2n</tex> преобразований. Группа <tex>G</tex> определяет группу перестановок на множестве <tex>M</tex>. Пусть <tex> d \in D</tex> — некое преобразование симметрии <tex> \Rightarrow </tex> для любого многоугольник <tex>x \in M</tex> можно сопоставить многоугольник получаемый из него симметрией <tex>d</tex>. Назовем сопоставление этой перестановки <tex>d'</tex>. Группу всех таких перестановок из <tex>D</tex> назовем <tex>D'</tex>.
| |
| − | | |
| − | Два многоугольника будут считаться разными, если из одного невозможно получить другой какой-либо перестановкой <tex>d' \in D'</tex> (они содержаться на разных орбитах группы <tex>D'</tex> действующей на множестве <tex>M</tex>). Поэтому для получения количества различных раскрасок вершин <tex>n</tex>угольника достаточно найти количество орбит группы <tex>D'</tex> на множестве <tex>M</tex>. По лемме Бернсайда, для этого нужно посчитать число неподвижных точек каждой перестановки <tex> d' \in D'</tex>.
| |
| − | | |
| − | | |
| − | '''Рассмотрим повороты:'''
| |
| − | | |
| − | пусть <tex>k</tex> — общий делитель <tex>n_i</tex>ых<tex>(i \in [1..m]) \Rightarrow</tex> поворот <tex>a_1</tex> на угол <tex>\frac { 2\pi } { k }</tex> оставит неподвижными ожерелья из <tex>k</tex> одинаковых кусков длинны <tex>\frac {n} {k}</tex>. Каждый кусок состоит из <tex>\frac {n_i} { k } </tex> бусен <tex>i</tex>ого цвета, поэтому число неподвижных точек для поворота будет равно количеству способов расставить бусины на <tex>\frac {n} {k}</tex> местах. Соответственно для перестановки <tex>d'</tex> число неподвижных точек будет равно <tex>t(d')=P(\frac {n_1} { k }, \frac {n_2} { k }, ..., \frac {n_m} { k })</tex>, где <tex>P(x_1, x_2, ..., x_m)</tex> — полиномиальные коэффициенты.
| |
| − | | |
| − | рассмотрим поворот <tex> a_i</tex> на угол <tex>\frac {2i\pi} {k}</tex>, где <tex> i \in [1..k]</tex>. Количество его неподвижных точек равно количеству неподвижных точек <tex>a_1</tex>, если <tex> i</tex> взаимно просто с <tex>k</tex>. Количество взаимно простых с <tex>k</tex>(не превосходящих <tex>k</tex>) — является функцией Эйлера <tex>\phi(k)</tex>. Пусть <tex>S</tex> — сумма по всем поворотам, тогда <tex>S= \sum_{k} \phi(k) \cdot P(\frac {n_1} { k }, \frac {n_2} { k }, ..., \frac {n_m} { k })</tex>, где k пробегает множество общих делителей <tex>n_1, n_2, ..., n_m</tex>.
| |
| − | | |
| − | | |
| − | '''рассмотрим симметрии относительно осей:'''
| |
| − | | |
| − | ''1 случай:''
| |
| − | | |
| − | <tex>n</tex> — нечетно. Тогда симметричные ожерелья существуют только если среди <tex>n_i/,(i \in [1..m])</tex> только одно число нечетное. Пусть <tex>n_1</tex> — нечетно, <tex>d</tex> — симметрия относительно оси, проходящей через некоторую вершину. Тогда неподвижными будут ожерелья, симметричные относительно оси проходящей через бусину цвета <tex>n_1</tex>. По одной стороне от оси будут находится <tex> \frac {n-1} { 2 } </tex> бусин: <tex> \frac {n_1-1} { 2 } </tex> бусин <tex>n_1 цвета, <tex> \frac {n_i} { 2 } </tex> бусин <tex>n_i</tex> цвета, где <tex>i \in [2.. m] \Rightarrow t(d')=P(\frac {n_1-1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })=P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }]),</tex> где <tex>[x]</tex> — целая часть числа <tex>x</tex>. Тогда такое же число неподвижных точек имеет каждая из <tex>n</tex> соответствующая таким симметриям. Пусть <tex>S'</tex> — сумма числа всех неподвижных точек <tex>t(d')</tex> по всем отражениям: <tex>S'=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.
| |
| − | | |
| − | | |
| − | ''2 случай:''
| |
| − | | |
| − | <tex>n</tex> — четно. Ожерелья, симметричные относительно оси проходящей между бусинами, существуют только если все <tex>n_i (i \in [1..m])</tex> четные. Если ось проходит через <tex>2</tex> бусины, то симметричные ожерелья существуют только если все <tex>n_i (i \in [1..m])</tex> четные '''или''' если только <tex>2</tex> из <tex>n_i (i \in [1..m])</tex> не четные. Рассмотрим оба случая:
| |
| − | | |
| − | ''a)Пусть'' <tex>n_1, n_2</tex> ''— не четные'', <tex>n_i (i \in [3..m])</tex> — четные, <tex>d</tex> — симметрия относительно некой оси, проходящей через противоположные вершины. Тогда неподвижными точками для <tex>d'</tex> будут ожерелья, симметричные относительно оси, проходящей через вершины <tex>n_1</tex> и <tex>n_2</tex> сортов. По одну сторону находятся от оси находятся <tex>\frac {n-2} { 2 }</tex> бусин, где <tex>\frac {n_1-1} { 2 },</tex> бусин <tex>n_1</tex> цвета, <tex>\frac {n_2-1} { 2 },</tex> бусин <tex>n_2</tex> цвета <tex>\frac {n_i} { 2 },</tex> бусин <tex>[3..m]</tex> цвета. Бусины <tex>n_1</tex> и <tex>n_2</tex> цвета можно поменять местами <tex>\Rightarrow</tex> количество неподвижных точек <tex>t(d')=2P(\frac {n_1-1} { 2 }, \frac {n_2-1} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий <tex>\frac {n} {2} \Rightarrow S'=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.
| |
| − | | |
| − | ''б)Пусть все'' <tex>n_i</tex> — ''четные''. Если <tex>d</tex> — симметрия относительно оси проходящей через 2 вершины, то неподвижными точками для <tex>d'</tex> будут симметричные ожерелья, у которых <tex>2</tex> бусины <tex>n_i (i \in [1..m])</tex> цвета расположены на данной оси. Их количество <tex>t(d')=P(\frac {n_1-2} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })+P(\frac {n_1} { 2 }, \frac {n_2-2} { 2 }, \frac {n_3} { 2 }, ..., \frac {n_m} { 2 })</tex><tex>+ ...+</tex><tex>P(\frac {n_1} { 2 }, ..., \frac {n_{m-1}} { 2 }, ..., \frac {n_m-2} { 2 })=P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий <tex> \frac {m} {2}</tex>. Если <tex>d</tex> — симметрия относительно оси, проходящей между бусинами, то количество неподвижных точек равно <tex>t(d')=P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })</tex>. Таких симметрий также <tex> \frac {m} {2}</tex>. Поэтому <tex>S'=m \cdot P(\frac {n_1} { 2 }, \frac {n_2} { 2 }, ..., \frac {n_m} { 2 })=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])</tex>.
| |
| − | | |
| − | | |
| − | '''Итак:'''
| |
| − | | |
| − | Во всех случаях получились одинаковые формулы для сумм неподвижных точек по всем отражениям<tex>(S')</tex>. По лемме Бернсайда <tex>t(D')= \frac {1} {2n} \cdot (S+S')= \frac {1} {2m} \cdot \sum_{k} \phi(k) \cdot P(\frac {n_1} { k }, \frac {n_2} { k }, ..., \frac {n_m} { k })+ \frac {1} {2} \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }]) </tex>. Это и будет количеством ожерелий. Если среди всех <tex>n_i (i \in [1..m])</tex> более 2 нечетных, то нет симметрий <tex>\Rightarrow S'=0, \, t(D')= \frac {1} {2m} \cdot \sum_{k} \phi(k) \cdot P(\frac {n_1} { k }, \frac {n_2} { k }, ..., \frac {n_m} { k })</tex>.
| |
| − | | |
| − | | |
| − | [[Категория:Теория групп]]
| |
