Количество способов раскрасить вершины многоугольника

[tolstopuz]

По лемме Бернсайда этот ответ получается без утомительных расчетов.

Раскраски, не меняющиеся при повороте на $0$ вершин - это все раскраски, их $n^6$.
Раскраски, не меняющиеся при повороте на $1$ или $5$ вершин - с периодом $1$, их $n$.
Раскраски, не меняющиеся при повороте на $2$ или $4$ вершины - с периодом $2$, их $n^2$.
Раскраски, не меняющиеся при повороте на $3$ вершины - с периодом $3$, их $n^3$.

Итого действительно имеем $\frac16(n^6+n^3+2n^2+2n)$.

Для $18$ вершин повороты на $i$ вершин так же группируются по $\operatorname{gcd}(i,18)$, и должно получиться $6$ слагаемых со степенями - делителями $18$.

[Gyros]

Цитата:

Итого действительно имеем $\frac16(n^6+n^3+2n^2+2n)$.

Извините, но на мой беглый взгляд, ответ должен быть другим.
См. книгу "Алгебра" Городенцев, стр 263, пример 15.4.6. Только там не шестиугольник, а ожерелье с шестью бусинами.

Сколько различных ожерелий одинаковой формы можно сделать из 6 бусин?
Ответом на этот вопрос является кол-во орбит группы диэдра $D_6$ на множестве всех раскрасок вершин правильного шестиугольника в $n$ цветов.

$|D_k|=2k$, т.е. $|D_6|=12$

[dgwuqtj]

По условию ТС надо смотреть на группу поворотов $\mathrm C_6$, а не всех симметрий. Это ровно то, что называется ожерельями в комбинаторике.

[tolstopuz]

По другой терминологии симметрия $D_6$ - это ожерелья, их можно переворачивать, а $C_6$ - это хороводы, девушек в хороводе переворачивать нельзя.

[svv]

Согласно OEIS, русской Википедии и английской Википедии ожерелье нельзя переворачивать, а браслет можно.

[tolstopuz]

(Оффтоп)

svv в сообщении #1607782 писал(а):

Согласно OEIS, русской Википедии и английской Википедии ожерелье нельзя переворачивать, а браслет можно.

Да, видимо, я перепутал ожерелье с браслетом.

[Alexander__]

iifat в сообщении #1607430 писал(а):

Действительно, не туда.
Итак. Разорвём многоугольник и вытянем в одну линию. Таких различных линий будет, естественно, $n^6$.
При этом линия $xyzuvw$ даёт тот же многоугольник, что и $yzuvwx$, $zuvwxy$ и так далее — всего шесть.
Линия $xxxxxx$ даёт многоугольник, который переходит в себя при любом повороте, так что такие многоугольники будут подсчитаны один раз.
Линия $xyxyxy$ даёт многоугольник, который переходит в себя при повороте на две вершины, так что такие многоугольники будут посчитаны два раза.
Наконец, $xyzxyz$ даёт многоугольник, который переходит в себя при повороте на три вершины и будет подсчитан три раза.
То бишь, формула $\frac{C_0}6+{C_1}+\frac{C_2}2+\frac{C_3}3$
Всё (для шести вершин). Вроде так.

Проверяющие мне говорят, что для л.Бернсайда пока рановато :) Вот это решение ведь по лемме?

Есть такая задача с решением. Решение я понимаю, но не понимаю как его поменять, если кол-во вершин непростое число.

[dgwuqtj]

А чем можно пользоваться вообще? Понятиями из теории групп, кроме леммы Бернсайда? Или надо на школьном уровне придумывать?