번사이드 보조정리

문제

회전·반사 같은 대칭으로 "같다"고 보는 채색·배열의 서로 다른 가짓수를 센다. 예: 구슬 \(n\)개를 \(k\)색으로 칠한 목걸이(회전 동일), 정육면체 면 색칠 등. 단순히 \(k^n\) 을 세면 대칭으로 겹치는 것을 중복 계산한다.

군 작용과 궤도

대칭들의 집합은 군 \(G\) 를 이루고, 색칠 전체 집합 \(X\) 에 작용한다. 두 색칠이 어떤 \(g\in G\) 로 서로 옮겨지면 같은 궤도(orbit). 우리가 세려는 것은 궤도의 개수다.

번사이드 보조정리

$$ \#\text{궤도} = \frac{1}{|G|} \sum_{g \in G} |X^g| $$

여기서 \(X^g\) 는 \(g\) 가 고정하는 색칠들의 집합(즉 \(g\) 를 적용해도 그대로인 색칠). "각 대칭이 고정하는 배열 수의 평균이 궤도 수"라는 우아한 정리다. 증명은 쌍 \((g, x)\) with \(g\cdot x = x\) 를 두 가지로 세는 이중 계수에서 나온다(오비-스태빌라이저 정리와 결합).

고정점 세기

핵심은 각 \(g\) 의 고정 색칠 수 \(|X^g|\) 를 세는 것. \(g\) 가 위치들에 작용하면 위치들이 여러 순환(cycle) 으로 쪼개진다. 한 순환에 속한 위치들은 색이 모두 같아야 \(g\) 가 그 색칠을 고정한다. 따라서

$$ |X^g| = k^{\,c(g)} $$

(\(c(g)\) = \(g\) 의 순환 개수, \(k\) = 색 수). 회전군이면 회전 \(d\) 칸의 순환 수는 \(\gcd(n,d)\).

폴리아 열거정리

색에 가중치(생성함수)를 붙이면 번사이드의 정련판인 폴리아 정리로 "각 색을 정확히 몇 개 쓰는" 분포별 가짓수까지 센다. 사이클 지표 다항식

$$ Z(G) = \frac{1}{|G|}\sum_{g} \prod_i a_i^{\,(\text{길이 } i \text{ 순환 수})} $$

에 \(a_i \to \sum_c x_c^i\) 를 대입한다.

예: 목걸이

\(n\)구슬 \(k\)색 회전 목걸이 수:

$$ \frac{1}{n}\sum_{d=0}^{n-1} k^{\gcd(n,d)} = \frac{1}{n}\sum_{e \mid n} \phi(n/e)\, k^{e}. $$

회전 목걸이 가짓수

\(\frac{1}{n}\sum_{e\mid n}\phi(n/e)\,k^e\) 를 그대로 구현.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

ll power(ll a, ll b, ll m){ ll r=1;a%=m;for(;b;b>>=1,a=a*a%m) if(b&1)r=r*a%m; return r; }
ll phi(ll n){ ll res=n; for(ll p=2;p*p<=n;p++) if(n%p==0){ while(n%p==0)n/=p; res-=res/p; } if(n>1) res-=res/n; return res; }

ll necklaces(ll n, ll k) {           // 회전만 (반사 제외)
    ll total = 0;
    for (ll e = 1; e * e <= n; e++) if (n % e == 0) {
        total = (total + phi(n / e) % MOD * power(k, e, MOD)) % MOD;
        ll e2 = n / e;
        if (e2 != e)
            total = (total + phi(n / e2) % MOD * power(k, e2, MOD)) % MOD;
    }
    ll inv_n = power(n % MOD, MOD - 2, MOD);
    return total % MOD * inv_n % MOD;            // 1/|G| = 1/n
}

반사 포함(이면체군 \(D_n\))

회전 \(n\)개 + 반사 \(n\)개. 반사의 고정점은 \(n\) 의 홀짝에 따라 다르다.

ll bracelets(ll n, ll k) {           // 회전 + 반사
    ll rot = necklaces(n, k) * (n % MOD) % MOD;   // 회전 합 (1/n 곱하기 전 값 복원)
    ll refl;
    if (n % 2 == 1) refl = n % MOD * power(k, (n + 1) / 2, MOD) % MOD;
    else refl = (n / 2 % MOD) * (power(k, n / 2 + 1, MOD) + power(k, n / 2, MOD)) % MOD;
    ll inv = power(2 * n % MOD, MOD - 2, MOD);     // |G| = 2n
    return (rot + refl) % MOD * inv % MOD;
}

자주 하는 실수

• \(1/|G|\) 모듈러. 정수 나눗셈이 아니라 페르마 역원 곱. \(MOD\) 소수 필요.
• 반사 고정점 공식. \(n\) 홀수면 축이 한 꼭짓점-한 변 중점을 지나 \((n+1)/2\) 순환. 짝수면 두 종류(꼭짓점축/변축)를 나눠 평균.
• 약수 순회. \(\phi\) 를 약수마다. \(n\) 이 크면 소인수분해로 \(\phi\) 합을 빠르게.
• 고정점 = \(k^{c(g)}\). 색이 위치가 아니라 "객체"면 순환 구조를 다시 분석.

응용

폴리아로의 확장

"빨강을 정확히 \(r\)개" 같은 분포별 카운팅이면 사이클 지표에 변수 생성함수를 대입한다. 각 군 원소의 순환 길이 분포를 모아 \(Z(G)\) 를 만들고 다항식 계수를 읽으면 된다.