Ожерелья

Задача "ожерелья" — это одна из классических комбинаторных задач. Требуется посчитать количество различных ожерелий из $n$ бусинок, каждая из которых может быть покрашена в один из $k$ цветов. При сравнении двух ожерелий их можно поворачивать, но не переворачивать (т.е. разрешается сделать циклический сдвиг).

Решение

Решить эту задачу можно, используя лемму Бернсайда и теорему Пойа. [ Ниже идёт копия текста из этой статьи ]

В этой задаче мы можем сразу найти группу инвариантных перестановок. Очевидно, она будет состоять из $n$ перестановок:

$\pi_0 = 1\ 2\ 3\ \ldots\ n$
$\pi_1 = 2\ 3\ \ldots\ n\ 1$
$\pi_2 = 3\ \ldots\ n\ 1\ 2$
$\ldots$
$\pi_{n-1} = n\ 1\ 2\ \ldots\ (n-1)$

Найдём явную формулу для вычисления $C(\pi_i)$ . Во-первых, заметим, что перестановки имеют такой вид, что в $i$ -ой перестановке на $j$ -ой позиции стоит $i+j$ (взятое по модулю $n$ , если оно больше $n$ ). Если мы будем рассматривать циклическую структуру $i$ -ой перестановки, то увидим, что единица переходит в $1+i$ , $1+i$ переходит в $1+2i$ , $1+2i$ — в $1+3i$ , и т.д., пока не придём в число $1 + kn$ ; для остальных элементов выполняются похожие утверждения. Отсюда можно понять, что все циклы имеют одинаковую длину, равную ${\rm lcm}(i,n) / i$ , т.е. $n / {\rm gcd}(i,n)$ ("gcd" — наибольший общий делитель, "lcm" — наименьшее общее кратное). Тогда количество циклов в $i$ -ой перестановке будет равно просто ${\rm gcd}(i,n)$ .

Подставляя найденные значения в теорему Пойа, получаем решение:

${\rm Ans} = \frac{1}{n} \sum_{i=1}^{n} k ^ {{\rm [...]$

Можно оставить формулу в таком виде, а можно её свернуть ещё больше. Перейдём от суммы по всем $i$ к сумме только по делителям $n$ . Действительно, в нашей сумме будет много одинаковых слагаемых: если $i$ не является делителем $n$ , то таковой делитель найдётся после вычисления ${\rm gcd}(i,n)$ . Следовательно, для каждого делителя $d|n$ его слагаемое $k^{{\rm gcd}(d,n)} = k^d$ учтётся несколько раз, т.е. сумму можно представить в таком виде:

${\rm Ans} = \frac{1}{n} \sum_{d|n} C_d k^d$

где $C_d$ — это количество таких чисел $i$ , что ${\rm gcd}(i,n) = d$ . Найдём явное выражение для этого количества. Любое такое число $i$ имеет вид: $i=dj$ , где ${\rm gcd}(j,n/d) = 1$ (иначе было бы ${\rm gcd}(i,n) > d$ ). Вспоминая функцию Эйлера, мы находим, что количество таких $j$ — это величина функции Эйлера $\phi(n/d)$ . Таким образом, $C_d = \phi(n/d)$ , и окончательно получаем формулу:

${\rm Ans} = \frac{1}{n} \sum_{d|n} \phi \left( \f[...]$