Задача об ожерельях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм решения задачи про ожерелья)
м (rollbackEdits.php mass rollback)
 
(не показано 39 промежуточных версий 8 участников)
Строка 1: Строка 1:
{{Определение
+
{{Задача
 
|definition=
 
|definition=
 
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}
 
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}
  
  
Решение этой задачи опирается на [http://neerc.ifmo.ru/wiki/index.php?title=Лемма_Бёрнсайда_и_Теорема_Пойа Лемму Бёрнсайда и Теорему Пойа].
+
Решение этой задачи опирается на [[Лемма Бёрнсайда и Теорема Пойа|лемму Бёрнсайда и теорему Пойа]].
  
  
Строка 14: Строка 14:
  
  
<tex>C =</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{l \in G} k^{P(l)}</tex>  
+
<tex>|C| =</tex> <tex> \dfrac{1} {|G|}</tex><tex>\sum\limits_{l \in G} k^{P(l)}</tex>  
  
 
По условию, перестановкой инвариантной данной будет любая перестановка, полученная из данной циклическим сдвигом.
 
По условию, перестановкой инвариантной данной будет любая перестановка, полученная из данной циклическим сдвигом.
Очевидно, что для каждой перестановки длины <tex>n</tex> существует ровно <tex>n - 1</tex> инвариантная перестановка, то есть всего инвариантных перестановок в каждом классе <tex>n</tex>, теперь найдем <tex>P(i)</tex>. Заметим, что в <tex>i</tex>-ой перестановке на <tex>l</tex>-ой позиции стоит элемент <tex>(i + l)\bmod n</tex>. Также, заметим, что элемент <tex>a</tex> переходит в элемент <tex>a + in</tex>, где <tex>i \in [1; k]</tex>. Из этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex>lcm(n, i)/i  = n/gcd(i,n)</tex>. Откуда следует что:
+
Очевидно, что для каждой перестановки длины <tex>n</tex> существует ровно <tex>n - 1</tex> инвариантная перестановка, то есть всего инвариантных перестановок в каждом классе <tex>n</tex>, теперь найдем <tex>P(i)</tex>. Заметим, что в <tex>i</tex>-ой перестановке на <tex>l</tex>-ой позиции стоит элемент <tex>(i + l)\bmod n</tex>. Также, заметим, что элемент <tex>a</tex> переходит в элемент <tex>a + in</tex>, где <tex>i = 1, 2, \ldots k</tex>. Из этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex> \dfrac{\mathrm{lcm}(n, i)}{i} = \dfrac{n}{\mathrm{gcd}(i,n)}</tex>, где <tex>\mathrm{gcd}(i, n)</tex> {{---}} [[Наибольший общий делитель|НОД<tex>(i, n)</tex>]], <tex>\mathrm{lcm}(i, n)</tex> {{---}} [[Наименьшее общее кратное|НОК<tex>(i, n)</tex>]]. Откуда следует что:
  
<tex>C =</tex> <tex dpi = "180"> \frac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{gcd(i,n)}</tex>.
+
<tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{\mathrm{gcd}(i,n)}</tex>.
  
  
где <tex>C</tex> - кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex> различных цветов.
+
где <tex>|C|</tex> {{---}} кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex> различных цветов.
 +
 
 +
 
 +
Если раскраски ожерелья одинаковые, то они принадлежат одной [[Орбита|орбите]], т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>p</tex> минимальное число такое, что <tex>ip</tex> делится на <tex>n</tex>, и число их раскрасок <tex>N_i=k^{\operatorname{gcd}(n,i)}</tex>. Сумма же инвариантных раскрасок для всех поворотов: <tex>S=\sum\limits_{i=1}^{n}N_i=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}</tex>. В последней сумме <tex>\varphi(n)</tex> слагаемых <tex>(\varphi(n)</tex> {{---}} [[Функция Эйлера|функция Эйлера]]<tex>)</tex>, для которых <tex>\operatorname{gcd}(n,i)=1</tex>. Если же <tex>\operatorname{gcd}(n,i)=q</tex>, то <tex>\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=1</tex>. Чтобы определить количество таких <tex>i</tex>, меньших <tex>n</tex>, нужно перебрать числа вида <tex>i=lq,\,0\leqslant l\leqslant \dfrac{n}{q}</tex> и проверять их на условие <tex>1=\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=\operatorname{gcd}\left(\dfrac{n}{q},l\right)</tex>. Таких чисел, очевидно, <tex>\varphi\left(\dfrac{n}{q}\right)</tex> (по определению <tex>\varphi(n)</tex>). Поэтому сумму можно заменить: <tex>S=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.
 +
 
 +
 
 +
Тогда <tex>|C| =</tex> <tex> \dfrac{1} {n}</tex><tex>\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q</tex>.
 +
 
 +
== Алгоритм решения задачи про ожерелья с отражениями==
 +
 
 +
[[Файл:axis_of_braclets.png|300px|thumb|right|Слева пример оси для нечётного случая. Справа для чётного.]]
 +
Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси (ось может проходить через две противоположные бусинки или через две противоположные пустоты в чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются bracelets <ref>[https://en.wikipedia.org/wiki/Necklace_(combinatorics) Necklace (combinatorics)]</ref>.
 +
Будем пользоваться [[Лемма Бёрнсайда и Теорема Пойа|леммой Бёрнсайда]].
 +
Разберём два случая.
 +
 
 +
Для начала покажем, что в качестве операций требуется рассматривать только повороты и отражения.
 +
* Поворот и отражение {{---}} отражение.
 +
Занумеруем наши бусинки по часовой стрелке. Поворот и отражение не меняют порядка (в каком-то направлении бусинки занумерованы по порядку). Нетрудно понять, что отражение меняет направление обхода наших бусинок и не меняет порядка. Если мы сначала сделаем поворот, а потом отразим относительно какой-нибудь оси, то мы то самое же можем получить и обыкновенным отражением относительно какой-то оси. Такая ось найдётся, потому что всегда можно выбрать ось, что поставит первую бусинку на своё изначальное место, поменяв направление обхода (если перебирать все оси подряд, начиная с оси, проходящей через нужную нам бусинку, то изначально она останется на своём месте, потом сместится на одно место, потом на два и.т.д.). Поэтому поворот и отражение не добавляет нам новой операции.
 +
 
 +
* Отражение и поворот {{---}} отражение.
 +
Аналогичные рассуждения.
 +
 
 +
* Отражение и отражение {{---}} поворот.
 +
Тут мы дважды меняем направление обхода, но не меняем порядка. Поэтому данная операция заменяется обычным поворотом.
 +
 
 +
Пусть число бусинок нечётное, тогда мы имеем <tex>n</tex> осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначно восстановится. Таким образом количество неподвижных точек для одной оси будет <tex>k^{\frac{n + 1}{2}}</tex>.
 +
Операций в группе будет в два раза больше, чем было: <tex>2n</tex> (<tex>n</tex> сдвигов и <tex>n</tex> отражений).
 +
 
 +
По Лемме Бёрнсайда:
 +
<tex> |B| = </tex> <tex>\dfrac{1} {|G|}</tex><tex>\sum\limits_{k \in G}I(k)</tex>
 +
 
 +
<tex> |G| = 2n</tex>. Первые <tex>n</tex> операций {{---}} повороты, и сумма количества их неподвижных точек, делённая на <tex>2n</tex>, принимает значение <tex>\dfrac{|C|} {2}</tex>, где <tex>|C|</tex> - количество ожерелий из <tex>n</tex> бусинок <tex>k</tex> различных цветов без отражений (задача выше) т.к. деление в задаче без отражений происходило на <tex>n</tex>, а здесь на <tex>2n</tex>. Следующие <tex>n</tex> операций {{---}} отражения. У каждой такой операции <tex>k^{\frac{n + 1}{2}}</tex> неподвижных точек. Поэтому сумма получается <tex>k^{\frac{n + 1}{2}}n</tex>.
 +
 
 +
<tex>|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}k^{\dfrac{n + 1}{2}}n  = \dfrac{|C|}{2} + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} </tex><tex> = \dfrac{1} {2n}\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} </tex>
 +
 
 +
 
 +
Разберём теперь чётный случай.
 +
Тут мы имеем <tex>\frac{n}{2}</tex> осей, проходящих через пустоты между бусинками (ось можно провести через пустоту после каждой бусинки, но половина из них будет повторяться). В таких вот случаях можно выбрать по <tex>\frac{n}{2}</tex> бусинок и дать им произвольные цвета. Остальная половина восстановится по ним. Таким образом для данных осей количество неподвижных точек будет <tex>k^{\frac{n}{2}}</tex>.
 +
Ещё у нас есть <tex>\frac{n}{2}</tex> осей, проходящих через бусинки. В данных случаях мы можем выбрать по <tex>\frac{n}{2} + 1</tex> бусинок (бусинки на оси и все по одну какую-то сторону от неё). То есть будет <tex>k^{\frac{n}{2} + 1}</tex> неподвижных точек. Операций также <tex>2n</tex>.
 +
 
 +
По Лемме Бёрнсайда:
 +
 
 +
<tex>|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}\left(\dfrac{n}{2}k^{\frac{n}{2}} + \dfrac{n}{2}k^{\frac{n}{2} + 1}\right)</tex> <tex>= \dfrac{|C|}{2} + \dfrac{1}{4}k^{\frac{n}{2}}(k + 1) = \dfrac{1} {2n}\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q + \dfrac{1}{4}k^{\frac{n}{2}}(k+1)</tex>
  
 
== См. также ==
 
