Изменения

Перейти к: навигация, поиск

Задача об ожерельях

3157 байт добавлено, 23:55, 7 января 2016
→‎Алгоритм решения задачи про ожерелья
{{ОпределениеЗадача
|definition=
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}
Решение этой задачи опирается на [[Лемма Бёрнсайда и Теорема Пойа|лемму Бернсайда Бёрнсайда и теорему Пойа]].
{{Определение== Алгоритм решения задачи про ожерелья ==|definition='''Инвариантная перестановка''' {{---}} такая перестановка, которая по условию задачи не меняет сам объектПусть нам даны бусинки <tex>k</tex> различных цветов, а только его представлениеожерелье должно состоять из <tex>n</tex> бусинок.}}Примером инвариантной перестановки в нашем случае является циклический сдвигДля решения воспользуемся формулой из теоремы Пойа.
{{Определение
|definition=
'''Неподвижной точкой''' <tex>f</tex> для перестановки называется такой элемент, который инвариантен относительно этой перестановки.
}}
== Лемма Бернсайда ==
<tex>|C| =</tex> <tex> \dfrac{1} {Лемма|id=lemmaBerns. G|author=Бернсайд|statement=Количество комбинаторных объектов равно сумме количеств неподвижных точек по всем перестановкам из группы }</tex><tex>\sum\limits_{l \in G} k^{P(l)}</tex> , делённой на размер этой группы:
По условию, перестановкой инвариантной данной будет любая перестановка, полученная из данной циклическим сдвигом.Очевидно, что для каждой перестановки длины <tex> C = n</tex> существует ровно <tex dpi = "180">\frac{n - 1} {|G|}</tex>инвариантная перестановка, то есть всего инвариантных перестановок в каждом классе <tex>n</tex>, теперь найдем <tex>\sum\limits_{k \in G}IP(ki)</tex>. Где Заметим, что в <tex>i</tex>-ой перестановке на <tex>l</tex>-ой позиции стоит элемент <tex>I(ki + l)\bmod n</tex> {{---}} количество неподвижных точек для перестановки . Также, заметим, что элемент <tex>a</tex> переходит в элемент <tex>a + in</tex>, где <tex>i = 1, 2, \ldots k</tex>.|proof=Рассмотрим сумму в числителе дроби справа:Из этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex>\sumdfrac{\limits_mathrm{k lcm}(n, i)}{i} = \dfrac{n}{\mathrm{gcd}(i,n)}</tex>, где <tex>\in Gmathrm{gcd}I(ki, n)</tex> {{---}} это ничто иное как количество "инвариантных пар". Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества [[Наибольший общий делитель|НОД<tex>f(i, n)</tex>]], а внутри нее поставить величину <tex>J\mathrm{lcm}(fi, n)</tex> {{---}} количество перестановок, относительно которых объект [[Наименьшее общее кратное|НОК<tex>f(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 dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>
где <tex>|C|</tex> {{---}} кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex> различных цветов.
Для доказательства этой формулы составим таблицу, столбцы которой будут подписаны всеми значениями <tex>f_i</tex>, строки {{---}} всеми перестановками <tex>k_j</tex>, а в клетках таблицы будут стоять их произведения . Тогда, если мы будем рассматривать столбцы этой таблицы как множества, то некоторые из них могут совпасть, и это будет означать, что соответствующие этим столбцам <tex>f</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>f_i</tex> одного объекта (иначе получилось бы, что некоторым эквивалентным преобразованием мы перешли в другой комбинаторный объект, что невозможно). Во-вторых, каждый элемент <tex>f_i</tex> будет встречаться одинаковое число раз во всех столбцах (это также следует из того, что столбцы соответствуют эквивалентным элементам). Отсюда можно сделать вывод, что все столбцы внутри одного комбинаторного объекта совпадают друг с другом как мультимножества.
Теперь зафиксируем произвольный элемент Тогда <tex>f|C| =</tex>. С одной стороны, он встречается в своём столбце ровно <tex>J(f)</tex> раз (по самому определению). С другой стороны, все столбцы внутри одного комбинаторного объекта одинаковы как мультимножества. Следовательно, внутри каждого столбца данного комбинаторного объекта любой элемент <tex>g\dfrac{1} {n}</tex> встречается ровно <tex>J\sum\limits_{q|n}\varphi\left(g\dfrac{n}{q}\right)k^q</tex> раз.
Таким образом, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу и просуммируем количество элементов в них, то получим, с одной стороны, <tex>C|G|</tex> (это получается, просто умножив количество столбцов на их размер), а == Алгоритм решения задачи про ожерелья с другой стороны {{---}} сумму величин <tex>J(f)</tex> по всем <tex>f</tex>(это следует из всех предыдущих рассуждений):<tex> C отражениями=</tex> <tex dpi = "180"> \frac{1} {|G|}</tex><tex>\sum\limits_{f} J(f)</tex>}}
== Теорема Пойа =={{Теорема|id=teorPo[[Файл:axis_of_braclets. png|author=Пойа300px|statement= <tex> C =</tex> <tex dpi = "180"> \frac{1} {thumb|Gright|}</tex><tex>\sum\limits_{k \in G} l^{P(k)}</tex> Слева пример оси для нечётного случая. Справа для чётного.]]Пусть теперь ожерелья считаются одинаковыми,где <tex>C</tex> {{---}} кол-во различных комбинаторных объектовесли они не только переходят друг в друга поворотом, <tex>Pно и отражением относительно некоторой оси (kось может проходить через две противоположные бусинки или через две противоположные пустоты в чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются bracelets </texref> - кол-во циклов в перестановке <tex>k<[https:/tex>, <tex>l</tex> {{---}} кол-во различных состояний одного элементаen.wikipedia.|proof=Для доказательства этой теорем достаточно установить следующее равенство<tex>Iorg/wiki/Necklace_(kcombinatorics) = l^{PNecklace (kcombinatorics)}]</texref>.Будем пользоваться [[Лемма Бёрнсайда и Теорема Пойа|леммой Бёрнсайда]].Разберём два случая.
Для начала покажем, что в качестве операций требуется рассматривать только повороты и отражения.
* Поворот и отражение {{---}} отражение.
Занумеруем наши бусинки по часовой стрелке. Поворот и отражение не меняют порядка (в каком-то направлении бусинки занумерованы по порядку). Нетрудно понять, что отражение меняет направление обхода наших бусинок и не меняет порядка. Если мы сначала сделаем поворот, а потом отразим относительно какой-нибудь оси, то мы то самое же можем получить и обыкновенным отражением относительно какой-то оси. Такая ось найдётся, потому что всегда можно выбрать ось, что поставит первую бусинку на своё изначальное место, поменяв направление обхода (если перебирать все оси подряд, начиная с оси, проходящей через нужную нам бусинку, то изначально она останется на своём месте, потом сместится на одно место, потом на два и.т.д.). Поэтому поворот и отражение не добавляет нам новой операции.
Рассмотрим некоторую перестановку <tex>k</tex> * Отражение и некоторый элемент <tex>f</tex>. Под действием перестановки <tex>k</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. Заметим, что внутри каждого цикла перестановки должны находиться одинаковые элементы <tex>f</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки <tex>k</tex> мы выбираем по одному значению, и тем самым мы получим все представления <tex>f</tex>, инвариантные относительно этой перестановки, т.е.:<tex>I(k) = l^поворот {{P(k)---}}</tex>отражение. }}Аналогичные рассуждения.
== Алгоритм решения задачи про ожерелья ==* Отражение и отражение {{---}} поворот.Тут мы дважды меняем направление обхода, но не меняем порядка. Поэтому данная операция заменяется обычным поворотом.
Пусть нам даны бусинки число бусинок нечётное, тогда мы имеем <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 =</tex> <tex dpi = "180"> |}{2} + \dfrac{1}{2n}k^{\fracdfrac{n + 1} {2}}n = \dfrac{|GC|}{2} + \dfrac{1}{2}k^{\dfrac{n + 1}{2}}</tex><tex>= \dfrac{1} {2n}\sum\limits_{l q|n}\varphi\left(\dfrac{n}{q}\in Gright)k^q + \dfrac{1}{2} k^{P(l)\dfrac{n + 1}{2}}</tex>
Очевидно, что для каждой перестановки длины Разберём теперь чётный случай. Тут мы имеем <tex>\frac{n}{2}</tex> существует ровно <tex>n</tex> циклических сдвиговосей, теперь найдем <tex>Pпроходящих через пустоты между бусинками (iось можно провести через пустоту после каждой бусинки, но половина из них будет повторяться)</tex>. Заметим, что в В таких вот случаях можно выбрать по <tex>i\frac{n}{2}</tex>-ой перестановке на бусинок и дать им произвольные цвета. Остальная половина восстановится по ним. Таким образом для данных осей количество неподвижных точек будет <tex>lk^{\frac{n}{2}}</tex>-ой позиции стоит элемент . Ещё у нас есть <tex>(i + l)\mod frac{n}{2}</tex>осей, проходящих через бусинки. Также, заметим, что элемент В данных случаях мы можем выбрать по <tex>a</tex> переходит в элемент <tex>a \frac{n}{2} + in1</tex>, где бусинок (бусинки на оси и все по одну какую-то сторону от неё). То есть будет <tex>i k^{\in [frac{n}{2} + 1; k]}</tex>неподвижных точек. Из этого следует, что длина цикла для <tex>iОпераций также </tex>-ой перестановки равна <tex>lcm(n, i)/i = n/gcd(i,n)2n</tex>.Откуда следует что:
<tex>C =</tex> <tex dpi = "180"> \frac{1} {n}</tex><tex>\sum\limits_{i = 1}^{n} k^{gcd(i,n)}</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>
где <tex>C</tex> - кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex> различных цветов== См.также ==* [[Лемма Бёрнсайда и Теорема Пойа]]* [[Функция Эйлера]]
== Примечания ==
<references/>
==CсылкиИсточники информации ==* [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::Ожерелья]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Теория групп]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/29798...50877»

Навигация