1632
правки
Изменения
м
{{Определение== Алгоритм решения задачи про ожерелья ==|definition='''Инвариантная перестановка''' - такая перестановка, которая по условию задачи не меняет сам объектПусть нам даны бусинки <tex>k</tex> различных цветов, а только его представлениеожерелье должно состоять из <tex>n</tex> бусинок.}}Примером инвариантной перестановки в нашем случае является циклический сдвигДля решения воспользуемся формулой из теоремы Пойа.
{{ЛеммаПо условию, перестановкой инвариантной данной будет любая перестановка, полученная из данной циклическим сдвигом.|idОчевидно, что для каждой перестановки длины <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 =lemmaBerns1, 2, \ldots k</tex>. |authorИз этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex> \dfrac{\mathrm{lcm}(n, i)}{i} =Бернсайд\dfrac{n}{\mathrm{gcd}(i,n)}</tex>, где <tex>\mathrm{gcd}(i, n)</tex> {{---}} [[Наибольший общий делитель|statement=Количество комбинаторных объектов равно сумме количеств неподвижных точек по всем перестановкам из группы НОД<tex>(i, n)</tex>]], <tex>G\mathrm{lcm}(i, n)</tex> {{---}} [[Наименьшее общее кратное|НОК<tex>(i, делённой на размер этой группыn)</tex>]]. Откуда следует что:
Для доказательства этой формулы составим таблицуЕсли раскраски ожерелья одинаковые, столбцы которой будут подписаны всеми значениями то они принадлежат одной [[Орбита|орбите]], т.е. одна получается из другой некоторым преобразованием симметрии. Неподвижные точки поворота есть только у тождественного поворота и их <tex>n</tex> штук. Тогда, по [[Лемма Бёрнсайда и Теорема Пойа|лемме Бёрнсайда]], число орбит равняется <tex>\dfrac{n}{p}=\operatorname{gcd}(n,i)</tex>, где <tex>f_ip</tex>минимальное число такое, строки — всеми перестановками что <tex>ip</tex> делится на <tex>k_jn</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>f\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>.
Cтолбцы таблицы сами распадаются на комбинаторные обекты; зафиксируем теперь какой-либо объект и рассмотрим столбцы в нём. Во-первых, заметим, что в этих столбцах могут стоять только элементы Тогда <tex>f_i|C| =</tex> одного объекта (иначе получилось бы, что некоторым эквивалентным преобразованием мы перешли в другой комбинаторный объект, что невозможно). Во-вторых, каждый элемент <tex>f_i\dfrac{1} {n}</tex> будет встречаться одинаковое число раз во всех столбцах <tex>\sum\limits_{q|n}\varphi\left(это также следует из того, что столбцы соответствуют эквивалентным элементам\dfrac{n}{q}\right). Отсюда можно сделать вывод, что все столбцы внутри одного комбинаторного объекта совпадают друг с другом как мультимножестваk^q</tex>.
Теперь зафиксируем произвольный элемент <tex>f</tex>. С одной стороны, он встречается в своём столбце ровно <tex>J(f)</tex> раз (по самому определению). С другой стороны, все столбцы внутри одного комбинаторного объекта одинаковы как мультимножества. Следовательно, внутри каждого столбца данного комбинаторного объекта любой элемент <tex>g</tex> встречается ровно <tex>J(g)</tex> раз.== Алгоритм решения задачи про ожерелья с отражениями==
Таким образом[[Файл:axis_of_braclets.png|300px|thumb|right|Слева пример оси для нечётного случая. Справа для чётного.]]Пусть теперь ожерелья считаются одинаковыми, если мы возьмём произвольным образом от каждого класса эквивалентности по одному столбцу они не только переходят друг в друга поворотом, но и просуммируем количество элементов отражением относительно некоторой оси (ось может проходить через две противоположные бусинки или через две противоположные пустоты в них, то получим, с одной стороны, чётном случае и через бусинку и пустоту напротив неё в нечётном случае). Такие ожерелья называются bracelets <texref>C|G|<[https://en.wikipedia.org/wiki/tex> Necklace_(это получается, просто умножив количество столбцов на их размерcombinatorics), а с другой стороны — сумму величин <tex>JNecklace (fcombinatorics)]</texref> по всем <tex>f</tex>(это следует из всех предыдущих рассуждений):.Будем пользоваться [[Лемма Бёрнсайда и Теорема Пойа|леммой Бёрнсайда]].Разберём два случая.
<tex>C = \fracДля начала покажем, что в качестве операций требуется рассматривать только повороты и отражения. * Поворот и отражение {1} {|G|---}\sum\limits_{f} Jотражение. Занумеруем наши бусинки по часовой стрелке. Поворот и отражение не меняют порядка (fв каком-то направлении бусинки занумерованы по порядку)</tex>}}. Нетрудно понять, что отражение меняет направление обхода наших бусинок и не меняет порядка. Если мы сначала сделаем поворот, а потом отразим относительно какой-нибудь оси, то мы то самое же можем получить и обыкновенным отражением относительно какой-то оси. Такая ось найдётся, потому что всегда можно выбрать ось, что поставит первую бусинку на своё изначальное место, поменяв направление обхода (если перебирать все оси подряд, начиная с оси, проходящей через нужную нам бусинку, то изначально она останется на своём месте, потом сместится на одно место, потом на два и.т.д.). Поэтому поворот и отражение не добавляет нам новой операции.
== Теорема Пойа =={{Теорема|id=teorPo. |author=Пойа|statement= <tex>C = \frac{1} {|G|}\sum\limits_* Отражение и поворот {k \in G} l^{P(k)}</tex> ,где <tex>C</tex> - кол-во различных комбинаторных объектов, P(k) - кол-во циклов в перестановке <tex>k</tex>, <tex>l</tex>- кол-во различных состояний одного элемента}} отражение.|proof=Для доказательства этой теорем достаточно установить следующее равенство<tex>I(k) = l^{P(k)}</tex>Аналогичные рассуждения.
Рассмотрим некоторую перестановку Пусть число бусинок нечётное, тогда мы имеем <tex>kn</tex> осей, проходящих через каждую бусинку. Рассмотрим одну ось. Возьмём половину бусинок с одной стороны от оси и некоторый элемент <tex>f</tex>ту бусинку, через которую проходит данная ось. Мы можем окрасить их в произвольные цвета, а остальная половина по ним однозначно восстановится. Под действием перестановки Таким образом количество неподвижных точек для одной оси будет <tex>k^{\frac{n + 1}{2}}</tex> элементы <tex>f</tex> передвигаются, как известно, по циклам перестановки. ЗаметимОпераций в группе будет в два раза больше, что внутри каждого цикла перестановки должны находиться одинаковые элементы чем было: <tex>f2n</tex>. В то же время, для разных циклов никакой связи между значениями элементов не возникает. Таким образом, для каждого цикла перестановки (<tex>kn</tex> мы выбираем по одному значению, сдвигов и тем самым мы получим все представления <tex>fn</tex>, инвариантные относительно этой перестановки, тотражений).е.:<tex>I(k) = l^{P(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>|B| = \dfrac{|C|}{2} + \dfrac{1}{2n}\left(\dfrac{n</tex> существует ровно <tex>}{2}k^{\frac{n</tex> циклических сдвигов, теперь найдем <tex>P(i)</tex>. Заметим, что в <tex>i</tex>-ой перестановке на <tex>l</tex>-ой позиции стоит элемент <tex>(i }{2}} + l)\mod dfrac{n}{2}k^{\frac{n}{2} + 1}\right)</tex>. Также, заметим, что элемент <tex>a</tex> переходит в элемент <tex>a = \dfrac{|C|}{2} + in</tex>, где <tex>i \in [dfrac{1; }{4}k]</tex>. Из этого следует, что длина цикла для <tex>i</tex>-ой перестановки равна <tex>lcm^{\frac{n}{2}}(n, ik + 1)/i = \dfrac{1} {2n}\sum\limits_{q|n/gcd}\varphi\left(i,\dfrac{n}{q}\right)k^q + \dfrac{1}{4}k^{\frac{n}{2}}(k+1)</tex>.Откуда следует что:
<tex>C = \frac{1} {n}\sum\limits_{i = 1}^{n} k^{gcd(i,n)}</tex>См.также ==* [[Лемма Бёрнсайда и Теорема Пойа]]* [[Функция Эйлера]]
где С == Источники информации ==* [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 Википедия {{- кол-во различных -}} Теорема Редфилда — Пойа, Задача о количестве ожерелий,которые можно составить из n бусинок k различных цветов]* [http://e-maxx.ru/algo/necklace_colouring MAXimal::algo::Ожерелья]
==Cсылки==[[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]*[http[Категория://e-maxx.ru/algo/necklace_colouring ОжерельяТеория групп]]
rollbackEdits.php mass rollback
{{ОпределениеЗадача
|definition=
Требуется посчитать количество ожерелий из <tex>n</tex> бусинок, каждая из которых может быть покрашена в один из <tex> k </tex> цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).}}
Решение этой задачи опирается на [[Лемма Бёрнсайда и Теорема Пойа|лемму Бернсайда Бёрнсайда и теорему Пойа]].
<tex>|C| =</tex> <tex> \dfrac{1} {Определение|definition='''Неподвижной точкой''' G|}</tex>f</tex> для перестановки называется такой элемент, который инвариантен относительно этой перестановки.\sum\limits_{l \in G}k^{P(l)}== Лемма Бернсайда ==</tex>
<tex> |C | = \frac{1} {|G|}\sum\limits_{k \in G}I(k)</tex>. Где <tex>I(k)</tex> - количество неподвижных точек для перестановки <tex>k\dfrac{1} {n}</tex>.|proof=Рассмотрим сумму в числителе дроби справа:<tex>\sum\limits_{i = 1}^{n} k ^{\in Gmathrm{gcd}I(ki,n)}</tex> — это ни что иное как количество "инвариантных пар". Очевидно, что в формуле мы имеем право изменить порядок суммирования - сделать внешнюю сумму по элементам множества <tex>f</tex>, а внутри нее поставить величину <tex>J(f)</tex> — количество перестановок, относительно которых объект <tex>f</tex> инвариантен:
где <tex>|C = \frac|</tex> {1} {|G|---}\sum\limits_{f} J(f)кол-во различных ожерелий,которые можно составить из <tex>n</tex> бусинок <tex>k</tex>различных цветов.
* Отражение и отражение {{---}} поворот.
Тут мы дважды меняем направление обхода, но не меняем порядка. Поэтому данная операция заменяется обычным поворотом.
По Лемме Бёрнсайда:<tex> |B| == Алгоритм решения задачи про ожерелья ==</tex> <tex>\dfrac{1} {|G|}</tex><tex>\sum\limits_{k \in G}I(k)</tex>
Разберём теперь чётный случай. Тут мы имеем <tex>C = \frac{1n}{2}</tex> осей, проходящих через пустоты между бусинками (ось можно провести через пустоту после каждой бусинки, но половина из них будет повторяться). В таких вот случаях можно выбрать по <tex>\frac{n} {|G|2}</tex> бусинок и дать им произвольные цвета. Остальная половина восстановится по ним. Таким образом для данных осей количество неподвижных точек будет <tex>k^{\sumfrac{n}{2}}</tex>. Ещё у нас есть <tex>\limits_frac{n}{l 2}</tex> осей, проходящих через бусинки. В данных случаях мы можем выбрать по <tex>\in Gfrac{n} {2} + 1</tex> бусинок (бусинки на оси и все по одну какую-то сторону от неё). То есть будет <tex>k^{P(l)\frac{n}{2} + 1}</tex> неподвижных точек. Операций также <tex>2n</tex>.
По Лемме Бёрнсайда:
== Примечания ==
<references/>
