포여 열거 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

포여 열거 정리(Pólya enumeration theorem)는 조합론에서 대칭성을 가진 대상의 수를 세는 데 사용되는 정리이다. 이 정리는 대상에 무게를 부여하는 함수와 대칭군을 활용하여 궤도의 무게를 계산하는 데 유용하며, 다중 지표, 무게 함수, 생성 함수 등의 개념을 포함한다. 포여 열거 정리는 유한군, 유한 집합, 작용, 궤도 등의 개념을 바탕으로 하며, 헝가리 수학자 포여 죄르지에 의해 개발되었다. 이 정리는 목걸이, 팔찌, 그래프, 트리, 색칠된 정육면체 등 다양한 문제에 적용될 수 있으며, 1937년 존 하워드 레드필드의 연구를 바탕으로 포여에 의해 완성되었다.

포여 열거 정리

📚 더 읽어볼만한 페이지

조합론 정리 - 세메레디의 정리
세메레디의 정리는 양의 상부 밀도를 갖는 자연수 부분집합이 임의 길이의 등차수열을 포함한다는 내용으로, 세메레디 엔드레가 증명하고 힐렐 퓌르스텐베르크가 다른 증명을 제시했으며, 반 데르 바르덴 정리의 일반화이자 그린-타오 정리와 연관된다.
조합론 정리 - 딜워스의 정리
딜워스의 정리는 부분 순서 집합의 너비와 사슬 분할의 최소 크기 간의 관계를 설명하며, 유한한 너비를 갖는 부분 순서 집합은 너비와 같은 수의 사슬로 분할될 수 있다고 말한다.
열거조합론 - 카탈랑 수
카탈랑 수는 조합론에서 여러 개수 세기 문제의 해답으로 나타나는 수열로, 괄호 구조, 이진 트리, 다각형 분할 등 다양한 조합론적 대상의 개수를 나타내며 여러 분야에 응용된다.
열거조합론 - 오일러 수 (조합론)
오일러 수는 조합론에서 집합의 순열 중 특정 조건을 만족하는 순열의 개수를 나타내는 수로, 주로 집합 <math>\{1,2,\ldots,n\}</math>의 순열에서 <math>a_i>a_{i+1}</math>인 <math>i</math>가 정확히 <math>m</math>개 있는 순열의 개수를 나타내며, 오일러 다항식 및 관련 성질과 함께 1755년 레온하르트 오일러에 의해 소개되었다.
대수학 정리 - 힐베르트 기저 정리
힐베르트 기저 정리는 가환환 R이 뇌터 환일 때 R을 계수로 하는 다항식환 R[x_1,...,x_n] 역시 뇌터 환임을 명시하는 정리이며, 대수기하학에서 대수적 집합을 유한 개의 다항식의 공통근으로 해석할 수 있게 한다.
대수학 정리 - 힐베르트 영점 정리
힐베르트 영점정리는 대수기하학에서 다항식환의 아이디얼과 대수적 집합 사이의 관계를 나타내는 중요한 정리로, 체 <math>k</math>와 그의 대수적 폐포 <math>K</math>에 대해, 다항식환 <math>k[x_1,x_2,\dots,x_n]</math>의 아이디얼 <math>J</math>의 영점들의 집합 <math>\mathcal V(J)</math>에 대하여, <math>\mathcal I(\mathcal V(J))=\sqrt J</math>가 성립한다는 것을 명시하며, 특히 <math>k</math>가 대수적으로 닫힌 체인 경우, 반소 아이디얼과 대수 집합 사이에 순서를 뒤집는 전단사 대응이 존재함을 의미한다.

1. 개요
2. 정의
- 2.1. 무게가 없는 경우의 열거 정리
- 2.2. 일반적 열거 정리
3. 코시-프로베니우스 보조정리 (번사이드 보조정리)
4. 예시
5. 역사

2. 정의

유한 집합 X와 X에 군 작용하는 유한 군 G가 주어졌을 때, X는 유한 개의 구슬을 나타내고, G는 구슬의 순열을 나타낸다고 생각할 수 있다. 예를 들어 X가 원형으로 배열된 n개의 구슬로 이루어진 목걸이라면 회전 대칭을 고려하여 G를 순환군 C_n으로, 팔찌라면 회전 및 반사 대칭을 고려하여 G를 이항군 D_n으로 잡을 수 있다.

