Раскраска флагов

[SomePupil]

Бородатая задача. Есть $q$ красок различных цветов. Сколькими способами можно покрасить полосатый флаг, имеющий $n$ полос одинаковой ширины?

[gris]

Если требуется, чтобы все полосы были разного цвета, то ответ очевиден. Предполагается, наверное, что полосы могут быть и одноцветными? И даже соседние? И даже все?

[SomePupil]

Да, различные полосы могут быть одноцветными. Кроме того, флаг можно перевертывать, т. е. флаги с "палиндромальными" раскрасками считаются одинаковыми.

[gris]

Это что, у Индонезии и Польши одинаковые флаги? А сколько ругани было по поводу перепута бесикра и красиба

[SomePupil]

gris в сообщении #1313609 писал(а):

Это что, у Индонезии и Польши одинаковые флаги?

Будем считать, что флаги негосударственные.

[gris]

Извините за занудство, но в задаче основная трудность это понять требования к флагам. Вот могут ли быть соседние полосы одного цвета? Вы написали, что любая полоса может быть любого цвета. Тогда решение тоже очевидно. Впрочем, как и когда соседние полосы обязательно разного цвета. Остаётся учесть симметричные флаги. Это тоже сделать нетрудно, поанализировав верхнюю половинку флага. Учесть ещё чётность количества полос.

[SomePupil]

gris в сообщении #1313635 писал(а):

Вы написали, что любая полоса может быть любого цвета. Тогда решение тоже очевидно. Впрочем, как и когда соседние полосы обязательно разного цвета. Остаётся учесть симметричные флаги. Это тоже сделать нетрудно, поанализировав верхнюю половинку флага. Учесть ещё чётность количества полос.

Да, задача нетрудная. Я изначально задумывал топик так, чтобы он был про миниатюру, не более.

gris в сообщении #1313635 писал(а):

Извините за занудство, но в задаче основная трудность это понять требования к флагам.

У меня сразу возникли аллюзии ко всем тем топикам dxdy, где люди на нескольких страницах выясняли, о чем же идет речь. И ведь они иногда достигали этой цели! Надеюсь, этот топик не будет исключением)

P.S. На самом деле, я надеялся, что кто-то представит теоретико-групповое решение задачи. Учитывая, что граждане dxdy весьма любят палить из пушек по воробьям.)

[SomePupil]

P. P. S. И да, решение, которое я подразумевал, я постараюсь выложить в ближайшее время.

[eugensk]

То есть было бы $q^n$, если бы не условие что перевернутые флаги считать как один.

[Pphantom]

Тема переименована по просьбе ее автора.

[SomePupil]

eugensk в сообщении #1313664 писал(а):

То есть было бы $q^n$, если бы не условие что перевернутые флаги считать как один.

Да, если бы перевернутые не считать как один, то было бы так.

[gris]

SomePupil, предлагаю теоретико-числовую интерпретацию задачи: сколько существует неотрицательных целых чисел длины(или как там у них? ) не больше $n$ в $q$-ричной позиционной системе? А сколько из них палиндромов с учётом ведущих нулей. Первый ответ уже дали. Попробую определить количество палиндромов.
Пусть $n=2k$. Существует $q^k$ различных верхних половинок флагов и столько же отражённых палиндромов. Пусть $n=2k+1$. Средняя полоса не входит ни в одну половинку и может быть окрашена в любой цвет. То есть будет $q^{k+1}$ палиндромов. Палиндром не образует пары. А каждый непалиндром имеет перевёрнутую пару. Объединяя, получим итоговую формулу. $N=q^n - \frac12(q^n-q^{\lceil {n/2}\rceil})=\frac12(q^n+q^{\lceil {n/2}\rceil})$
Проверим. $q=1;n=n: N=1$ Верно. Один цвет — один флаг.
$q=2;n=2: N=3$ Верно. $q=q;n=1: N=q$ Верно.

[SomePupil]

Пусть $(s_1, s_2, \ldots, s_n),\; s_i \in \{1, 2, \ldots, n\}$ обозначают раскраски. Введем группу $G = \{e, f\}$ из тождественного элемента и флипа, и пусть эта группа действует на раскраски таким образом: $f(s_1, s_2, \ldots, s_{n-1}, s_n) = (s_n, s_{n-1}, \ldots, s_2, s_1).$ Различные раскраски в точности соответствуют орбитам этого действия. Количество орбит-раскрасок равно

$$C = \frac1{|G|}\sum_{g\in G}S(g),$$

где $S(g) -$ количество элементов-раскрасок, которые $g$ переводит в себя, $|G| = 2 -$ кол-во элементов в группе. Тождественный элемент $e$ переводит все раскраски в себя $S(e) = q^n.$ Флип же переводит в себя только палиндромальные раскраски, поэтому $S(f) = q^{\lceil \frac{n}2\rceil}.$ Следовательно,

$$C = \frac12 \left(q^n + {q^{\lceil\frac{n}{2}\rceil}\right),$$

что совпадает с ответом gris.
Теги: лемма Бернсайда, действия групп, их орбиты.

[gris]

SomePupil, выкатили Ваше орудие? Только сначала чисто комбинаторным сачком отловили воробьёв, рассадили их по двум мешкам, затолкали в групповую пушку и выстрелили не по воробьям, а воробьями. Чисто по-Китайски
На самом деле получилась симпатичная иллюстрация к Лемме Бёрнсайда. Изменим немного требования к флагам: соседние полосы разноцветны. Тоже легко посчитать ингредиенты формулы. С необходимостью использовать ровно $k$ цветов и т.п. Тут чуть сложнее. А можно считать одинаковыми флаги с циклической перестановкой цветов (то есть ожерелья).
В общем, задача Ваша действительно показывает необыкновенную красоту приложений теории групп.