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

[Alexander__]

Есть правильный 18-угольник. Сколько способов раскрасить вершины в $n$ цветов? Раскраски одинаковы, если совпадают при повороте.

---

Для каждой вершины можно независимо выбрать один из $n$ цветов. Поэтому способов раскрасить 18-угольник: $18^n$.

Подскажите, пожалуйста, как подсчитать кол-во одинаковых при повороте?

[dgwuqtj]

Есть лемма Бернсайда: количество орбит при действии конечной группы $G$ на конечном множестве $X$ равно среднему количеству неподвижных точек $\frac 1 G \sum_{g \in G} |\{x \in X \mid gx = x\}|$. В вашем случае группа вращений $\mathrm C_n$ действует на множестве всех раскрасок. Так что можно посчитать сумму из $18$ слагаемых, чтобы дальше не думать.

[iifat]

Ну, рассмотреть каждый поворот, расписать соотношения и посчитать, имхо. Всего поворотов девять (отрицательные эквивалентны положительным), не так уж, в принципе, и много.
Тут же ещё как: например, поворот на 2. То бишь, 1 переходит в 3, 3 в 5, ну и так далее. Восемнадцатиугольник распадается на два девятиугольника, которые надо рассмотреть отдельно, с поворотом на 1 каждый.
Если взять, например, поворот на пять, то $5\times7\equiv-1\pmod{18}$, то бишь, если многоугольник при повороте на пять переходит в себя, то и при повороте на -1 он перейдёт в себя же, так что пять можно не рассматривать.

[dgwuqtj]

Вообще всё должно зависеть только от порядка поворота, это будет 6 слагаемых.

[Alexander__]

dgwuqtj в сообщении #1607072 писал(а):

Есть лемма Бернсайда: количество орбит при действии конечной группы $G$ на конечном множестве $X$ равно среднему количеству неподвижных точек $\frac 1 G \sum_{g \in G} |\{x \in X \mid gx = x\}|$. В вашем случае группа вращений $\mathrm C_n$ действует на множестве всех раскрасок. Так что можно посчитать сумму из $18$ слагаемых, чтобы дальше не думать.

Это крутовато

-- 29.08.2023, 17:39 --

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

Ну, рассмотреть каждый поворот, расписать соотношения и посчитать, имхо. Всего поворотов девять (отрицательные эквивалентны положительным), не так уж, в принципе, и много.
Тут же ещё как: например, поворот на 2. То бишь, 1 переходит в 3, 3 в 5, ну и так далее. Восемнадцатиугольник распадается на два девятиугольника, которые надо рассмотреть отдельно, с поворотом на 1 каждый.
Если взять, например, поворот на пять, то $5\times7\equiv-1\pmod{18}$, то бишь, если многоугольник при повороте на пять переходит в себя, то и при повороте на -1 он перейдёт в себя же, так что пять можно не рассматривать.

Я не понимаю. Давайте упростим до 6-угольника. Если начать с поворота на 1, там же зависит от конкретных цветов, в которые разукрашен, т.е. может перейти в "одинаковый", а может нет, т.е. для поворота на 1 разных может быть от 1 до 6.

[dgwuqtj]

Для шестиугольника надо посчитать $\frac 1 6 (N_0 + N_1 + \ldots + N_5)$, где $N_k$ - это количество раскрасок, сохраняющихся при повороте на $k$. В частности, $N_0$ - это количество всех раскрасок. При повороте на 1 раскраски, которые сохраняются, - это в точности когда всё покрашено в один цвет, их $n$.

[iifat]

Alexander__ в сообщении #1607089 писал(а):

Давайте упростим до 6-угольника

Прекрасный метод.

Alexander__ в сообщении #1607089 писал(а):

Если начать с поворота на 1, там же зависит от конкретных цветов, в которые разукрашен

Вот отсюда уже не понимаю. Можно поподробнее: что можно сказать про раскрашенный шестиугольник, если известно, что при повороте на $60^\circ$ он переходит в себя?

[Alexander__]

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

Alexander__ в сообщении #1607089 писал(а):

Давайте упростим до 6-угольника

Прекрасный метод.

Alexander__ в сообщении #1607089 писал(а):

Если начать с поворота на 1, там же зависит от конкретных цветов, в которые разукрашен

Вот отсюда уже не понимаю. Можно поподробнее: что можно сказать про раскрашенный шестиугольник, если известно, что при повороте на $60^\circ$ он переходит в себя?

Я тоже не понял предыдущий тезис. Поворот на $60^\circ$ -- поворот на 1 вершину. Если перешёл в себя, то у каждой предыдущей вершины до поворота был тот же цвет, что у текущей, т.е. все вершины были одного цвета. Т.е. для каждого из $n$ цветов существует 6 идентичных 6-угольников, т.е. при итоговом подсчёте нужно выкинуть 5 из 6 таких 6-угольников. Если используется 2 и более цветов, то все 6-угольники будут разные (при повороте на 1). Поэтому ответ тут: $6^n - 5 n$. Верно?

[iifat]

Вычитать ещё рано. Просто запомнить, что надо вычесть $5n$.
Ну, теперь примерно так же попробуйте с поворотами на 2 вершины разобраться.

[Alexander__]

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

Вычитать ещё рано. Просто запомнить, что надо вычесть $5n$.
Ну, теперь примерно так же попробуйте с поворотами на 2 вершины разобраться.

6-угольник переходит в себя при повороте на 2 вершины, если вершины 1-3-5 окрашены в один цвет, и аналогично для вершин 2-4-6 в какой-от отличный от первого цвет. Цвет первого набора из 3х вершин можно выбрать $n$ способами, цвет второго -- $n-1$ способами. Повернуть на 2 вершины можно 3 раза. Итого идентичных 6-угольников: $3n(n-1)$. Верно?

[iifat]

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

[dgwuqtj]

Вообще так можно посчитать ответ, надо просто для каждой подгруппы $\mathrm C_6$ найти, сколько раскрасок сохраняются в точности этой подгруппой, и просуммировать. Например, те раскраски, которые сохраняются только тривиальной подгруппой, - это апериодические.

[iifat]

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

[Alexander__]

Ещё упростил задачу. Существенны 2 варианта:
1. одноцветные, которых $n$
2. разноцветные, которых без поворотов $n^3-n$. но каждую разноцветную можно повернуть 1, 2 или 3 раза, и она перейдёт в какую-то из $n^3-n$. поэтому уникальных разноцветных в 3 раза меньше: $\frac{n^3-n}{3}$

Вопрос что в таком подходе делать, если кол-во вершин -- не простое число. Например, для квадрата раскрасим вершины в цвета $xyxy$, тогда квадрат перейдёт в себя уже при повороте на 2, а не на 4.

-- 31.08.2023, 17:17 --

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

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

$$C_0 = n(n-1)(n-2)(n-3)(n-4)(n-5)$$

$$C_1=n$$

$$C_2=3 n (n-1)$$

$$C_3=2 n (n-1)(n-2)$$

Верно понял $C_i$?

[dgwuqtj]

Для шестиугольника ответ - это $ (n^6 + n^3 + 2n^2 + 2n)/6 $, если что.