구슬의 색깔을 나타내는 유한 집합 Y가 주어지면, $Y^X$ 는 색깔이 지정된 구슬 배열의 집합(또는 함수 $X \to Y$ 의 집합)을 나타낸다. 이때, 군 G는 $Y^X$ 에 작용하게 된다.

포여 열거 정리는 이러한 상황에서, 주어진 색깔 집합 Y와 군 G에 대해, 색깔이 지정된 구슬 배열들의 G에 대한 궤도의 개수를 계산하는 공식을 제공한다.

2.1. 무게가 없는 경우의 열거 정리

다음과 같은 데이터가 주어졌다고 하자.

* 유한군 $G$
* 유한 집합 $X$ . 그 원소를 구슬(bead^영어)이라고 한다.
* $G$ 의 $X$ 위의 왼쪽 충실한 작용
* 유한 집합 $Y$ . 그 원소를 색깔(color^영어)이라고 한다.

그렇다면 $G$ 는 함수 집합 $Y^X$ 위에도 역시 다음과 같이 왼쪽 작용을 갖는다.

: $g\cdot (y_x)_{x\in X}=(y_{g^{-1}\cdot x})_{x\in X}$

포여 열거 정리에 따르면, $Y^X$ 의 궤도의 수 $|Y^X/G|$ 는 다음과 같다.

: $|Y^X/G| = \frac1$

👆

좌우로 밀어서 보기

\sum_{g \in G} |Y|^{c(g)}

여기서
*

c(g)

는

g

를

X

위의 순열로 생각하였을 때 순환들의 수이다.

X

를 유한 집합이라고 하고,

G

를

X

의 순열 군(또는

X

에 군 작용하는 유한 대칭군)이라고 하자. 집합

X

는 유한 개의 구슬을 나타낼 수 있고,

G

는 구슬의 순열로 선택된 군이 될 수 있다. 예를 들어,

X

가 원형으로 배열된

n

개의 구슬로 이루어진 목걸이라면, 회전 대칭이 관련되므로

G

는 순환군

C_n

이 되고,

X

가 원형으로 배열된

n

개의 구슬로 이루어진 팔찌라면, 회전과 반사 대칭이 관련되므로

G

는 차수가

2n

인 이항군

D_n

이 된다. 또한,

Y

를 구슬의 색상인 유한 집합이라고 하자. 그러면

Y^X

는 색깔이 지정된 구슬 배열의 집합이 된다(더 정확히는,

Y^X

는 함수

X \to Y

의 집합이다). 그러면 군

G

는

Y^X

에 작용한다. 포여 열거 정리는 색깔이 지정된 구슬 배열의

G

에 대한 궤도 수를 다음과 같은 공식으로 계산한다.

:

\left |Y^X/G \right | = \frac{1}

👆

좌우로 밀어서 보기

\sum_{g \in G} m^{c(g)}

여기서

m=|Y|

는 색상의 개수이고,

c(g)

는 집합

X

의 순열로 간주될 때, 군 원소

g

의 순환 순열의 개수이다.

집합

D_1

위의 링 지수

P(x_1, x_2, \cdots, x_n)

를 갖는 치환군을 G라고 하자. D₁에서 D₂로의 사상 f, g에 대해

f(\pi(x))=g(x)

가 되는

\pi

가 존재하지 않을 때, f와 g는 다르다고 한다. 이때, D1에서 D2로의 서로 다른 것의 개수는

:

P(x_1, x_2, \cdots, x_n)=\frac{1}

👆

좌우로 밀어서 보기

\sum_{\pi \in G} |D_2|^{k(\pi)}

가 된다.

여기서,

|D_1|=n, |D_2|=m

이라고 하면,

|P(x_k)|=m^n

이 되고,

:

P(x_1, x_2, \cdots, x_n)=\frac{1}

👆

좌우로 밀어서 보기

\sum_{\pi \in G} |D_2|^{k(\pi)}=\frac{1}

👆

좌우로 밀어서 보기