== См. также ==
* [http://neerc.ifmo.ru/wiki/index.php?title=Лемма_Бёрнсайда_и_Теорема_Пойа Лемма Бёрнсайда и Теорема Пойа]
+
* [[Лемма Бёрнсайда и Теорема Пойа]]
 +
* [[Функция Эйлера]]
 +
 
 +
== Примечания ==
 +
<references/>
 +
 
 +
== Источники информации ==
 +
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A0%D0%B5%D0%B4%D1%84%D0%B8%D0%BB%D0%B4%D0%B0_%E2%80%94_%D0%9F%D0%BE%D0%B9%D0%B0#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BA.D0.BE.D0.BB.D0.B8.D1.87.D0.B5.D1.81.D1.82.D0.B2.D0.B5_.D0.BE.D0.B6.D0.B5.D1.80.D0.B5.D0.BB.D0.B8.D0.B9 Википедия {{---}} Теорема Редфилда — Пойа, Задача о количестве ожерелий]
 +
* [http://e-maxx.ru/algo/necklace_colouring MAXimal::algo::Ожерелья]
  
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]
 +
[[Категория: Теория групп]]

Текущая версия на 19:42, 4 сентября 2022

Задача:
Требуется посчитать количество ожерелий из [math]n[/math] бусинок, каждая из которых может быть покрашена в один из [math] k [/math] цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).


