포여 열거 정리

포여 열거 정리(Pólya enumeration theorem) 또는 폴리아 열거 정리는 번사이드 보조정리의 일반화로 생각할 수 있는 조합론의 정리이다. 헝가리 수학자 포여 죄르지(Pólya György)의 이름이 붙어 있다.

간단한 형태의 포여 열거 정리

치환군 G가 n개의 개체에 작용한다고 하고, 이 개체들로 이루어진 구조들을 생각하자. 포여 열거 정리는 G의 작용에 관해 불변인 구조들의 개수를 계산하는 데 사용되는 생성함수를 구하는 방법을 기술하며, 그 생성함수는

$P_G(\sum_{i=1}^{m} c_i, \sum_{i=1}^{m} {c_i}^2 , \ldots, \sum_{i=1}^{m} {c_i}^n)$

이다. 여기에서 다항식 $P_G(x_1, x_2, ..., x_n)$ 은 $\frac{1}{|G|} \sum_{\pi\in G} x_1^{l_1(\pi)} x_2^{l_2(\pi)} \cdots x_n^{l_n(\pi)}$ 이며 $l_i(\pi)$는 $\pi$의 순환치환 표현에서 길이 i인 순환치환의 개수를 뜻한다. 또한 변수 $c_i, i = 1,2, \ldots, m$ 는 각 개체가 독립적으로 가질 수 있는 속성을 표현한다.

위의 다항식은 결과적으로 $c_i$들의 다항식이며 $c_i^{\alpha} c_j^{\beta} \cdots c_k^{\gamma}$의 계수는 속성 $c_i$를 가진 개체 $\alpha$개, 속성 $c_j$를 가진 개체 $\beta$개, $\ldots$, 속성 $c_k$를 가진 개체 $\gamma$개로 이루어진 (G의 작용에 관해 불변인) 구조들의 개수이다.

예제

세 가지 색깔이 허용된 구슬 세 개로 이루어진 목걸이

회전만 허용할 때

이 예에서 $n=3$ 이고 구슬의 속성(색깔)은 $c_1, c_2, c_3$ 이다. 치환군 G의 원소를 항등원, 120도 회전, 240도 회전이라 하자. 즉, G는 위수 3인 순환군이다. 그러면 숫자 1,2,3 이 구슬을 의미한다고 할 때, 이들 원소의 순환치환 표현은 각각 $(1)(2)(3), (1 2 3), (1 3 2)$ 이므로, $P_G(x_1, x_2, x_3) = \frac{1}{|G|} (x_1 ^3 + x_3 + x_3)$ 이 된다. 포여 열거 정리에 의해 다음과 같은 생성함수를 얻는다.

$P_G((c_1 + c_2 + c_3)^3 + 2 (c_1^3 + c_2^3 + c_3^3)) = c_1^3 + c_1^2 c_2 + c_1^2 c_3 + c_1 c_2^2 + 2 c_1 c_2 c_3 + c_1 c_3^2 + c_2^3 + c_2^2 c_3 + c_2 c_3^2 + c_3^3$

예를 들어 $c_1^2 c_2$의 계수가 1이므로 $c_1$ 색깔의 구슬 두 개와 $c_2$ 색깔의 구슬 하나로 이루어진 목걸이의 개수는 하나이다. G가 회전 변환만을 포함하고 있기 때문에 세 개의 색깔 $c_1, c_2, c_3$ 을 가진 서로 다른 목걸이의 개수는 (하나가 아니라) 두개이다.

계수들의 총 합이 11이므로 총 11개의 서로 다른 목걸이들이 있다.

모든 종류의 변환을 허용할 때

이 경우 앞선 예의 세 가지 회전 변환에 세 가지 뒤집는 변환을 더한 대칭군 $H = S_3$을 사용한다.

각각의 뒤집는 변환이 길이 1과 길이 2인 순환치환 두 개로 표현되므로 $P_G(x_1, x_2, x_3) = \frac{1}{|H|} (x_1 ^3 + 2 x_3 + 3 x_1 x_2)$ 을 얻는다. 따라서,

$P_G((c_1 + c_2 + c_3)^3 + 2 (c_1^3 + c_2^3 + c_3^3) + 3 (c_1 + c_2 + c_3)(c_1^2 + c_2^2 + c_3^2)) = c_1^3 + c_1^2 c_2 + c_1^2 c_3 + c_1 c_2^2 + c_1 c_2 c_3 + c_1 c_3^2 + c_2^3 + c_2^2 c_3 + c_2 c_3^2 + c_3^3$

이 경우 세 개의 색깔 $c_1, c_2, c_3$ 을 가진 서로 다른 목걸이의 개수는 하나가 되고 총 10개의 서로 다른 목걸이들이 있게 된다.