\sum_{\pi \in G} m^{k(\pi)}
이다.

2.2. 일반적 열거 정리

다음과 같은 데이터가 주어졌다고 가정한다.

* 유한군 $G$
* 크기 $n$ 의 유한 집합 $X$ . 그 원소를 구슬(bead^영어)이라고 한다.
* $G$ 의 $X$ 위의 왼쪽 충실한 작용
* 각 다중지표 $\vec w\in\mathbb N^k$ 에 대하여, 유한 집합 $Y_{\vec w}$ . 그 원소를 무게 $\vec w$ 의 색깔(color of weight $\vec w$ ^영어)이라고 하고, $\textstyle Y=\bigsqcup_{\vec w\in\mathbb N^k}Y_{\vec w}$ 라고 한다. $Y$ 는 무한 집합일 수 있다. 즉, 무게 함수 $\vec w\colon Y\to\mathbb N^k$ 에 대하여 각 자연수의 원상은 유한 집합이다.

그렇다면, $G$ 는 함수 집합 $Y^X$ 위에 작용한다. 함수 $f\colon X\to Y$ 의 무게 $\vec W(f)\in\mathbb N^k$ 는 각 구슬의 색깔의 무게의 합이다.

: $\vec W(f)=\sum_{w\in\mathbb N}\sum_{x\in X}\vec w(f(x))$

다음과 같은 생성 함수를 정의한다.

: $F(y_1,\dots,y_k)=\sum_{\vec w\in\mathbb N^k} |W^{-1}(\{\vec w\})/G|x^{\vec w}$

여기서

: $y^{\vec w}=y_1^{w_1}y_2^{w_2}\cdots y_k^{w_k}$

이다. 즉, $F(y_1,\dots,y_k)$ 의 $y^{\vec w}$ 항의 계수는 $Y^X$ 속의 함수 가운데, 무게가 $\vec w$ 인 것들의 수이다. 또한, 다음과 같은 생성 함수를 정의한다.

: $C(y_1,\dots,y_k)=\sum_{\vec w\in\mathbb N^k} |Y_{\vec w}|y^{\vec w}$

즉, $C(y_1,\dots,y_k)$ 의 $y^{\vec w}$ 항의 계수는 무게가 $\vec w$ 인 색깔의 수이다.

포여 열거 정리에 따르면, 다음이 성립한다.

: $F(y_1,\dots,y_k)=Z_G\left(C(y_1,\dots,y_k),C(y_1^2,\dots,y_k^2),\dots,C(y_1^n,\dots,y_k^n)\right)$

좌변에서 $Z_G$ 는 순열군 $G$ 의 순환 지표이다. 즉, 계산하고자 하는 생성 함수 $F$ 는 순환 지표 $Z_G$ 의 특정한 값이다.

무게의 간단한 예로, 색깔 집합 $Y$ 가 유한 집합이며, 무게 집합은 $\mathbb N^y$ 이며, 색깔 $y\in Y$ 의 무게가

: $w(y)=(0,0,\dots,0,1,0,\dots,0)$

의 꼴이라고 잡을 수 있다. 이 경우, 생성 함수의 형식적 변수 $y_1,\dots,y_k$ 는 $Y$ 의 원소로 생각할 수 있다.

정리의 더 일반적이고 더 중요한 버전에서, 색상에는 하나 이상의 방식으로 가중치가 부여되며, 색상 집합이 유한 계수를 가진 생성 함수를 가지고 있다면 무한한 수의 색상이 있을 수 있다. 단변량의 경우, 다음을 가정한다.

: $f(t) = f_0 + f_1 t + f_2 t^2 + \cdots$

는 색상 집합의 생성 함수이므로, 각 정수 w ≥ 0에 대해 가중치 w의 f_w개의 색상이 있다. 다변량의 경우, 각 색상의 가중치는 정수 벡터이며, 각 주어진 가중치 벡터를 가진 색상의 수를 표로 나타내는 생성 함수 f(t₁, t₂, ...)가 있다.

열거 정리는 순환 지표라고 하는 또 다른 다변량 생성 함수를 사용한다.

: $Z_G(t_1,t_2,\ldots,t_n) = \frac{1}$