Решение этой задачи опирается на лемму Бёрнсайда и теорему Пойа.


Алгоритм решения задачи про ожерелья

Пусть нам даны бусинки [math]k[/math] различных цветов, а ожерелье должно состоять из [math]n[/math] бусинок.

Для решения воспользуемся формулой из теоремы Пойа.


[math]|C| =[/math] [math] \dfrac{1} {|G|}[/math][math]\sum\limits_{l \in G} k^{P(l)}[/math]

По условию, перестановкой инвариантной данной будет любая перестановка, полученная из данной циклическим сдвигом. Очевидно, что для каждой перестановки длины [math]n[/math] существует ровно [math]n - 1[/math] инвариантная перестановка, то есть всего инвариантных перестановок в каждом классе [math]n[/math], теперь найдем [math]P(i)[/math]. Заметим, что в [math]i[/math]-ой перестановке на [math]l[/math]-ой позиции стоит элемент [math](i + l)\bmod n[/math]. Также, заметим, что элемент [math]a[/math] переходит в элемент [math]a + in[/math], где [math]i = 1, 2, \ldots k[/math]. Из этого следует, что длина цикла для [math]i[/math]-ой перестановки равна [math] \dfrac{\mathrm{lcm}(n, i)}{i} = \dfrac{n}{\mathrm{gcd}(i,n)}[/math], где [math]\mathrm{gcd}(i, n)[/math]НОД[math](i, n)[/math], [math]\mathrm{lcm}(i, n)[/math]НОК[math](i, n)[/math]. Откуда следует что:

[math]|C| =[/math] [math] \dfrac{1} {n}[/math][math]\sum\limits_{i = 1}^{n} k^{\mathrm{gcd}(i,n)}[/math].


где [math]|C|[/math] — кол-во различных ожерелий,которые можно составить из [math]n[/math] бусинок [math]k[/math] различных цветов.


Если раскраски ожерелья одинаковые, то они принадлежат одной орбите, т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их [math]n[/math] штук. Тогда, по лемме Бёрнсайда, число орбит равняется [math]\dfrac{n}{p}=\operatorname{gcd}(n,i)[/math], где [math]p[/math] минимальное число такое, что [math]ip[/math] делится на [math]n[/math], и число их раскрасок [math]N_i=k^{\operatorname{gcd}(n,i)}[/math]. Сумма же инвариантных раскрасок для всех поворотов: [math]S=\sum\limits_{i=1}^{n}N_i=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}[/math]. В последней сумме [math]\varphi(n)[/math] слагаемых [math](\varphi(n)[/math]функция Эйлера[math])[/math], для которых [math]\operatorname{gcd}(n,i)=1[/math]. Если же [math]\operatorname{gcd}(n,i)=q[/math], то [math]\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=1[/math]. Чтобы определить количество таких [math]i[/math], меньших [math]n[/math], нужно перебрать числа вида [math]i=lq,\,0\leqslant l\leqslant \dfrac{n}{q}[/math] и проверять их на условие [math]1=\operatorname{gcd}\left(\dfrac{n}{q},\dfrac{i}{q}\right)=\operatorname{gcd}\left(\dfrac{n}{q},l\right)[/math]. Таких чисел, очевидно, [math]\varphi\left(\dfrac{n}{q}\right)[/math] (по определению [math]\varphi(n)[/math]). Поэтому сумму можно заменить: [math]S=\sum\limits_{i=1}^{n}k^{\operatorname{gcd}(n,i)}=\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q[/math].


