번사이드 보조 정리

첫 번째 주의 AlgoShitPo에서 ahgus89의 지목을 받아 Burnside’s Lemma를 작성하게 된 justiceHui입니다.

서론

번사이드 보조 정리는 원순열 등의 경우의 수를 구하는 문제에서 자주 나오는 정리입니다. 공부하기 위해 책을 보거나 검색을 하면, $\displaystyle \frac {1}{n}\sum_{k=1}^{n} c(k)$같은 공식만 나와있거나 Group Theory가 튀어나오는 경우가 대부분입니다.

저는 고등학교에 재학중인 학생으로써, 고등학교 수준에 맞춰 번사이드 보조 정리의 아이디어를 소개하는 것에 초점을 맞추도록 하겠습니다.

문제 1

위 그림처럼 구슬 4개로 구성된 목걸이가 있을 때, 각 구슬을 빨간색 혹은 파란색으로 색칠하는 경우의 수를 구해봅시다. 단, 회전시켰을 때 같은 색 조합은 같은 것으로 취급합니다.

모든 경우를 다 구해보면 6가지인 것을 쉽게 알 수 있습니다.
N개의 구슬, M개의 색깔에서 답을 구하고 싶은데 N과 M이 크다면? 당연히 모든 경우를 다 볼 수가 없겠죠. 규칙을 찾던가, 아니면 공식을 찾아야합니다.

구슬이 4개, 색깔이 2개라면 목걸이의 구슬을 색칠하는 경우는 총 $2^4 = 16$입니다. 구슬이 4개라면 목걸이를 시계 방향으로 0번, 1번, 2번, 3번 회전시킬 수 있습니다. 16가지 경우를 회전 횟수에 따라 표로 작성해봅시다.

이렇게 보면 알 수 있는 점은, RBBB / BRBB / BBRB / BBBR은 회전시켰을 때 같고, 같은 이유로 RRBB BRRB BBRR RBBR과 RBBB / BRBB / BBRB / BBBR도 회전시켰을 때 같기 때문에 4로 나누어야 합니다.
또한 RBRB / BRBR도 같기 때문에 2로 나누어야 합니다.

재미있는 아이디어를 하나 생각해봅시다.

아이디어

??? : 재밌는 상상을 한 번 해보자고. 이렇게 나누어야 할 수를 말이야, 굳이 계산할 필요가 있을까?

1로 나누어야 하는 경우는 4번 카운팅하고, 2로 나누어야 하는 경우는 2번 카운팅 한 다음 다 같이 4로 나누면 되지 않을까요? 위에서 작성했던 테이블을 약간 수정해봅시다.

이렇게 테이블을 꽉 채워준 다음에 4로 나눠도 똑같습니다. 번사이드 보조 정리는 이런 아이디어를 사용합니다.

RRRR과 BBBB는 원래 카운팅 해야하는 것보다 3번 더 카운팅했습니다. 그 이유는 1번, 2번, 3번 회전했을 때도 같기 때문입니다.
같은 이유로, RBRB와 BRBR은 각각 1번 더 카운팅했습니다.

이렇게 추가로 몇 개를 더 카운팅하는 것을 편하게 할 수 있는 똑똑한 방법이 있습니다.
0번 회전했을 때 처음과 같은 경우, 1번 회전했을 때 처음과 같은 경우, 2번 회전했을 때 처음과 같은 경우, 3번 회전했을 때 처음과 같은 경우를 각각 모두 카운팅해주면 됩니다.

RRRR의 경우 1번, 2번, 3번 회전해도 처음과 같기 때문에 3번 추가로 카운팅하게 됩니다.
비슷하게, RBRB와 BRBR은 각각 2번 회전했을 때 처음과 같기 때문에 1번씩 추가로 카운팅합니다.

전부 카운팅을 한 뒤 4로 나눠주면 됩니다.

공식

서론에서 잠깐 언급한, $\displaystyle \frac {1}{n}\sum_{k=1}^{n} c(k)$ 식을 다시 봅시다.
$c(k)$는 k방법으로 배정했을 때 처음과 같은 경우라고 하면, 위에서 말한 목걸이 문제의 답을 구하는 것과 똑같아집니다. 목걸이 문제에서의 k방법은 k번 회전을 의미하겠죠. 당연히 n은 배정하는 방법의 수를 의미합니다.

문제 2

구슬 N개, 색깔 M개를 이용해 목걸이를 색칠하는 경우의 수를 구하는 것으로 글을 끝내도록 하겠습니다.
당연히 M개의 색깔을 모두 쓸 필요는 없고, 회전했을 때 같은 색 조합은 같은 경우로 취급합니다.

k번 회전시켰을 때 처음과 같아진다는 것은, 목걸이의 구슬들의 색깔이 $gcd(N, k)$를 주기로 같다는 것을 의미합니다. 그러므로 $c(k) = M^{gcd(N, k)}$라는 것을 쉽게 알 수 있습니다.

결국, 구슬 N개와 색깔 M개를 이용해 목걸이를 색칠하는 경우의 수는 $\displaystyle \frac {1}{N}\sum_{k=1}^{N} c(k) = \frac {1}{N} \sum _{k=1}^{N} M^{gcd(N, k)}$입니다.

문제 3

문제 2를 조금 바꿔서, 임의의 축을 기준으로 대칭했을 때 같은 색 조합도 같은 경우로 취급하는 문제를 풀어봅시다.

배정하는 방법은 뒤집지 않고 돌리기만 하는 방법 N가지와 뒤집은 다음 돌리는 N가지, 총 2N가지가 있습니다.
뒤집지 않고 돌리기만 하는 것은 위에서 다룬 것처럼 k번 회전했을 때 각각 $M^{gcd(N, k)}$입니다. 뒤집은 다음 회전하는 경우를 생각해봅시다.

N이 홀수인 경우에는 한 개의 구슬의 색은 상관이 없고, 나머지는 대칭이 되어야 합니다. $N \times M^{(N+1)/2}$가 됩니다.

N이 짝수인 경우에는 회전 횟수 k가 홀수, 짝수인 경우를 각각 나눠서 봐야 합니다.
홀수 번 회전한 경우에는 두 개의 구슬은 원래 자리로 돌아오기 때문에 축처럼 생각해줄 수 있고, 반대의 경우에는 모든 원소가 짝을 이룹니다. $\frac {N}{2} \times (M^{N/2}+M^{N/2+1})$가 됩니다.

다 더하고 방법의 개수 2N으로 나눠주면 됩니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll pw(ll a, ll b){
	ll ret = 1;
	while(b){
		if(b & 1) ret *= a;
		b >>= 1; a *= a;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	while(1){
		ll n, m; cin >> m >> n;
		if(n == 0) break;
		
		ll ans = 0;
		for(ll i=0; i<n; i++) ans += pw(m, __gcd(n, i));
		if(n & 1) ans += n * pw(m, n + 1 >> 1);
		else ans += n/2 * (pw(m, n/2) + pw(m, n/2+1));
		cout << ans / 2 / n << "\n";
	}
}

2020-02-09 00:00