번사이드 정리(Burnside's Lemma)는 유한군의 작용에 의해 변하지 않는 대상의 개수를 세는 데 사용되는 조합론의 정리이다. 때때로 "코시-프로베니우스 정리(Cauchy-Frobenius Lemma)"라고도 불린다. 이 정리는 군론의 기본 개념을 활용하여, 직접 계산하기 어려운 경우의 수를 효과적으로 구할 수 있게 해준다.
정의
G를 유한군, X를 유한 집합이라고 하자. G가 X에 작용한다고 할 때, 다음이 성립한다.
|X/G| = (1/|G|) * Σ |Xg|
여기서 |X/G|는 G의 작용에 의한 X의 궤도의 개수를 나타내며, Xg는 g에 의해 고정되는 X의 원소들의 집합, 즉 Xg = {x ∈ X | g.x = x}를 나타낸다. Σ는 G의 모든 원소 g에 대한 합을 의미한다.
설명
번사이드 정리는 주어진 군 G의 각 원소 g에 대해, g에 의해 고정되는 대상의 개수를 모두 더한 후, 군 G의 크기로 나누면 G의 작용에 의해 구별되지 않는 대상의 종류 수를 얻을 수 있다는 것을 의미한다. 즉, 중복되는 경우를 제외하고 실질적으로 서로 다른 경우의 수를 계산하는 데 유용하다.
활용 예시
- 정다면체 칠하기: 정육면체의 각 면을 서로 다른 색으로 칠하는 경우의 수를 계산할 때, 회전 변환에 의해 동일하게 보이는 경우를 제외하고 실제 서로 다른 색칠 방법의 수를 구할 수 있다.
- 목걸이 만들기: 여러 개의 구슬을 연결하여 목걸이를 만들 때, 회전 및 뒤집기에 의해 동일하게 보이는 경우를 제외하고 서로 다른 목걸이의 종류 수를 계산할 수 있다.
- 그래프 동형: 두 그래프가 동형인지 판별하는 문제에서, 번사이드 정리를 활용하여 그래프의 자기 동형사상의 수를 계산하고 이를 통해 동형인 그래프의 수를 셀 수 있다.
주의 사항
번사이드 정리를 적용하기 위해서는 군 G의 작용과 각 원소 g에 의해 고정되는 대상의 개수를 정확하게 파악해야 한다. G의 크기가 크거나 작용이 복잡한 경우, 각 항을 계산하는 것이 어려울 수 있다.