Тогда [math]|C| =[/math] [math] \dfrac{1} {n}[/math][math]\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q[/math].

Алгоритм решения задачи про ожерелья с отражениями

Слева пример оси для нечётного случая. Справа для чётного.

Пусть теперь ожерелья считаются одинаковыми, если они не только переходят друг в друга поворотом, но и отражением относительно некоторой оси (ось может проходить через две противоположные бусинки или через две противоположные пустоты в чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются bracelets [1]. Будем пользоваться леммой Бёрнсайда. Разберём два случая.

Для начала покажем, что в качестве операций требуется рассматривать только повороты и отражения.

  • Поворот и отражение — отражение.

Занумеруем наши бусинки по часовой стрелке. Поворот и отражение не меняют порядка (в каком-то направлении бусинки занумерованы по порядку). Нетрудно понять, что отражение меняет направление обхода наших бусинок и не меняет порядка. Если мы сначала сделаем поворот, а потом отразим относительно какой-нибудь оси, то мы то самое же можем получить и обыкновенным отражением относительно какой-то оси. Такая ось найдётся, потому что всегда можно выбрать ось, что поставит первую бусинку на своё изначальное место, поменяв направление обхода (если перебирать все оси подряд, начиная с оси, проходящей через нужную нам бусинку, то изначально она останется на своём месте, потом сместится на одно место, потом на два и.т.д.). Поэтому поворот и отражение не добавляет нам новой операции.

  • Отражение и поворот — отражение.

Аналогичные рассуждения.

  • Отражение и отражение — поворот.

Тут мы дважды меняем направление обхода, но не меняем порядка. Поэтому данная операция заменяется обычным поворотом.

Пусть число бусинок нечётное, тогда мы имеем [math]n[/math] осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначно восстановится. Таким образом количество неподвижных точек для одной оси будет [math]k^{\frac{n + 1}{2}}[/math]. Операций в группе будет в два раза больше, чем было: [math]2n[/math] ([math]n[/math] сдвигов и [math]n[/math] отражений).

По Лемме Бёрнсайда: [math] |B| = [/math] [math]\dfrac{1} {|G|}[/math][math]\sum\limits_{k \in G}I(k)[/math]

[math] |G| = 2n[/math]. Первые [math]n[/math] операций — повороты, и сумма количества их неподвижных точек, делённая на [math]2n[/math], принимает значение [math]\dfrac{|C|} {2}[/math], где [math]|C|[/math] - количество ожерелий из [math]n[/math] бусинок [math]k[/math] различных цветов без отражений (задача выше) т.к. деление в задаче без отражений происходило на [math]n[/math], а здесь на [math]2n[/math]. Следующие [math]n[/math] операций — отражения. У каждой такой операции [math]k^{\frac{n + 1}{2}}[/math] неподвижных точек. Поэтому сумма получается [math]k^{\frac{n + 1}{2}}n[/math].

[math]|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}k^{\dfrac{n + 1}{2}}n = \dfrac{|C|}{2} + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} [/math][math] = \dfrac{1} {2n}\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q + \dfrac{1}{2}k^{\dfrac{n + 1}{2}} [/math]


Разберём теперь чётный случай. Тут мы имеем [math]\frac{n}{2}[/math] осей, проходящих через пустоты между бусинками (ось можно провести через пустоту после каждой бусинки, но половина из них будет повторяться). В таких вот случаях можно выбрать по [math]\frac{n}{2}[/math] бусинок и дать им произвольные цвета. Остальная половина восстановится по ним. Таким образом для данных осей количество неподвижных точек будет [math]k^{\frac{n}{2}}[/math]. Ещё у нас есть [math]\frac{n}{2}[/math] осей, проходящих через бусинки. В данных случаях мы можем выбрать по [math]\frac{n}{2} + 1[/math] бусинок (бусинки на оси и все по одну какую-то сторону от неё). То есть будет [math]k^{\frac{n}{2} + 1}[/math] неподвижных точек. Операций также [math]2n[/math].

По Лемме Бёрнсайда:

[math]|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}\left(\dfrac{n}{2}k^{\frac{n}{2}} + \dfrac{n}{2}k^{\frac{n}{2} + 1}\right)[/math] [math]= \dfrac{|C|}{2} + \dfrac{1}{4}k^{\frac{n}{2}}(k + 1) = \dfrac{1} {2n}\sum\limits_{q|n}\varphi\left(\dfrac{n}{q}\right)k^q + \dfrac{1}{4}k^{\frac{n}{2}}(k+1)[/math]

См. также

Примечания

Источники информации