MAXimal

добавлено: 11 Jun 2008 11:17
редактировано: 1 Jun 2009 11:36

Ожерелья

Задача "ожерелья" — это одна из классических комбинаторных задач. Требуется посчитать количество различных ожерелий из 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[...]