Лемма Бернсайда, задача о числе ожерелий — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 28: Строка 28:
 
Эта задача равносильна следующей задаче: сколькими различными способами можно раскрасить вершины правильного <tex>n</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> g \in D</tex> — некое преобразование симметрии <tex> \Rightarrow </tex> для любого многоугольник <tex>x \in M</tex> можно сопоставить многоугольник получаемый из него симметрией <tex>g</tex>. Назовем сопоставление этой перестановки <tex>g'</tex>. Группу всех таких перестановок из <tex>D</tex> назовем <tex>D'</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>d' \in D'</tex> (они содержаться на разных орбитах группы <tex>D'</tex> действующей на множестве <tex>M</tex>). Поэтому для получения количества различных раскрасок вершин  <tex>n</tex>угольника достаточно найти количество орбит группы <tex>D'</tex> на множестве <tex>M</tex>. По лемме Бернсайда, для этого нужно посчитать число неподвижных точек каждой перестановки <tex> d' \in D'</tex>.  
Строка 37: Строка 37:
 
пусть <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>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>.
+
рассмотрим поворот <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>.  
 
 
  
 
'''рассмотрим симметрии относительно осей:'''
 
'''рассмотрим симметрии относительно осей:'''
Строка 44: Строка 43:
 
''1 случай:''
 
''1 случай:''
  
<tex>n</tex> — нечетно.
+
<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 случай:''
 
''2 случай:''

Версия 22:14, 9 августа 2010

Эта статья требует доработки!
  1. Надо решить задачу о числе ожерелий!

Если Вы исправили некоторые из указанных выше замечаний, просьба дописать в начало соответствующего пункта (Исправлено).

Лемма (Бернсайда):
Число орбит [math] = \frac { \sum_{g \in G} |Fix(g)| } { |G| } [/math]
Утверждение (1):
[math] |Orb(x)| = \frac { |G| } { |St(x) } [/math]

Преобразуем выражение для числа орбит, полученное из леммы Бернсайда.
[math]\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)| } [/math]
Последнее преобразование выполнено на основании утверждения 1.

Задача о числе ожерелий

Пусть есть [math]n[/math] бусинок [math]m[/math] разных сортов, [math]n_i[/math] назовем количество бусинок [math]i[/math]ого цвета[math](i \in [1;m])[/math]. Найти число ожерелий которые можно составить из этих бусинок. Ожерелья полученные поворотом друг из друга поворотом или отражением считаются одним ожерельем.

решение:

Эта задача равносильна следующей задаче: сколькими различными способами можно раскрасить вершины правильного [math]n[/math]угольника вершины которого окрашены в цветов, а количество вершин каждого цвета равно [math]n_i[/math]. Две расскраски считаются разными, если из одной нельзя получить другую с помощью симметрии или вращения.

Пусть [math]M[/math] — множество всех возможных окрасок [math]n[/math]угольника, [math]D[/math] — группа симметрий [math]n[/math]угольника, состоящая из [math]2n[/math] преобразований. Группа [math]G[/math] определяет группу перестановок на множестве [math]M[/math]. Пусть [math] d \in D[/math] — некое преобразование симметрии [math] \Rightarrow [/math] для любого многоугольник [math]x \in M[/math] можно сопоставить многоугольник получаемый из него симметрией [math]d[/math]. Назовем сопоставление этой перестановки [math]d'[/math]. Группу всех таких перестановок из [math]D[/math] назовем [math]D'[/math].

Два многоугольника будут считаться разными, если из одного невозможно получить другой какой-либо перестановкой [math]d' \in D'[/math] (они содержаться на разных орбитах группы [math]D'[/math] действующей на множестве [math]M[/math]). Поэтому для получения количества различных раскрасок вершин [math]n[/math]угольника достаточно найти количество орбит группы [math]D'[/math] на множестве [math]M[/math]. По лемме Бернсайда, для этого нужно посчитать число неподвижных точек каждой перестановки [math] d' \in D'[/math].


Рассмотрим повороты:

пусть [math]k[/math] — общий делитель [math]n_i[/math]ых[math](i \in [1..m]) \Rightarrow[/math] поворот [math]a_1[/math] на угол [math]\frac { 2\pi } { k }[/math] оставит неподвижными ожерелья из [math]k[/math] одинаковых кусков длинны [math]\frac {n} {k}[/math]. Каждый кусок состоит из [math]\frac {n_i} { k } [/math] бусен [math]i[/math]ого цвета, поэтому число неподвижных точек для поворота будет равно количеству способов расставить бусины на [math]\frac {n} {k}[/math] местах. Соответственно для перестановки [math]d'[/math] число неподвижных точек будет равно [math]t(d')=P(\frac {n_1} { k }, \frac {n_2} { k }, ..., \frac {n_m} { k })[/math], где [math]P(x_1, x_2, ..., x_m)[/math] — полиномиальные коэффициенты.

рассмотрим поворот [math] a_i[/math] на угол [math]\frac {2i\pi} {k}[/math], где [math] i \in [1..k][/math]. Количество его неподвижных точек равно количеству неподвижных точек [math]a_1[/math], если [math] i[/math] взаимно просто с [math]k[/math]. Количество взаимно простых с [math]k[/math](не превосходящих [math]k[/math]) — является функцией Эйлера [math]\phi(k)[/math]. Пусть [math]S[/math] — сумма по всем поворотам, тогда [math]S= \sum_{k} \phi(k) \cdot P(\frac {n_1} { k }, \frac {n_2} { k }, ..., \frac {n_m} { k })[/math], где k пробегает множество общих делителей [math]n_1, n_2, ..., n_m[/math].

рассмотрим симметрии относительно осей:

1 случай:

[math]n[/math] — нечетно. Тогда симметричные ожерелья существуют только если среди [math]n_i/,(i \in [1..m])[/math] только одно число нечетное. Пусть [math]n_1[/math] — нечетно, [math]d[/math] — симметрия относительно оси, проходящей через некоторую вершину. Тогда неподвижными будут ожерелья, симметричные относительно оси проходящей через бусину цвета [math]n_1[/math]. По одной стороне от оси будут находится [math] \frac {n-1} { 2 } [/math] бусин: [math] \frac {n_1-1} { 2 } [/math] бусин [math]n_1 цвета, \lt tex\gt \frac {n_i} { 2 } [/math] бусин [math]n_i[/math] цвета, где [math]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 }]),[/math] где [math][x][/math] — целая часть числа [math]x[/math]. Тогда такое же число неподвижных точек имеет каждая из [math]n[/math] соответствующая таким симметриям. Пусть [math]S'[/math] — сумма числа всех неподвижных точек [math]t(d')[/math] по всем отражениям: [math]S'=m \cdot P([\frac {n_1} { 2 }], [\frac {n_2} { 2 }], ..., [\frac {n_m} { 2 }])[/math].


2 случай:

[math]n[/math] — четно.