이 보조정리는 1897년에 번사이드(Burnside)가 정식화하고 증명하였으나, 이 공식은 그보다 앞서 1887년에 프로베니우스(Frobenius)가, 그리고 더 이전인 1845년에 코시(Cauchy)가 이미 발견했다는 사실이 밝혀졌습니다. 그래서 이 공식은 번사이드 보조정리라고 불리기도 하고, 코시-프로베니우스 정리라고 불리기도 합니다.
번사이드 보조정리를 사용하면 어떤 집합이 가진 내부 대칭성을 바탕으로 그 집합의 동치류 개수를 셀 수 있습니다.
객체와 표현 객체의 수와 표현의 수 사이에 명확한 경계를 그어 봅시다.
같은 대상에 서로 다른 표현이 대응될 수 있지만, 당연히 모든 표현은 정확히 하나의 대상에 대응합니다. 따라서 모든 표현의 집합은 동치류로 분할됩니다. 우리의 과제는 바로 대상의 개수, 즉 동치류의 개수를 세는 것입니다.
문제 예시: 이진 트리 색칠하기 다음과 같은 문제를 생각해 봅시다. 각 정점에서 오른쪽 자식과 왼쪽 자식을 구별하지 않을 때, 정점이 n개인 루트 있는 이진 트리를 2가지 색으로 색칠하는 방법의 수를 구해야 합니다.
여기서 객체의 집합은 이러한 의미에서 서로 다른 트리 색칠들의 집합입니다.
이제 표현들의 집합을 정의합시다. 각 색칠에 그 색칠을 정의하는 함수 f(v)를 대응시킵니다. 여기서 v = 1 \ldots n이고 f(v)=0 \ldots 1입니다. 그러면 표현들의 집합은 이러한 형태의 서로 다른 함수들의 집합이며, 그 크기는 자명하게 2^n입니다. 한편, 우리는 이 표현들의 집합 위에 동치류로의 분할을 도입하였습니다.
예를 들어, n=3이고 트리가 다음과 같다고 합시다. 루트는 정점 1이고, 정점 2와 3은 그 자식입니다. 그러면 다음 함수 f_1과 f_2는 동등한 것으로 간주됩니다.
\matrix{ f_1(1)=0 & f_2(1)=0 \cr f_1(2)=1 & f_2[…]
불변 순열 왜 이 두 함수 f_1과 f_2는 같은 동치류에 속합니까? 직관적으로는 이해할 수 있습니다. 정점 1의 자식들, 즉 정점 2와 3의 위치를 서로 바꿀 수 있고, 이러한 변환을 거치면 함수 f_1과 f_2가 일치하기 때문입니다. 그러나 형식적으로 이는 다음을 만족하는 불변 순열 \pi(즉, 문제의 조건에 따라 대상 자체는 바꾸지 않고 그 표현만 바꾸는 순열)가 존재한다는 것을 의미합니다.
f_2 \pi \equiv f_1
이처럼 문제의 조건으로부터 모든 불변 순열, 즉 적용해도 한 동치류에서 다른 동치류로 넘어가지 않는 순열을 찾을 수 있습니다. 그러면 두 함수 f_1과 f_2가 동치인지(즉, 실제로 같은 대상에 해당하는지) 확인하려면, 각 불변 순열 \pi에 대해 조건 f_2 \pi \equiv f_1(또는 같은 의미로 f_1 \pi \equiv f_2)이 성립하는지 확인해야 합니다. 적어도 하나의 순열에 대해 이 등식이 성립하면 f_1과 f_2는 동치이고, 그렇지 않으면 동치가 아닙니다.
우리 문제가 불변이 되는 이러한 불변 순열을 모두 찾는 것은 번사이드 보조정리와 포여 정리를 적용하기 위한 핵심 단계입니다. 이러한 불변 순열은 구체적인 문제에 따라 달라지며, 이를 찾는 과정은 직관적인 고려에 기반한 순전히 휴리스틱한 과정임이 분명합니다. 그러나 대부분의 경우에는 몇 개의 “기본” 순열을 직접 찾는 것으로 충분하며, 나머지 모든 순열은 이들의 가능한 모든 곱으로 얻을 수 있습니다(그리고 이 순전히 기계적인 작업은 컴퓨터에 맡길 수 있습니다. 이에 대해서는 아래에서 구체적인 문제를 예로 들어 더 자세히 살펴보겠습니다).
불변 순열들이 군을 이룬다는 것은 쉽게 알 수 있습니다. 임의의 불변 순열들의 곱 역시 불변 순열이기 때문입니다. 불변 순열들의 군을 G로 나타냅시다.
보조정리의 서술 서술을 위해 대수학의 개념 하나를 상기하는 일만 남았습니다. 순열 \pi에 대한 고정점 f란 이 순열에 대해 불변인 원소, 즉 f \equiv f \pi를 만족하는 원소를 말합니다. 예를 들어, 우리의 예에서 고정점은 순열 \pi를 적용해도 변하지 않는(정확히는 두 함수가 같다는 형식적인 의미에서 변하지 않는) 색칠에 대응하는 함수 f들입니다. 순열 \pi에 대한 고정점의 개수를 I(\pi)로 나타냅시다.
그러면 번사이드 보조정리는 다음과 같습니다. 동치류의 개수는 군 G에 속한 모든 순열에 대한 고정점 개수의 합을 이 군의 크기로 나눈 값과 같습니다.
{\rm ClassesCount} = \frac{1}{|G|} \sum_{\pi \in […]
번사이드 보조정리 자체는 실제로 적용하기에 그리 편리하지 않지만(I(\pi) 값을 빠르게 구하는 방법이 아직 분명하지 않기 때문입니다), 동치류의 개수를 세는 아이디어가 기반으로 하는 수학적 본질을 가장 명확하게 드러냅니다.
번사이드 보조정리의 증명 여기에서 설명하는 번사이드 보조정리의 증명은 이 보조정리를 이해하고 실제로 적용하는 데 그다지 중요하지 않으므로, 처음 읽을 때는 건너뛰어도 됩니다.
여기서 소개하는 증명은 알려진 증명 중 가장 간단하며 군론을 사용하지 않습니다. 이 증명은 1991년에 보가트(Bogart)와 케네스(Kenneth)가 발표했습니다.
따라서 다음 명제를 증명해야 합니다:
{\rm ClassesCount} |G| = \sum_{\pi \in G} I(\pi)
오른쪽에 있는 값은 다름 아닌 “불변 쌍” (f, \pi)의 개수, 즉 f \pi \equiv f를 만족하는 쌍의 개수입니다. 공식에서 합의 순서를 바꿀 수 있음은 명백합니다. 즉, 바깥쪽 합을 원소 f에 대한 합으로 만들고, 그 안에 f가 불변이 되게 하는 순열의 개수인 J(f)를 두면 됩니다:
{\rm ClassesCount} |G| = \sum_{f} J(f)
이 공식을 증명하기 위해 표를 하나 만듭시다. 표의 열에는 모든 값 f_i를, 행에는 모든 순열 \pi_j를 붙이고, 표의 칸에는 곱 f_i \pi_j를 적습니다. 그러면 이 표의 열들을 집합으로 간주할 때 그중 일부는 서로 일치할 수 있으며, 이는 해당 열들에 대응하는 f들 역시 동치라는 것을 의미하게 됩니다. 따라서 집합으로서 서로 다른 열의 개수는 구하고자 하는 값 \rm ClassesCount와 같습니다. 덧붙여 말하자면, 군론의 관점에서 어떤 원소 f_i가 붙은 표의 열은 이 원소의 궤도입니다. 동치인 원소들의 궤도는 명백히 일치하며, 서로 다른 궤도의 개수가 바로 \rm ClassesCount가 됩니다.
이렇게 하여 표의 열들은 저절로 동치류로 나뉩니다. 이제 어떤 동치류 하나를 고정하고 그 안의 열들을 살펴봅시다. 첫째, 이 열들에는 하나의 동치류에 속하는 원소 f_i만 나타날 수 있습니다(그렇지 않다면 어떤 동치 변환 \pi_j에 의해 다른 동치류로 넘어갔다는 뜻이 되는데, 이는 불가능합니다). 둘째, 각 원소 f_i는 모든 열에서 같은 횟수만큼 나타납니다(이 역시 열들이 동치인 원소들에 대응한다는 사실에서 따라 나옵니다). 이로부터 하나의 동치류 안의 모든 열은 중복집합으로서 서로 일치한다는 결론을 내릴 수 있습니다.
이제 임의의 원소 f를 고정합시다. 한편으로, 이 원소는 자신의 열에 정확히 J(f)번 나타납니다(J(f)의 정의 자체에 의해). 다른 한편으로, 하나의 동치류 안에 있는 모든 열은 중복집합으로서 서로 같습니다. 따라서 주어진 동치류의 각 열 안에서 임의의 원소 g는 정확히 J(g)번 나타납니다.
따라서 각 동치류에서 열을 하나씩 임의로 골라 그 안의 원소 개수를 모두 더하면, 한편으로는 {\rm ClassesCount} |G|를 얻고(이는 열의 개수에 열의 크기를 곱하기만 하면 얻어집니다), 다른 한편으로는 모든 f에 대한 J(f) 값의 합을 얻습니다(이는 앞의 모든 논증에서 따라 나옵니다):
{\rm ClassesCount} |G| = \sum_{f} J(f)
이로써 증명이 끝났습니다.
포여 정리. 가장 단순한 형태 포여(Polya) 정리는 번사이드 보조정리를 일반화한 것으로, 동치류의 개수를 구하는 데 더 편리한 도구를 제공합니다. 포여보다 앞서 1927년에 레드필드(Redfield)가 이 정리를 발견하고 증명했지만, 그의 논문은 당시 수학자들의 주목을 받지 못했다는 점을 짚고 넘어가야 합니다. 포여는 1937년에 이르러서야 독립적으로 같은 결과에 도달했으며, 그의 논문은 더 큰 반향을 얻었습니다.
여기서는 포여 정리의 특수한 경우로 얻어지며, 실제 계산에 사용하기에 매우 편리한 공식을 살펴보겠습니다. 일반적인 포여 정리는 이 글에서 다루지 않습니다.
순열 \pi에 있는 사이클의 개수를 C(\pi)로 나타냅시다. 그러면 다음 공식(포여 정리의 특수한 경우)이 성립합니다:
{\rm ClassesCount} = \frac{1}{|G|} \sum_{\pi \in […]
여기서 k는 표현 f(v)의 각 원소가 가질 수 있는 값의 개수입니다. 예를 들어, 우리의 예제 문제(루트 있는 이진 트리를 2가지 색으로 칠하기)에서는 k = 2입니다.
증명 이 공식은 번사이드 보조정리의 직접적인 결과입니다. 이를 얻으려면 보조정리에 나오는 값 I(\pi)에 대한 명시적인 식을 찾기만 하면 됩니다(다시 말하면, 이는 순열 \pi의 고정점 개수입니다).
이제 어떤 순열 \pi와 어떤 원소 f를 생각해 봅시다. 잘 알려져 있듯이, 순열 \pi의 작용에 따라 f의 원소들은 순열의 사이클을 따라 이동합니다. 결과적으로 f \equiv f \pi가 성립해야 하므로, 순열의 각 사이클 안에는 같은 원소 f가 있어야 한다는 점에 주목하십시오. 한편, 서로 다른 사이클 사이에서는 원소의 값 사이에 아무런 관계도 생기지 않습니다. 따라서 순열 \pi의 각 사이클마다 하나의 값을 (k가지 중에서) 선택하면, 이 순열에 대해 불변인 f의 모든 표현을 얻게 됩니다. 즉:
I(\pi) = k ^ {C(\pi)}
여기서 C(\pi)는 순열의 사이클 개수입니다.
예시 문제: 목걸이 “목걸이” 문제는 고전적인 조합론 문제 중 하나입니다. 각 구슬을 k가지 색 중 하나로 칠할 수 있을 때, n개의 구슬로 이루어진 서로 다른 목걸이의 개수를 구해야 합니다. 두 목걸이를 비교할 때 회전은 할 수 있지만 뒤집을 수는 없습니다(즉, 순환 이동은 허용됩니다).
이 문제에서는 불변 순열의 군을 바로 찾을 수 있습니다. 분명히, 이 군은 n개의 순열로 이루어집니다:
\pi_0 = 1\ 2\ 3\ \ldots\ n \pi_1 = 2\ 3\ \ldots\ n\ 1 \pi_2 = 3\ \ldots\ n\ 1\ 2 \ldots \pi_{n-1} = n\ 1\ 2\ \ldots\ (n-1)
C(\pi_i)를 계산하는 명시적인 공식을 구해 봅시다. 먼저, 순열들은 i번째 순열의 j번째 위치에 i+j(n보다 크면 n을 법으로 취한 값)가 오는 형태임을 알 수 있습니다. i번째 순열의 순환 구조를 살펴보면, 1은 1+i로, 1+i는 1+2i로, 1+2i는 1+3i로 이동하며, 이런 식으로 수 1 + kn에 도달할 때까지 계속됩니다. 나머지 원소들에 대해서도 비슷한 사실이 성립합니다. 이로부터 모든 순환의 길이가 {\rm lcm}(i,n) / i, 즉 n / {\rm gcd}(i,n)으로 모두 같다는 것을 알 수 있습니다(“gcd"는 최대공약수, “lcm"은 최소공배수입니다). 그러면 i번째 순열의 순환 개수는 간단히 {\rm gcd}(i,n)이 됩니다.
구한 값들을 포여 정리에 대입하면, 다음과 같은 해를 얻습니다:
{\rm Ans} = \frac{1}{n} \sum_{i=1}^{n} k ^ {{\rm […]
공식을 이 형태로 둘 수도 있고, 더 간단하게 정리할 수도 있습니다. 모든 i에 대한 합에서 n의 약수에 대한 합으로 넘어갑시다. 실제로 이 합에는 같은 항이 많이 나타납니다. i가 n의 약수가 아니라면, {\rm gcd}(i,n)을 계산하면 그러한 약수를 얻게 됩니다. 따라서 각 약수 d|n에 대하여 그 항 k^{{\rm gcd}(d,n)} = k^d가 여러 번 더해지므로, 합을 다음과 같은 형태로 나타낼 수 있습니다:
{\rm Ans} = \frac{1}{n} \sum_{d|n} C_d k^d
여기서 C_d는 {\rm gcd}(i,n) = d를 만족하는 수 i의 개수입니다. 이 개수에 대한 명시적인 식을 구해 봅시다. 이러한 수 i는 모두 i=dj 꼴이며, 여기서 {\rm gcd}(j,n/d) = 1입니다(그렇지 않다면 {\rm gcd}(i,n) > d가 됩니다). 오일러 함수를 떠올리면, 이러한 j의 개수는 오일러 함수의 값 \phi(n/d)임을 알 수 있습니다. 따라서 C_d = \phi(n/d)이며, 최종적으로 다음 공식을 얻습니다:
{\rm Ans} = \frac{1}{n} \sum_{d|n} \phi \left( \f[…]
번사이드 보조정리와 프로그램 계산의 병용 순수하게 해석적인 방법만으로 동치류의 개수에 대한 명시적인 공식을 얻을 수 있는 경우는 결코 많지 않습니다. 많은 문제에서 군에 속하는 순열의 개수가 손으로 계산하기에는 너무 많을 수 있으며, 그 순열들의 사이클 개수를 해석적으로 계산하는 것은 불가능합니다.
이러한 경우에는 군 G 전체를 생성하기에 충분한 몇 개의 “기본” 순열을 손으로 찾아야 합니다. 그다음에는 군 G의 모든 순열을 생성하고, 각 순열의 사이클 개수를 센 뒤, 이를 공식에 대입하는 프로그램을 작성할 수 있습니다.
예로 토러스 색칠의 가짓수를 구하는 문제를 살펴봅시다. n \times m (n < m) 크기의 직사각형 모눈종이가 있고, 그중 일부 칸은 검은색으로 칠해져 있습니다. 그런 다음 이 종이의 길이가 m인 두 변을 이어 붙여 원기둥을 만듭니다. 이어서 원기둥의 두 원(원기둥의 밑면)을 비틀지 않고 이어 붙여 토러스를 만듭니다. 이어 붙인 선은 구별할 수 없고 토러스는 회전하거나 뒤집을 수 있다고 할 때, 서로 다른 토러스의 개수를 구해야 합니다(처음에 종이는 임의로 칠해져 있었습니다).
이 문제에서는 일부 칸이 검은색으로 칠해진 n \times m 크기의 종이를 표현으로 볼 수 있습니다. 다음과 같은 종류의 변환이 동치류를 보존한다는 것은 쉽게 알 수 있습니다: 종이의 행에 대한 순환 이동, 종이의 열에 대한 순환 이동, 종이를 180도 회전하는 것입니다. 또한 이 세 종류의 변환만으로 불변 변환의 군 전체를 생성하기에 충분하다는 것도 직관적으로 알 수 있습니다. 어떤 방식으로든 판의 칸에 번호를 매기면, 이 변환들에 대응하는 세 순열 p_1, p_2, p_3을 적을 수 있습니다. 이제 남은 일은 이 순열들의 곱으로 얻어지는 모든 순열을 생성하는 것뿐입니다. 이러한 순열은 모두 p_1^{i_1} p_2^{i_2} p_3^{i_3} 꼴이며, 여기서 i_1 = 0 \ldots m-1, i_2 = 0 \ldots n-1, i_3 = 0 \ldots 1이라는 것은 자명합니다.
따라서 이 문제의 풀이를 다음과 같이 구현할 수 있습니다:
void mult (vector
int cnt_cycles (vector
int main() { int n, m; cin » n » m;
vector<int> p (n*m), p1 (n*m), p2 (n*m), p3 (n*m);
for (int i=0; i<n*m; ++i) {
p[i] = i;
p1[i] = (i % n + 1) % n + i / n * n;
p2[i] = (i / n + 1) % m * n + i % n;
p3[i] = (m - 1 - i / n) * n + (n - 1 - i % n);
}
int sum = 0, cnt = 0;
set < vector<int> > s;
for (int i1=0; i1<n; ++i1) {
for (int i2=0; i2<m; ++i2) {
for (int i3=0; i3<2; ++i3) {
if (!s.count(p)) {
s.insert (p);
++cnt;
sum += 1 << cnt_cycles(p);
}
mult (p, p3);
}
mult (p, p2);
}
mult (p, p1);
}
cout << sum / cnt;
}
#목걸이
“목걸이” 문제는 고전적인 조합론 문제 중 하나입니다. n개의 구슬로 이루어진 서로 다른 목걸이의 개수를 세어야 하며, 각 구슬은 k가지 색 중 하나로 칠할 수 있습니다. 두 목걸이를 비교할 때 목걸이를 회전시킬 수는 있지만 뒤집을 수는 없습니다(즉, 순환 이동은 허용됩니다).
풀이 이 문제는 번사이드 보조정리와 포여 정리를 사용하여 풀 수 있습니다. [ 아래는 이 글의 텍스트를 그대로 옮긴 것입니다 ]
이 문제에서는 불변 순열의 군을 바로 찾을 수 있습니다. 명백히, 이 군은 n개의 순열로 이루어집니다.
\pi_0 = 1\ 2\ 3\ \ldots\ n \pi_1 = 2\ 3\ \ldots\ n\ 1 \pi_2 = 3\ \ldots\ n\ 1\ 2 \ldots \pi_{n-1} = n\ 1\ 2\ \ldots\ (n-1)
C(\pi_i)를 계산하는 명시적인 공식을 구해 봅시다. 먼저, 순열들은 i번째 순열의 j번째 위치에 i+j(n보다 크면 n을 법으로 취한 값)가 놓이는 형태임을 알 수 있습니다. i번째 순열의 순환 구조를 살펴보면, 1은 1+i로, 1+i는 1+2i로, 1+2i는 1+3i로 가는 식으로 이어지다가 1 + kn이라는 수에 도달함을 알 수 있습니다. 나머지 원소들에 대해서도 비슷한 사실이 성립합니다. 이로부터 모든 순환이 {\rm lcm}(i,n) / i, 즉 n / {\rm gcd}(i,n)와 같은 동일한 길이를 가진다는 것을 알 수 있습니다(“gcd"는 최대공약수, “lcm"은 최소공배수입니다). 따라서 i번째 순열의 순환 개수는 간단히 {\rm gcd}(i,n)와 같습니다.
구한 값들을 포여 정리에 대입하면 다음과 같은 해를 얻습니다:
{\rm Ans} = \frac{1}{n} \sum_{i=1}^{n} k ^ {{\rm […]
공식을 이대로 두어도 되지만, 더 간단하게 정리할 수도 있습니다. 모든 i에 대한 합을 n의 약수에 대한 합으로 바꾸어 봅시다. 실제로 이 합에는 같은 항이 여러 개 있습니다. i가 n의 약수가 아니더라도 {\rm gcd}(i,n)을 계산하면 n의 약수가 하나 얻어지기 때문입니다. 따라서 각 약수 d|n에 대해 그 항 k^{{\rm gcd}(d,n)} = k^d가 여러 번 더해지므로, 합을 다음과 같이 나타낼 수 있습니다:
{\rm Ans} = \frac{1}{n} \sum_{d|n} C_d k^d
여기서 C_d는 {\rm gcd}(i,n) = d를 만족하는 수 i의 개수입니다. 이 개수를 명시적으로 나타내는 식을 구해 봅시다. 이러한 수 i는 모두 i=dj 꼴이며, 여기서 {\rm gcd}(j,n/d) = 1입니다(그렇지 않으면 {\rm gcd}(i,n) > d가 됩니다). 오일러 함수를 떠올리면, 이러한 j의 개수는 오일러 함수의 값 \phi(n/d)임을 알 수 있습니다. 따라서 C_d = \phi(n/d)이며, 최종적으로 다음 공식을 얻습니다:
{\rm Ans} = \frac{1}{n} \sum_{d|n} \phi \left( \f[…]