번사이드 보조정리 (Burnside's Lemma)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 3분 · 970자/단어 #algorithm #game #burnside #combinatorics

정의

번사이드 보조정리 (Burnside’s Lemma, Cauchy-Frobenius Lemma) 는 군 G 가 집합 X 에 작용할 때, 궤도(orbit)의 개수 를 구하는 공식:

|X/G| = (1/|G|) * sum_{g in G} |Fix(g)|

Fix(g): g 에 의해 고정되는(fixed) X 의 원소 집합.
|G|: 군의 크기 (group order).

1845년 Cauchy 최초 발견, Burnside (1897) 가 저서로 널리 알림.

문제 상황과 동기

대칭(symmetry) 이 있는 조합적 대상의 “본질적으로 다른” 개수를 셀 때.

naive: 모든 경우를 나열 후 중복 제거. k^n 가지가 n! 대칭과 합쳐져 폭발.
Burnside: 각 대칭 변환(g) 에 대해 불변인 배치 수를 세고 평균.

핵심 통찰: 대칭 변환 각각에 대해 고정되는 배치 수는 독립적으로 계산 가능. 그 평균이 곧 distinct orbits 수.

시각화

핵심 아이디어

공식의 의미

3단계로 구성:

대칭 변환 나열: 군 G 의 모든 원소 g 를 나열한다.
고정점 계산: 각 g 에 대해 g 를 적용해도 변하지 않는 X 의 원소(배치) 수 |Fix(g)| 를 구한다.
평균: 모두 더한 후 |G| 로 나눈다.

예시: 4개 구슬 목걸이, 2색 (회전만)

회전군 C_4 (4개 회전):

| 회전 | 고정 조건 | |Fix(g)| | |:---|---:|:---| | 0도 (항등) | 모든 2^4 가지 | 16 | | 90도 | 모든 구슬 같은 색 | 2 | | 180도 | 마주보는 쌍 동일 | 4 | | 270도 | 모든 구슬 같은 색 | 2 |

(16 + 2 + 4 + 2) / 4 = 6 가지.

일반식 (회전만)

necklace(n, k) = (1/n) * sum_{r=0}^{n-1} k^{gcd(n, r)}

Polya vs Burnside

정리	관점	입력
Burnside	각 변환의 고정점	`\|Fix(g)\|` 직접 계산
Polya	각 변환의 순환 구조	`k^{C(g)}` (C(g) = 순환 개수)

알고리즘

burnside_necklace(n, k):
    total = 0
    for r = 0..n-1:
        total += k^{gcd(n, r)}
    return total / n

# D_n (회전 + 반사)
burnside_dihedral(n, k):
    total = burnside_necklace(n, k) * n   # 회전 기여
    # 반사 기여
    if n % 2 == 0:
        total += n/2 * (k^{n/2} + k^{n/2 + 1})
    else:
        total += n * k^{(n+1)/2}
    return total / (2*n)

구현

// Burnside's lemma: necklace counting
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll modpow(ll base, ll exp, ll mod) {
  ll res = 1;
  while (exp) {
      if (exp & 1) res = res * base % mod;
      base = base * base % mod;
      exp >>= 1;
  }
  return res;
}

int main() {
  // 회전만: necklace(n, k)
  int n, k; cin >> n >> k;
  ll total = 0;
  for (int r = 0; r < n; r++)
      total += modpow(k, gcd(n, r), LLONG_MAX);
  cout << "Necklace (rotation): " << total / n << "\n";

  // 반사 포함 (Dihedral group D_n)
  total = 0;
  for (int r = 0; r < n; r++)
      total += modpow(k, gcd(n, r), LLONG_MAX);
  if (n % 2 == 1) {
      total += n * modpow(k, (n + 1) / 2, LLONG_MAX);
  } else {
      total += n / 2 * modpow(k, n / 2, LLONG_MAX);
      total += n / 2 * modpow(k, n / 2 + 1, LLONG_MAX);
  }
  cout << "Necklace (dihedral): " << total / (2 * n) << "\n";
  return 0;
}

# Burnside's lemma: necklace counting
import math

def modpow(base, exp, mod):
  res = 1
  while exp:
      if exp & 1:
          res = res * base % mod
      base = base * base % mod
      exp >>= 1
  return res

n, k = map(int, input().split())

# rotation only
total = sum(k ** math.gcd(n, r) for r in range(n))
print(f"Necklace (rotation): {total // n}")

# dihedral (rotation + reflection)
total = sum(k ** math.gcd(n, r) for r in range(n))
if n % 2 == 1:
  total += n * k ** ((n + 1) // 2)
else:
  total += n // 2 * k ** (n // 2)
  total += n // 2 * k ** (n // 2 + 1)
print(f"Necklace (dihedral): {total // (2 * n)}")

import java.util.*;

public class Main {
  static long modpow(long base, long exp, long mod) {
      long res = 1;
      while (exp > 0) {
          if ((exp & 1) == 1) res = res * base % mod;
          base = base * base % mod;
          exp >>= 1;
      }
      return res;
  }

  static long gcd(long a, long b) {
      return b == 0 ? a : gcd(b, a % b);
  }

  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int k = sc.nextInt();

      long total = 0;
      for (int r = 0; r < n; r++)
          total += modpow(k, gcd(n, r), Long.MAX_VALUE);
      System.out.println("Necklace (rotation): " + total / n);

      total = 0;
      for (int r = 0; r < n; r++)
          total += modpow(k, gcd(n, r), Long.MAX_VALUE);
      if (n % 2 == 1) {
          total += n * modpow(k, (n + 1) / 2, Long.MAX_VALUE);
      } else {
          total += n / 2 * modpow(k, n / 2, Long.MAX_VALUE);
          total += n / 2 * modpow(k, n / 2 + 1, Long.MAX_VALUE);
      }
      System.out.println("Necklace (dihedral): " + total / (2 * n));
  }
}

stdin

4 2

결과

Necklace (rotation): 6
Necklace (dihedral): 6

복잡도

항목	값
회전만 (C_n)	O(n log k) (거듭제곱)
정다각형 (D_n)	O(n log k)
정육면체 면 색칠	O(1) (고정 24개 변환)

변형 / 활용

정육면체 면 색칠 (k 색)

회전군 크기 = 24. cube_faces(k) = (k^6 + 3*k^4 + 12*k^3 + 8*k^2) / 24. k=2 -> 10 가지.

응용 분야

목걸이/팔찌 색칠: C_n (회전) / D_n (회전+반사)
분자의 이성질체 계수: 화학에서 구조 이성질체 수
그래프 색칠 대칭: 군 작용 궤도 계산
Polya 열거 정리: 가중치 있는 색칠, 생성함수

함정

1. 단순 나누기

k^n / n 이 아닌 이유: 각 변환마다 고정점 개수가 다르다.

2. 반사 대칭 누락

홀수/짝수 n 에 따라 반사축 구조가 다름. 항상 케이스 분기 필요.

3. mod 나눗셈

mod p 에서 |G| 로 나눌 때 modular inverse 사용. p 가 |G| 와 서로소인지 확인.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 9817	Necklace of Beads	73.0%	kokoa-lab
BOJ 12748	색칠 공부 (Large)	65.6%	kokoa-lab
BOJ 18567	Kaleidoscope	88.9%	kokoa-lab

참고

조합론