👆

좌우로 밀어서 보기

\sum_{g \in G} t_1^{c_1(g)} t_2^{c_2(g)} \cdots t_n^{c_n(g)}

여기서 n은 X의 요소 수이고, c_k(g)는 X의 순열로서의 그룹 요소 g의 k-사이클의 수이다.

색상 배열은 집합 Y^X에 대한 G의 작용의 궤도이다(여기서 Y는 색상 집합이고 Y^X는 모든 함수 φ: X→Y의 집합을 나타낸다). 이러한 배열의 가중치는 X의 모든 x에 대해 φ(x)의 가중치의 합으로 정의된다. 이 정리는 가중치에 따른 색상 배열의 수에 대한 생성 함수 F가 다음과 같이 주어진다고 명시한다.

:

F(t) = Z_G(f(t),f(t^2),f(t^3),\ldots,f(t^n))

또는 다변량의 경우:

:

F(t_1,t_2,\ldots) = Z_G(f(t_1,t_2,\ldots),f(t_1^2,t_2^2,\ldots),f(t_1^3,t_2^3,\ldots),\ldots,f(t_1^n,t_2^n,\ldots)).

앞서 주어진 단순화된 버전으로 축소하려면, m개의 색상이 있고 모두 가중치가 0인 경우 f(t) = m이며

:

\left |Y^X/G \right | =F(0)= Z_G(m,m,\ldots,m) = \frac{1}

👆

좌우로 밀어서 보기

\sum_{g \in G} m^{c(g)}.

집합

D_1

위의 링 지수

P(x_1, x_2, \cdots, x_n)

를 갖는 치환군을 G라고 한다. D₁에서 D₂로의 사상 f, g에 대해

f(\pi(x))=g(x)

가 되는

\pi

가 존재하지 않을 때, f와 g는 다르다고 한다. 이때, D1에서 D2로의 서로 다른 것의 개수는

:

P(x_1, x_2, \cdots, x_n)=\frac{1}

👆

좌우로 밀어서 보기

\sum_{\pi \in G} |D_2|^{k(\pi)}

가 된다.

여기서,

|D_1|=n, |D_2|=m

이라고 하면,

|P(x_k)|=m^n

이 되고,

:

P(x_1, x_2, \cdots, x_n)=\frac{1}

👆

좌우로 밀어서 보기

\sum_{\pi \in G} |D_2|^{k(\pi)}=\frac{1}

👆

좌우로 밀어서 보기

\sum_{\pi \in G} m^{k(\pi)}

이다.

3. 코시-프로베니우스 보조정리 (번사이드 보조정리)

포여 열거 정리의 단순화된 형태는 번사이드 보조정리에서 파생되며, 번사이드 보조정리는 색칠의 궤도 수는 모든 순열 g에 대해 G의 순열 g에 의해 고정된 $Y^X$ 의 원소 수의 평균이라고 말한다. 정리의 가중치 버전은 본질적으로 동일한 증명을 가지지만, 가중 열거를 위한 번사이드 보조정리의 개선된 형태를 사용한다. 이는 서로 다른 가중치의 궤도에 번사이드 보조정리를 개별적으로 적용하는 것과 동일하다.

더 명확한 표기를 위해 $x_1,x_2,\ldots$ 를 $Y$ 의 생성 함수 f의 변수라고 하자. 가중치 벡터 $\omega$ 가 주어지면, $x^\omega$ 는 f의 해당 단항식을 나타낸다. 번사이드 보조정리를 가중치 $\omega$ 의 궤도에 적용하면, 이 가중치의 궤도 수는 다음과 같다.

: $\frac{1}$

👆

좌우로 밀어서 보기

\sum_{g\in G} \left |(Y^X)_{\omega,g} \right |

여기서

(Y^X)_{\omega,g}

는 g에 의해서도 고정된 가중치

\omega

의 색칠 집합이다. 그런 다음 모든 가능한 가중치에 대해 합하면, 다음을 얻는다.

:

F(x_1,x_2,\ldots)= \frac{1}

👆

좌우로 밀어서 보기

\sum_{g \in G, \omega} x^\omega \left |(Y^X)_{\omega,g} \right |.

