Теорема Бёрнсайда: как посчитать число раскрасок ожерелья с точностью до поворотов?
Сколько различных ожерелий из n бусин k цветов, если ожерелья, переходящие друг в друга поворотом, считаются одинаковыми? Без учёта симметрии было бы k^n, но как правильно «поделить» на повороты — ведь делить на n в лоб неправильно? Слышал про лемму Бёрнсайда.
2 ответа
Лемма Бёрнсайда: число классов эквивалентности под действием группы G равно среднему числу раскрасок, неподвижных под каждым элементом группы:
|классов| = (1/|G|) · Σ_{g ∈ G} |Fix(g)|.
Для поворотов ожерелья группа — циклическая C_n из n поворотов. Поворот на d позиций разбивает бусины на циклы, и неподвижными остаются раскраски, постоянные внутри каждого цикла. Число циклов поворота на d равно gcd(n, d), поэтому |Fix(поворот на d)| = k^{gcd(n,d)}. Итог:
ответ = (1/n) · Σ_{d=0}^{n−1} k^{gcd(n,d)}.
long long gcd(long long a, long long b){return b?gcd(b,a%b):a;}
long long power(long long a,long long b){long long r=1;while(b){if(b&1)r*=a;a*=a;b>>=1;}return r;}
long long necklaces(int n, int k) { // без модуля, n,k маленькие
long long total = 0;
for (int d = 0; d < n; d++)
total += power(k, gcd(n, d));
return total / n; // сумма всегда делится на n
}
Сложность O(n log k) (или O(n log n) с gcd). Сумма гарантированно делится на n, поэтому целочисленное деление корректно. Это и есть «правильное деление на повороты».
Два важных уточнения. (1) По модулю делить на n нельзя обычным / — нужно умножать на обратный к n по модулю (через Ферма), а n должно быть взаимно просто с модулем. (2) Если кроме поворотов разрешены ещё и отражения (как у настоящего ожерелья, которое можно перевернуть), группа — диэдральная D_n из 2n элементов, и к сумме добавляются вклады отражений (для них число неподвижных раскрасок зависит от чётности n). Теорема Пойа — это обобщение Бёрнсайда, дающее производящую функцию по цветам через индекс циклов группы.