Burnside 보조정리 / Pólya 열거 정리¶

Burnside 보조정리¶

Burnside 보조정리는 1897년 Burnside가 정식화하고 증명했지만, 역사적으로는 이미 1887년에 Frobenius가, 그보다 앞선 1845년에는 Cauchy가 발견했습니다. 그래서 이 보조정리는 Cauchy-Frobenius 보조정리라고 불리기도 합니다.

Burnside 보조정리를 이용하면 내부 대칭성을 바탕으로 집합의 동치류 개수를 셀 수 있습니다.

대상과 표현¶

대상의 개수와 표현의 개수는 명확히 구분해야 합니다.

서로 다른 표현이 같은 대상에 대응할 수 있지만, 당연히 모든 표현은 정확히 하나의 대상에 대응합니다. 따라서 모든 표현의 집합은 동치류들로 나뉩니다. 우리가 할 일은 대상의 개수, 즉 동치류의 개수를 구하는 것입니다. 다음 예제를 보면 대상과 표현의 차이가 더 분명해질 것입니다.

예제: 이진 트리 색칠하기¶

다음과 같은 문제가 있다고 가정합시다. 정점 $n$개로 이루어진 루트 있는 이진 트리를 두 가지 색으로 칠하는 방법의 수를 세어야 하며, 이때 각 정점에서 왼쪽 자식과 오른쪽 자식은 구분하지 않습니다.

여기서 대상의 집합은 트리의 서로 다른 색칠 방법의 집합입니다.

이제 표현의 집합을 정의합니다. 색칠의 표현은 각 정점에 색을 하나씩 배정하는 함수 $f(v)$입니다(여기서는 색 $0$과 $1$을 사용합니다). 표현의 집합은 이러한 형태의 가능한 모든 함수를 담은 집합이며, 그 크기는 당연히 $2^n$입니다.

동시에 이 집합을 동치류들로 분할합니다.

예를 들어 $n = 3$이고, 트리가 루트 $1$과 그 두 자식 $2$, $3$으로 이루어져 있다고 가정합시다. 그러면 다음 함수 $f_1$과 $f_2$는 동치로 간주됩니다.

$$\begin{array}{ll} f_1(1) = 0 & f_2(1) = 0\\ f_1(2) = 1 & f_2(2) = 0\\ f_1(3) = 0 & f_2(3) = 1 \end{array}$$

불변 순열¶

두 함수 $f_1$과 $f_2$는 왜 같은 동치류에 속합니까? 직관적으로는 쉽게 이해할 수 있습니다. 정점 $1$의 자식인 정점 $2$와 $3$의 순서를 바꿀 수 있고, 함수 $f_1$에 이러한 변환을 적용하면 $f_2$와 일치하게 됩니다.

그러나 엄밀하게 말하면 이는 다음을 만족하는 불변 순열 $\pi$(즉, 대상 자체는 바꾸지 않고 그 표현만 바꾸는 순열)가 존재한다는 뜻입니다.

$$f_2 \pi \equiv f_1$$

따라서 대상의 정의에서 출발하여 모든 불변 순열, 즉 표현에 적용했을 때 대상을 바꾸지 않는 모든 순열을 찾을 수 있습니다. 그런 다음 각 불변 순열에 대해 조건 $f_2 \pi \equiv f_1$(또는 이와 동등한 $f_1 \pi \equiv f_2$)을 확인하여 두 함수 $f_1$과 $f_2$가 동치인지(즉, 같은 대상에 대응하는지) 판별할 수 있습니다. 조건을 만족하는 순열이 하나라도 발견되면 $f_1$과 $f_2$는 동치이고, 그렇지 않으면 동치가 아닙니다.

대상의 정의에 대하여 이러한 불변 순열을 모두 찾는 것은 Burnside 보조정리와 Pólya 열거 정리를 적용하는 데 모두 핵심적인 단계입니다. 이러한 불변 순열이 구체적인 문제에 따라 달라진다는 것은 분명하며, 이를 찾는 것은 직관적인 고찰에 기반한 순수한 휴리스틱 과정입니다. 그러나 대부분의 경우 몇 개의 "기본" 순열만 직접 찾으면 충분하며, 이들로부터 나머지 모든 순열을 생성할 수 있습니다(그리고 이 부분의 작업은 컴퓨터에 맡길 수 있습니다).

