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