한편, 사이클 구조

j_1(g),j_2(g),\ldots,j_n(g)

를 가진 그룹 원소 g는 다음 항을 기여한다.

:

t_1^{j_1(g)} t_2^{j_2(g)} \cdots t_n^{j_n(g)}

G의 사이클 지수에. 원소 g는 함수 φ가 g의 모든 사이클 q에서 상수인 경우에만 원소

\phi \in Y^X

를 고정한다. 모든 이러한 사이클 q에 대해, f에 의해 열거된 집합으로부터 |q|개의 동일한 색상의 가중치에 의한 생성 함수는 다음과 같다.

:

f \left (x_1^

👆

좌우로 밀어서 보기

, x_2^

👆

좌우로 밀어서 보기

, x_3^

👆

좌우로 밀어서 보기

, \ldots \right ).

따라서 g에 의해 고정된 점들의 가중치에 의한 생성 함수는 g의 모든 사이클에 대한 위의 항의 곱이다.

:

\begin{align}\sum_{\omega} x^\omega \left |(Y^X)_{\omega,g} \right | &= \prod_{q \text{ cycle of } g} f \left (x_1^

👆

좌우로 밀어서 보기

, x_2^

👆

좌우로 밀어서 보기

, x_3^

👆

좌우로 밀어서 보기

,\ldots \right )\\&= f(x_1, x_2, \ldots)^{j_1(g)} f \left (x_1^2, x_2^2, \ldots \right )^{j_2(g)} \cdots f \left (x_1^n, x_2^n, \ldots \right )^{j_n(g)}\end{align}

모든 g에 대한 합에 이것을 대입하면, 주장된 치환된 사이클 지수가 산출된다.

1,2,…,n} 위의 치환군으로, k개의 궤도를 가진 것을 G라고 한다. 이때, G의 치환에 의한 고정점의 개수의 평균은 k이다.

:

\frac{1}

👆

좌우로 밀어서 보기

\sum_{\pi \in G} k_n (\pi) = k

위의 식에서, 치환 π에 의한 고정점의 개수를

k_n (\pi)

로 나타낸다. 이 사실은, 각각의 점을 움직이지 않는 G의 요소의 개수를 세는 것으로 알 수 있다.

4. 예시

포여 열거 정리를 적용하여 정육면체를 2가지 색으로 칠하는 방법의 수를 구하는 예시는 다음과 같다.

먼저, 정육면체 abcd-efgh의 각 면에 다음과 같이 번호를 붙인다.

* 면 abcd: 1
* 면 abef: 2
* 면 bcfg: 3
* 면 adeh: 4
* 면 cdhg: 5
* 면 efgh: 6

이때, 정육면체의 회전군은 크기가 24이다. ( $|G|=24$ )

포여 열거 정리를 적용하기 위한 다항식은 다음과 같다.

: $P(x_1, x_2, x_3, x_4, x_5, x_6)=\frac{1}{24} (x_1^6+6x_1^2x_4+6x_1^2x_2^2+8x_3^2)$

2가지 색으로 칠하므로, $x_1=x_2=x_3=x_4=x_5=x_6=2$ 를 대입한다.

: $P(2,2,2,2,2,2)=10$

따라서, 정육면체를 2가지 색으로 칠하는 방법은 총 10가지이다.

4.1. 목걸이

크기 $n$ 의 집합 위에서 순환군 $\operatorname{Cyc}(n)$ 의 작용에 대한 궤도들을 목걸이라고 한다. $k$ 가지 색깔을 가질 수 있는 길이 $n$ 의 목걸이들을 열거하는 방법을 생각해보자. 이 경우 다음이 성립한다.

* $G=\operatorname{Cyc}(n)$ (3차 순환군)
* $X$ 는 크기 $n$ 의 집합
* $Y$ 는 크기 $k$ 의 집합

순환군 $\operatorname{Cyc}(n)$ 의 순환 지표는 다음과 같다.

: $Z_{\operatorname{Cyc}(n)}(t_1,\dots,t_n)=\frac1n\sum_{d\mid n}\phi(d)t_d^{n/d}$