불변 순열들의 곱(합성)은 다시 불변 순열이 되므로, 불변 순열들이 군을 이룬다는 것은 어렵지 않게 이해할 수 있습니다. 불변 순열의 군을 $G$로 나타냅니다.

보조정리의 내용¶

보조정리를 서술하려면 대수학의 정의가 하나 더 필요합니다. 순열 $\pi$에 대한 고정점 $f$는 이 순열에 대해 불변인 원소입니다: $f \equiv f \pi$. 예를 들어 우리 예시에서 고정점은 순열 $\pi$를 적용해도 변하지 않는 색칠에 대응하는 함수 $f$들입니다(즉, 함수의 상등이라는 형식적인 의미에서 변하지 않는 것입니다). 순열 $\pi$에 대한 고정점의 개수를 $I(\pi)$로 나타냅니다.

그러면 Burnside 보조정리는 다음과 같습니다. 동치류의 개수는 군 $G$의 모든 순열 각각에 대한 고정점 개수의 합을 이 군의 크기로 나눈 값과 같습니다.

$$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} I(\pi)$$

Burnside 보조정리 자체는 실제로 사용하기에 그다지 편리하지 않지만(값 $I(\pi)$를 빠르게 구하는 방법이 분명하지 않습니다), 동치류의 개수를 계산하는 아이디어의 바탕이 되는 수학적 본질을 가장 명확하게 드러냅니다.

Burnside 보조정리의 증명¶

여기에서 설명하는 Burnside 보조정리의 증명은 실제 응용에서는 중요하지 않으므로 처음 읽을 때는 건너뛰어도 됩니다.

여기의 증명은 알려진 것 중 가장 간단하며, 군론을 사용하지 않습니다. 이 증명은 1991년에 Kenneth P. Bogart가 발표했습니다.

다음 명제를 증명해야 합니다:

$$|\text{Classes}| \cdot |G| = \sum_{\pi \in G} I(\pi)$$

우변의 값은 다름 아닌 "불변 쌍" $(f, \pi)$의 개수, 즉 $f \pi \equiv f$를 만족하는 쌍의 개수입니다. 합의 순서를 바꿀 수 있다는 것은 자명합니다. 합이 모든 원소 $f$를 순회하도록 하여, 값 $J(f)$ - $f$가 고정점이 되는 순열의 개수 - 들을 더합니다.

$$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

이 공식을 증명하기 위해, 열에는 모든 함수 $f_i$를, 행에는 모든 순열 $\pi_j$를 레이블로 붙인 표를 만들겠습니다. 그리고 각 칸을 $f_i \pi_j$로 채웁니다. 이 표의 열들을 집합으로 보면 그중 일부는 서로 일치하게 되며, 이는 그 열들에 대응하는 함수 $f$들 역시 동치라는 뜻입니다. 따라서 (집합으로서) 서로 다른 열의 개수는 동치류의 개수와 같습니다. 덧붙여 군론의 관점에서 보면, $f_i$로 레이블이 붙은 열은 이 원소의 궤도입니다. 동치인 원소들은 궤도가 일치하며, 궤도의 개수가 정확히 동치류의 개수가 됩니다.

따라서 표의 열들은 동치류별로 나뉩니다. 동치류 하나를 고정하고, 그 안의 열들을 살펴봅시다. 첫째, 이 열들에는 해당 동치류의 원소 $f_i$만 들어갈 수 있다는 점에 주목하십시오(그렇지 않다면 어떤 순열 $\pi_j$가 함수 중 하나를 다른 동치류로 옮긴 것인데, 우리는 불변 순열만 살펴보고 있으므로 이는 불가능합니다). 둘째, 각 원소 $f_i$는 각 열에서 같은 횟수만큼 나타납니다(이 역시 열들이 동치인 원소에 대응한다는 사실로부터 따라 나옵니다). 이로부터 같은 동치류에 속한 모든 열은 중복집합으로서 서로 일치한다는 결론을 내릴 수 있습니다.

