위키득계정 ↗
과학

번사이드 보조정리

번사이드 보조정리과학
영어
Burnside’s lemma
다른 이름
Cauchy-Frobenius lemma
세는 대상
군 작용의 궤도 개수
계산 방법
각 군 원소의 고정점 수 평균
번사이드 보조정리는 대칭으로 같다고 보는 대상들의 종류 수를 고정점 개수의 평균으로 구하는 정리다. 유한군 G가 유한집합 X에 작용할 때 궤도 수는 (1/|G|)Σ₍g∈G₎|Fix(g)|이며 Fix(g)는 g를 적용해도 변하지 않는 원소들의 집합이다.

대칭으로 같은 대상 묶기

회전하여 겹쳐지는 색칠을 같은 것으로 본다면 여러 배치가 하나의 종류가 된다. 이처럼 허용한 변환으로 서로 이동할 수 있는 원소들의 묶음이 궤도다. 어떤 변환을 허용하는지에 따라 같은 종류로 보는 기준이 정해진다.

고정점이 뜻하는 것

색칠 문제에서 변환의 고정점은 그 변환을 적용해도 전체 색칠이 똑같이 남는 배치다. 도형의 꼭짓점 위치가 움직이지 않는다는 말과 다르다. 꼭짓점들이 서로 자리바꿈을 하더라도 같은 색을 지니고 있으면 전체 색칠은 변하지 않을 수 있다.

삼각형의 두 색칠

정삼각형의 세 꼭짓점을 두 색으로 칠하고 회전만 같다고 보자. 항등회전이 고정하는 배치는 2³=8개다. 120도와 240도 회전은 세 꼭짓점의 색이 모두 같아야 하므로 각각 2개를 고정한다. 따라서 종류 수는 (8+2+2)/3=4다.

그냥 나누면 안 되는 이유

대칭 개수로 전체 배치 수를 단순히 나누면 모든 궤도의 크기가 같다고 가정하게 된다. 앞의 예에서 한 색으로만 칠한 배치는 회전해도 하나뿐이므로 다른 배치와 궤도 크기가 다르다. 또한 회전만 허용하는 문제와 뒤집기까지 허용하는 문제는 사용하는 군이 달라질 수 있으므로 조건을 먼저 정해야 한다.

관련 문서

집합 / 순열 / 동치류 / 고정점 / 경우의 수 / 원순열