여기서 $\phi$ 는 오일러 피 함수이다. 따라서, 목걸이의 수는 다음과 같이 주어진다.

: $Z_{\operatorname{Cyc}(n)}(k,\dots,k)=\frac1n\sum_{d\mid n}\phi(d)k^{n/d}$

주어진 색깔들의 중복집합에 대해 무게를 달리하여 목걸이의 수를 셀 수도 있다. 예를 들어 $n=k=3$ 이고, 각 색깔 $Y=\{c_1,c_2,c_3\}$ 의 무게가 $(1,0,0)$ , $(0,1,0)$ , $(0,0,1)$ 이라고 하자. 이 경우 순환 지표는 다음과 같다.

: $Z_{\operatorname{Cyc}(3)}(t_1,t_2,t_3)=\frac13(t_1^3+2t_3)$

포여 열거 정리에 의해 다음과 같은 생성 함수를 얻는다.

: $F(c_1,c_2,c_3)=Z_{\operatorname{Cyc}(3)}(c_1+c_2+c_3,c_1^2+c_2^2+c_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$ 색깔 구슬 하나로 이루어진 목걸이는 한가지 종류만 존재한다.

4.2. 팔찌

크기 $n$ 의 집합 위에, 정이면체군 $\operatorname{Dih}(n)$ 의 작용에 대한 궤도들을 팔찌라고 한다. $k$ 가지 색깔을 가질 수 있는, 길이 $n$ 의 팔찌들의 열거를 생각할 때, 정이면체군 $\operatorname{Dih}(n)$ 의 순환 지표는 다음과 같다.

: $Z_{\operatorname{Dih}(n)}(t_1,\dots,t_n)=\frac12Z_{\operatorname{Cyc}(n)}(t_1,\dots,t_n)+\begin{cases}\frac14(t_2^{n/2}+t_1^2t_2^{n/2-1})&2\mid n\\\frac12t_1t_2^{(n-1)/2}&2\nmid n\end{cases}$

따라서, 팔찌의 수는 다음과 같다.

: $Z_{\operatorname{Dih}(n)}(k,\dots,k)=\frac1{2n}\sum_{d\mid n}\phi(d)k^{n/d}+\begin{cases}\frac14(1+k)k^{n/2}&2\mid n\\\frac12k^{(n+1)/2}&2\nmid n\end{cases}$

주어진 색깔들의 중복집합을 갖는 팔찌의 수를 무게를 달리하여 셀 수도 있다. 예를 들어, $n=k=3$ 이고 각 색깔 $Y=\{c_1,c_2,c_3\}$ 의 무게가 $(1,0,0)$ , $(0,1,0)$ , $(0,0,1)$ 인 경우, 순환 지표는 다음과 같다.

: $Z_{\operatorname{Dih}(3)}(t_1,t_2,t_3)=\frac16(t_1^3+3t_1t_2+2t_3)$

포여 열거 정리에 의해 다음과 같은 생성 함수를 얻는다.

: $F(c_1,c_2,c_3)=Z_{\operatorname{Dih}(3)}\left(c_1+c_2+c_3,c_1^2+c_2^2+c_3^2,c_1^3+c_2^3+c_3^3\right)=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^2 c_2$ 의 계수가 1이므로, $c_1$ 색깔 구슬 두 개와 $c_2$ 색깔 구슬 하나로 이루어진 팔찌의 수는 하나이다.

4.3. 그래프

$m$ 개의 꼭짓점을 가지는 그래프의 동형류를 열거하는 방법은 다음과 같다.

* $G=\operatorname{Sym}(m)$ 은 꼭짓점 집합 위의 대칭군이다.
* $X$ 는 $\textstyle\binom m2$ 개의 가능한 변의 집합이다.
* $Y=\{0,1\}$ 이며, 0은 변이 없는 것, 1은 변이 있는 것을 나타낸다. 0의 무게는 0, 1의 무게는 1이다. (즉, 그래프의 무게는 변의 수이다.)

포여 열거 정리는 고정된 꼭짓점 수를 가진 동형 그래프의 수를 계산하거나, 모서리 수에 따른 그래프의 생성 함수를 계산하는 데 사용된다.

예를 들어, 3개의 꼭짓점을 가지는 그래프의 경우 순환 지표는 다음과 같다.
: $Z_{\operatorname{Sym}(3)}(t_1, t_2, t_3) = \frac1{3!}(t_1 ^3 + 2 t_3 + 3 t_1 t_2)$
: $C(y)=1+y$
따라서,
: $F(y)=Z_{\operatorname{Sym}(3)}(1+y,1+y^2,1+y^3)=y^3+y^2+y+1$
이다. 즉, 꼭짓점이 3개이고 변이 3개, 2개, 1개, 0개인 그래프가 각각 1개씩 존재한다.

4개의 꼭짓점을 가지는 그래프의 경우 순환 지표는 다음과 같다.
:

Z_{\operatorname{Sym}(4)}(t_1,t_2,t_3,t_4) = \frac1{4!}\left(t_1^6 + 9 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2 t_4\right)

따라서,
:

F(y)=Z_{\operatorname{Sym}(4)}(1+y,1+y^2,1+y^3,1+y^4)=y^6+y^5+2y^4+3y^3+2y^2+y+1

이다. 예를 들어, 꼭짓점이 4개이고 변이 3개인 그래프의 동형류는 3개가 있다.

4.4. 트리

k^영어진 트리는 잎이거나, k^영어개의 k^영어진 트리를 가지로 가지는 마디이다. 즉, k^영어진 트리의 집합 $T_k$ 는 다음과 같다.
: $T_k^{(0)}=\{\bullet\}$
: $T_k^{(i+1)}=T_k^{(i)}\cup \overbrace{T_k^{(i)}\times T_k^{(i)}\times\cdots\times T_k^{(i)}}^k$
: $T_k=\bigcup_{i=0}^\infty T_k^{(i)}$

주어진 마디 수의 k^영어진 트리를 열거하는 문제를 생각해 보자. 이는 포여 열거 정리로 다음과 같이 다룰 수 있다.
* $G=\operatorname{Sym}(k)$ 는 대칭군
* $X=\{1,\dots,k\}$
* $Y=T_k$ . 즉, 각 가지의 "색깔"은 가지에 대응하는 부분 k^영어진 트리이다.
* $Y$ 의 무게는 꼭짓점의 수이다. 즉, 그 생성 함수는 $F(y)$ 이다.

그렇다면, 포여 열거 정리에 의하여 다음과 같은 점화식을 얻는다.
: $F(y)=1+yZ_{\operatorname{Sym}(k)}\left(F(y),F(y^2),\dots,F(y^k)\right)$
이를 재귀적으로 풀어, 주어진 마디 수의 k^영어진 트리의 동형류의 생성 함수 $F$ 를 계산할 수 있다.

예를 들어, k^영어=2이라고 하자. 이 경우 순환 지표는
: $Z_{\operatorname{Sym}(2)}(t_1,t_2)=\frac12(t_1^2+t_2)$
이다. 따라서
: $F(y)=1+\frac12y\left(F(y)^2+F(y^2)\right)=1+y+y^2+2y^3+3y^4+6y^5+\cdots$
이다.

마찬가지로, k^영어=3이라고 하자. 이 경우 순환 지표는
: $Z_{\operatorname{Sym}(3)}(t_1,t_2,t_3)=\frac16(t_1^3+3t_1t_2+2t_3)$
이다. 따라서
: $F(y)=1+\frac16y\left(F(y)^3+3F(y)F(y^2)+2F(y^3)\right)=1+y+y^2+2y^3+4y^4+8y^5+\cdots$
이다.

루트 삼진 트리의 집합 T₃는 모든 노드(또는 비 잎 정점)가 정확히 세 개의 자식(잎 또는 서브트리)을 갖는 루트 트리로 구성된다. n개의 노드를 가진 루트 삼진 트리는 (잎을 무시함으로써) 최대 3의 차수를 가진 n개의 정점을 가진 루트 트리와 동일하다. 일반적으로, 두 개의 루트 트리는 한 트리의 노드의 자식을 순열하여 다른 트리를 얻을 수 있을 때 동형이다. 즉, 노드의 자식에 작용하는 그룹은 대칭 그룹 S₃이다. 이러한 삼진 트리의 가중치는 노드(또는 비 잎 정점)의 수로 정의한다.

--

루트 삼진 트리는 잎이거나, 스스로 루트 삼진 트리인 세 자식을 가진 노드로 재귀적 객체로 볼 수 있다. 이 자식들은 구슬과 동일하다. 이에 작용하는 대칭 그룹 S₃의 사이클 지수는 다음과 같다.

: $Z_{S_3}(t_1,t_2,t_3) = \frac{t_1^3 + 3 t_1 t_2 + 2 t_3}{6}.$

폴리아 열거 정리는 루트 삼진 트리의 재귀적 구조를 노드 수에 따른 루트 삼진 트리의 생성 함수 F(t)에 대한 함수 방정식으로 변환한다. 이것은 노드 수로 가중된 루트 삼진 트리로 세 자식을 "색칠"하여 달성되며, 이로써 색 생성 함수는 $f(t)=F(t)$ 로 주어지며, 열거 정리에 의해

: $\frac{F(t)^3 + 3 F(t)F(t^2) + 2 F(t^3)}{6}$

는 노드 수보다 1 적게 가중된(자식 가중치의 합이 루트를 고려하지 않기 때문에) 루트 삼진 트리의 생성 함수이므로,

: $F(t) = 1 + t \cdot \frac{F(t)^3 + 3 F(t)F(t^2) + 2 F(t^3)}{6}.$

이는 n개의 노드를 가진 루트 삼진 트리의 수 t_n에 대한 다음 재귀 공식과 동일하다.

: $\begin{align}t_0 &= 1 \\t_{n+1} &= \frac{1}{6} \left(\sum_{a+b+c=n} t_a t_b t_c + 3\sum_{a+2b=n} t_a t_b + 2 \sum_{3a=n} t_a \right)\end{align}$

여기서 a, b 및 c는 음이 아닌 정수이다.

$t_n$ 의 처음 몇 값은 다음과 같다.

:1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241.

4.5. 색칠된 정육면체

정육면체의 면을 여러 가지 색으로 칠하는 방법의 수를 계산한다. 정육면체의 회전군을 이용하여 가능한 색칠의 종류를 열거한다.

3차원 정육면체의 면을 회전을 고려하여 m가지 색상으로 칠하는 방법은 다음과 같이 계산할 수 있다. 정육면체의 회전군 C는 정육면체의 여섯 면에 작용하며, 이는 구슬과 동등하다. 그 순환 지수는 다음과 같다.

: $Z_C(t_1,t_2,t_3,t_4) = \frac{1}{24}\left(t_1^6 + 6 t_1^2 t_4 + 3 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2^3\right)$

C의 24개 각 요소가 정육면체의 6면에 미치는 영향은 여기를 참조하여 분석할 수 있다.

모든 색상의 가중치를 0으로 설정하면 다음과 같은 서로 다른 색칠이 존재한다.

: $F(0)=Z_C(m,m,m,m) = \frac{1}{24}\left(m^6+ 3m^4 + 12 m^3 + 8 m^2\right)$

정육면체를 2가지 색으로 칠하는 방법의 수를 세어보면 다음과 같다.

정육면체 abcd-efgh에서 면 abcd를 1, 면 abef를 2, 면 bcfg를 3, 면 adeh를 4, 면 cdhg를 5, 면 efgh를 6으로 명명한다. 이 때, $|G|=24$ 가 되며,
$P(x_1, x_2, x_3, x_4, x_5, x_6)=\frac{1}{24} (x_1^6+6x_1^2x_4+6x_1^2x_2^2+8x_3^2)$
여기서, $x_1=x_2=x_3=x_4=x_5=x_6=2$ (2가지 색으로 칠하기 위해)이므로
$P(2,2,2,2,2,2)=10$
이 된다.

5. 역사

1927년에 미국의 수학자 존 하워드 레드필드(John Howard Redfield^영어, 1879~1944)가 발견하였으나 널리 알려지지 못했다. 이후 헝가리의 수학자 포여 죄르지가 1937년에 같은 정리를 독자적으로 발견하였고, 이를 화합물의 수를 세는 데 응용하였다.