이제 임의의 원소 $f$를 고정합니다. 한편으로, 이 원소는 (정의에 따라) 자신의 열에 정확히 $J(f)$번 나타납니다. 다른 한편으로, 같은 동치류에 속하는 모든 열은 다중집합으로서 서로 같습니다. 따라서 주어진 동치류의 각 열 안에서 임의의 원소 $g$는 정확히 $J(g)$번 나타납니다.

따라서 각 동치류에서 열을 하나씩 임의로 골라 그 안에 있는 원소의 개수를 모두 더하면, 한편으로는 (단순히 열의 개수에 행의 개수를 곱하여) $|\text{Classes}| \cdot |G|$를 얻고, 다른 한편으로는 모든 $f$에 대한 $J(f)$ 값들의 합을 얻습니다(이는 앞의 모든 논증으로부터 따라 나옵니다):

$$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

Pólya 열거 정리¶

Pólya 열거 정리는 Burnside 보조정리의 일반화이며, 동치류의 개수를 구하는 데 더 편리한 도구도 제공합니다. 이 정리는 Pólya보다 앞서 1927년에 Redfield가 이미 발견하였으나, 그의 논문은 수학자들의 주목을 받지 못했다는 점에 유의해야 합니다. Pólya는 1937년에 독립적으로 같은 결과에 도달하였으며, 그의 논문은 더 큰 성공을 거두었습니다.

여기서는 실제로 매우 유용한 것으로 드러날 Pólya 열거 정리의 특수한 경우만을 다룹니다. 이 정리의 일반적인 공식은 다루지 않습니다.

순열 $\pi$에 있는 사이클의 개수를 $C(\pi)$로 나타냅니다. 그러면 다음 공식(Pólya 열거 정리의 특수한 경우)이 성립합니다:

$$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} k^{C(\pi)}$$

$k$는 표현의 각 원소가 가질 수 있는 값의 개수이며, 이진 트리를 색칠하는 경우에는 $k = 2$가 됩니다.

증명¶

이 공식은 Burnside 보조정리의 직접적인 귀결입니다. 이를 얻으려면 보조정리에 등장하는 $I(\pi)$에 대한 명시적인 식을 찾기만 하면 됩니다. $I(\pi)$는 순열 $\pi$의 고정점의 개수라는 것을 상기하십시오.

따라서 순열 $\pi$와 어떤 원소 $f$를 생각해 봅시다. $\pi$를 적용하는 동안 $f$의 원소들은 순열의 사이클을 따라 이동합니다. 결과가 $f \equiv f \pi$를 만족해야 하므로, 하나의 사이클에 속한 원소들은 모두 같아야 합니다. 동시에 서로 다른 사이클들은 서로 독립적입니다. 따라서 순열 $\pi$의 각 사이클마다 ($k$가지 가능한 값 중) 하나의 값을 선택할 수 있으며, 이로써 고정점의 개수를 얻습니다:

$$I(\pi) = k^{C(\pi)}$$

응용: 목걸이 색칠하기¶

"목걸이" 문제는 고전적인 조합론 문제 중 하나입니다. 이 문제는 각각 $k$가지 색 중 하나로 칠할 수 있는 $n$개의 구슬로 만들 수 있는 서로 다른 목걸이의 개수를 세는 것입니다. 두 목걸이를 비교할 때 회전은 할 수 있지만 뒤집을 수는 없습니다(즉, 순환 이동이 허용됩니다).

이 문제에서는 불변 순열의 군을 바로 구할 수 있습니다:

$$\begin{align} \pi_0 &= 1 2 3 \dots n\\ \pi_1 &= 2 3 \dots n 1\\ \pi_2 &= 3 \dots n 12\\ &\dots\\ \pi_{n-1} &= n 1 2 3\dots\end{align}$$

