число циклических последовательностей

[leolev]

Циклической назовем линейную последовательность полученную циклическим сдвигом.
Задача - найти число циклических последовательностей длины $n$ составленную из $r$ символов.

Ответ такой:
$ \frac{1}{n}\sum_{d|n} \varphi(\frac{n}{d})r^d $


Для простого n = p есть очевидное решение: $ \frac{r^p -r}{p} + r$.
Для доказательства осознаем, что циклический сдвиг это тоже самое, что и поворот последовательности, где последний элемент как бы склеен с первым. Всего таких последовательностей $r^m$, но среди есть $r$ одноцветных и их надо посчитать отдельно. Оставшиеся надо поделить на $p$, потому что есть p способов повернуть последовательность.

Задача сложная и я не до конца осознаю причем здесь простота длины и откуда имеет место быть вышеприведенная устрашающая формула.

Это задача вроде как решается некой теоремой Пойа, но хотелось бы найти решения "с нуля" без читерства, с чем прошу помочь уважаемых форумчан!

upd: возникли сомнения насчет того, делить нужно именно на p. А вдруг при повороте некоторые раскраски совместятся?

[leolev]

Кажется я понял, почему в случае с простым p надо делить именно так. Все непериодические мы уже вычли, а среди периодических каждому циклическому слово соответствует p линейных, поэтому мы делим. Но это тоже надо как-то построже оформить, да?

[Brukvalub]

Подозреваю, что при таком начале сообщения:

leolev в сообщении #1061491 писал(а):

Циклической назовем линейную последовательность полученную циклическим сдвигом.

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

[2old]

Делители вылезают из-за того что циклическая последовательность может быть $AABB$, а может быть $BBBB$, например

[grizzly]

leolev
По запросу "количество циклических последовательностей" гугл сразу предлагает какую-то нарезку одной лекции на русском. Правда в странном формате и с предупреждением "предварительного ознакомления". Я лекцию не смотрел (не регистрировался), но создалось впечатление, что это именно оно и может быть полезно для Вас на вполне доступном и подробном уровне. (Вы можете попытаться посмотреть там или поискать такое же в другом месте.)

[NSKuber]

В этой задаче надо воспользоваться функцией Мёбиуса и первой формулой обращения Мёбиуса. Загляните в Википедию, вы сразу заметите сходство формулы обращения с данным результатом. Вот только как именно этот ответ выводится, не помню. Смотрел в лекциях ШАД Яндекса, но они закрыты для публичного доступа. Может, у вас получится самостоятельно.

[leolev]

Brukvalub в сообщении #1061925 писал(а):

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

Ну, я не знаю как определить формально, а неформально можно так. В линейной последовательности стрелочки идут от первого элемента ко второму, от второго - к третьему, и.т.д. вплоть до последней стрелки от предпоследнего к последнему. В циклической проводится стрелка от последнего к первому и тем самым задается класс эквивалентности, то есть все линейные последовательности длины n превращаются в одну циклическую, которой соответствует n линейных (столько способов выбрать начало (хотя не уверен, что слово начало тут уместно)).
Вообще исходная задача, насколько я понимаю, изоморфна следующей: есть r цветов и n секторов круга. Раскраски, которые совмещаются при повороте, неотличимы. Чему равно число всевозможных раскрасок, если круг можно поворачивать?

NSKuber в сообщении #1062075 писал(а):

функцией Мёбиуса и первой формулой обращения Мёбиуса

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

grizzly в сообщении #1062058 писал(а):

гугл сразу предлагает какую-то нарезку одной лекции на русском

Это ту, где мультпликативные функции и обращение Мёбиуса? Ну, все же хочется попытаться решить задачу в рамках школьно-олимпиадного инструментария. Без функций мёбиуса, орбит, стабилизаторов и прочих умных слов.

[Brukvalub]

leolev в сообщении #1062085 писал(а):

В линейной последовательности стрелочки идут от первого элемента ко второму, от второго - к третьему, и.т.д. вплоть до последней стрелки от предпоследнего к последнему.

