포여 열거 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

간단한 형태의 포여 열거 정리[편집]

치환군 Gn개의 개체에 작용한다고 하고, 이 개체들로 이루어진 구조들을 생각하자. 포여 열거 정리는 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개의 서로 다른 목걸이들이 있게 된다.