$C(\pi_i)$를 계산하는 명시적인 공식을 찾아봅시다. 먼저, 순열 $\pi_i$의 $j$번째 위치에는 값 $i + j$($n$에 대한 나머지)가 있다는 점에 주목합니다. $\pi_i$의 사이클 구조를 확인해 봅시다. $1$은 $1 + i$로 가고, $1 + i$는 $1 + 2i$로 가며, 이는 다시 $1 + 3i$로 가는 식으로 $1 + k n$ 꼴의 수에 도달할 때까지 계속됨을 알 수 있습니다. 나머지 원소들에 대해서도 비슷한 논의를 할 수 있습니다. 따라서 모든 사이클의 길이가 $\frac{\text{lcm}(i, n)}{i} = \frac{n}{\gcd(i, n)}$으로 같음을 알 수 있습니다. 그러므로 $\pi_i$의 사이클 개수는 $\gcd(i, n)$과 같습니다.

이 값들을 Pólya 열거 정리에 대입하면 다음과 같은 해를 얻습니다.

$$\frac{1}{n} \sum_{i=1}^n k^{\gcd(i, n)}$$

이 공식을 이 형태 그대로 두어도 되고, 더 간단하게 정리할 수도 있습니다. 합이 $n$의 모든 약수에 대해 순회하도록 바꾸어 봅시다. 원래의 합에는 같은 항이 많이 나타납니다. $i$가 $n$의 약수가 아니라면, $\gcd(i, n)$을 계산하여 그러한 약수를 찾을 수 있습니다. 따라서 각 약수 $d ~|~ n$에 대해 그 항 $k^{\gcd(d, n)} = k^d$가 합에 여러 번 나타나며, 즉 문제의 답은 다음과 같이 다시 쓸 수 있습니다.

$$\frac{1}{n} \sum_{d ~|~ n} C_d k^d,$$

여기서 $C_d$는 $\gcd(i, n) = d$를 만족하는 수 $i$의 개수입니다. 이 값에 대한 명시적인 식을 구할 수 있습니다. 그러한 수 $i$는 모두 $\gcd(j, n / d) = 1$인 $i = d j$ 꼴입니다(그렇지 않으면 $\gcd(i, n) > d$가 됩니다). 따라서 이러한 성질을 갖는 $j$의 개수를 세면 됩니다. 오일러 피 함수를 이용하면 $C_d = \phi(n / d)$라는 결과를 얻으며, 따라서 다음과 같은 답을 얻습니다:

$$\frac{1}{n} \sum_{d ~|~ n} \phi\left(\frac{n}{d}\right) k^d$$

응용: 토러스 색칠하기¶

동치류의 개수에 대한 명시적인 공식을 얻을 수 없는 경우가 꽤 많습니다. 많은 문제에서 군에 속한 순열의 개수가 너무 많아 손으로 계산할 수 없으며, 각 순열의 사이클 개수를 해석적으로 계산하는 것도 불가능합니다.

이 경우에는 전체 군 $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 \dots m-1$, $i_2 = 0 \dots n-1$, $i_3 = 0 \dots 1$입니다.

따라서 이 문제에 대한 구현을 작성할 수 있습니다.

using Permutation = vector<int>;

void operator*=(Permutation& p, Permutation const& q) {
    Permutation copy = p;
    for (int i = 0; i < p.size(); i++)
        p[i] = copy[q[i]];
}

int count_cycles(Permutation p) {
    int cnt = 0;
    for (int i = 0; i < p.size(); i++) {
        if (p[i] != -1) {
            cnt++;
            for (int j = i; p[j] != -1;) {
                int next = p[j];
                p[j] = -1;
                j = next;
            }
        }
    }
    return cnt;
}

int solve(int n, int m) {
    Permutation 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);
    }

    set<Permutation> s;
    for (int i1 = 0; i1 < n; i1++) {
        for (int i2 = 0; i2 < m; i2++) {
            for (int i3 = 0; i3 < 2; i3++) {
                s.insert(p);
                p *= p3;
            }
            p *= p2;
        }
        p *= p1;
    }

    int sum = 0;
    for (Permutation const& p : s) {
        sum += 1 << count_cycles(p);
    }
    return sum / s.size();
}

Burnside 보조정리 / Pólya 열거 정리¶