Выходит, линейная последовательность состоит из стрелочек?

[provincialka]

Brukvalub
Из стрелочек состоит ее диаграмма Хассе. А циклическая последовательность -- это класс эквивалентности обычного кортежа относительно циклических сдвигов.

[grizzly]

leolev в сообщении #1062085 писал(а):

Это ту, где мультпликативные функции и обращение Мёбиуса?

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

leolev в сообщении #1062085 писал(а):

Ну, все же хочется попытаться решить задачу в рамках школьно-олимпиадного инструментария. Без функций мёбиуса, орбит, стабилизаторов и прочих умных слов.

У Вас уже есть опыт упрощения предложенных другими профессионалами (в педагогике в том числе) изложений задач до школьного уровня? Или это первая попытка?

[Brukvalub]

(Оффтоп)

provincialka в сообщении #1062103 писал(а):

Brukvalub
Из стрелочек состоит ее диаграмма Хассе. А циклическая последовательность -- это класс эквивалентности обычного кортежа относительно циклических сдвигов.

Вообще-то, я спрашивал ТС, желая обратить его внимание, что обсуждать задачу на форуме, при этом не зная даже определений упомянутых в задаче понятий - это моветон и большая глупость, но вам за ответ - зачОт!

[leolev]

grizzly в сообщении #1062108 писал(а):

У Вас уже есть опыт упрощения предложенных другими профессионалами (в педагогике в том числе) изложений задач до школьного уровня? Или это первая попытка?

Первая, а упростить я хочу впервую очередь для себя, так как одновременно воспринимать сложные понятия и идею задачи мне не позволяет слабая математическая культура. Или это безнадежная затея? Я думал, может кто подскажет ключевую идею решения, так как я не вижу. Наверное надо сделать "свою" лемму бернсайда, в менее общем виде.

grizzly в сообщении #1062108 писал(а):

Обратил внимание, что в обоих источниках итоговая формула выглядит иначе

Если посчитать для каких конкретных чисел, то выходит одно и то же, но прям явного соответствия между величинами я не вижу. Но оно же есть?

-- 13.10.2015, 19:50 --

provincialka в сообщении #1062103 писал(а):

Из стрелочек состоит ее диаграмма Хассе. А циклическая последовательность -- это класс эквивалентности обычного кортежа относительно циклических сдвигов.

Точно, Вы правы, просто я пытался определить отношение эквивалентности без слов "циклический сдвиг", так как не до конца понимал что вызывает нарекания и можно ли использовать это словосочетание

[grizzly]

leolev в сообщении #1062113 писал(а):

Если посчитать для каких конкретных чисел, то выходит одно и то же, но прям явного соответствия между величинами я не вижу. Но оно же есть?

Я сразу удалил то своё замечание.

leolev в сообщении #1062113 писал(а):

Или это безнадежная затея?

Да, пока безнадёжная. Но упорный труд в течение нескольких лет может Вам помочь (и я бы так не сказал, если бы Вы попросили объяснить доказательство ВТФ на пальцах). Но сейчас Вы хотите вступить в соревнование с людьми, которые являются гениями в вопросах подобных упрощений. Как Пойа, например. И, кстати, ссылка на учебник с решением по теории Пойа есть в упомянутой мной статье (она идёт под номером 1 в результатах гугла по предложенному запросу).

[leolev]

grizzly
спасибо, буду изучать.

grizzly в сообщении #1062121 писал(а):

вступить в соревнование

Не сказал бы, все же Пойа не конкретную задачу про ожерелья решал, а создавал алгоритм решения такого рода задач в самом общем случае. Начал читать, вообще тут достаточно Леммы Бёрнсайда, а не т.Пойа, так как последняя именно вычислительная

[grizzly]

leolev в сообщении #1062137 писал(а):

Не сказал бы, все же Пойа не конкретную задачу про ожерелья решал

Ок, не буду спорить -- я ещё не смотрел. Намерения у Вас здравые, раз Вы сдвинулись с мёртвой точки "подскажите гениальную идею" так что успехов. Будет у Вас интерес -- выкладывайте результаты.