포여 열거 정리

\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\; \backslash to\; Y$의 집합이다). 그러면 군 $G$는 $Y^X$에 작용한다. 포여 열거 정리는 색깔이 지정된 구슬 배열의 $G$에 대한 궤도 수를 다음과 같은 공식으로 계산한다.

:$\backslash left\; |Y^X/G\; \backslash right\; |\; =\; \backslash frac\{1\}$

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

여기서 $m=|Y|$는 색상의 개수이고, $c(g)$는 집합 $X$의 순열로 간주될 때, 군 원소 $g$의 순환 순열의 개수이다.

집합 $D\_1$ 위의 링 지수 $P(x\_1,\; x\_2,\; \backslash cdots,\; x\_n)$를 갖는 치환군을 G라고 하자. D₁에서 D₂로의 사상 f, g에 대해 $f(\backslash pi(x))=g(x)$가 되는 $\backslash pi$가 존재하지 않을 때, ''f''와 ''g''는 다르다고 한다. 이때, ''D1''에서 ''D2''로의 서로 다른 것의 개수는

:$P(x\_1,\; x\_2,\; \backslash cdots,\; x\_n)=\backslash 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,\; \backslash cdots,\; x\_n)=\backslash 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$ 위의 왼쪽 충실한 작용
• 각 다중지표 $\backslash vec\; w\backslash in\backslash mathbb\; N^k$에 대하여, 유한 집합 $Y\_\{\backslash vec\; w\}$. 그 원소를 '''무게 $\backslash vec\; w$의 색깔'''(color of weight $\backslash vec\; w$^영어)이라고 하고, $\backslash textstyle\; Y=\backslash bigsqcup\_\{\backslash vec\; w\backslash in\backslash mathbb\; N^k\}Y\_\{\backslash vec\; w\}$라고 한다. $Y$는 무한 집합일 수 있다. 즉, 무게 함수 $\backslash vec\; w\backslash colon\; Y\backslash to\backslash mathbb\; N^k$에 대하여 각 자연수의 원상은 유한 집합이다.

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

:$\backslash vec\; W(f)=\backslash sum\_\{w\backslash in\backslash mathbb\; N\}\backslash sum\_\{x\backslash in\; X\}\backslash vec\; w(f(x))$

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

:$F(y\_1,\backslash dots,y\_k)=\backslash sum\_\{\backslash vec\; w\backslash in\backslash mathbb\; N^k\}\; |W^\{-1\}(\backslash \{\backslash vec\; w\backslash \})/G|x^\{\backslash vec\; w\}$

여기서

:$y^\{\backslash vec\; w\}=y\_1^\{w\_1\}y\_2^\{w\_2\}\backslash cdots\; y\_k^\{w\_k\}$

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

:$C(y\_1,\backslash dots,y\_k)=\backslash sum\_\{\backslash vec\; w\backslash in\backslash mathbb\; N^k\}\; |Y\_\{\backslash vec\; w\}|y^\{\backslash vec\; w\}$

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

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

:$F(y\_1,\backslash dots,y\_k)=Z\_G\backslash left(C(y\_1,\backslash dots,y\_k),C(y\_1^2,\backslash dots,y\_k^2),\backslash dots,C(y\_1^n,\backslash dots,y\_k^n)\backslash right)$

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

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

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

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

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

:$f(t)\; =\; f\_0\; +\; f\_1\; t\; +\; f\_2\; t^2\; +\; \backslash cdots$

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

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

:$Z\_G(t\_1,t\_2,\backslash ldots,t\_n)\; =\; \backslash 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),\backslash ldots,f(t^n))$

또는 다변량의 경우:

:$F(t\_1,t\_2,\backslash ldots)\; =\; Z\_G(f(t\_1,t\_2,\backslash ldots),f(t\_1^2,t\_2^2,\backslash ldots),f(t\_1^3,t\_2^3,\backslash ldots),\backslash ldots,f(t\_1^n,t\_2^n,\backslash ldots)).$

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

:$\backslash left\; |Y^X/G\; \backslash right\; |\; =F(0)=\; Z\_G(m,m,\backslash ldots,m)\; =\; \backslash frac\{1\}$

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

집합 $D\_1$ 위의 링 지수 $P(x\_1,\; x\_2,\; \backslash cdots,\; x\_n)$를 갖는 치환군을 G라고 한다. D₁에서 D₂로의 사상 f, g에 대해 $f(\backslash pi(x))=g(x)$가 되는 $\backslash pi$가 존재하지 않을 때, ''f''와 ''g''는 다르다고 한다. 이때, ''D1''에서 ''D2''로의 서로 다른 것의 개수는

:$P(x\_1,\; x\_2,\; \backslash cdots,\; x\_n)=\backslash 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,\; \backslash cdots,\; x\_n)=\backslash 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,\backslash ldots$를 $Y$의 생성 함수 ''f''의 변수라고 하자. 가중치 벡터 $\backslash omega$가 주어지면, $x^\backslash omega$는 ''f''의 해당 단항식을 나타낸다. 번사이드 보조정리를 가중치 $\backslash omega$의 궤도에 적용하면, 이 가중치의 궤도 수는 다음과 같다.

:$\backslash frac\{1\}$

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

여기서 $(Y^X)\_\{\backslash omega,g\}$는 ''g''에 의해서도 고정된 가중치 $\backslash omega$의 색칠 집합이다. 그런 다음 모든 가능한 가중치에 대해 합하면, 다음을 얻는다.

:$F(x\_1,x\_2,\backslash ldots)=\; \backslash frac\{1\}$

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

한편, 사이클 구조 $j\_1(g),j\_2(g),\backslash ldots,j\_n(g)$를 가진 그룹 원소 ''g''는 다음 항을 기여한다.

:$t\_1^\{j\_1(g)\}\; t\_2^\{j\_2(g)\}\; \backslash cdots\; t\_n^\{j\_n(g)\}$

''G''의 사이클 지수에. 원소 ''g''는 함수 φ가 ''g''의 모든 사이클 ''q''에서 상수인 경우에만 원소 $\backslash phi\; \backslash in\; Y^X$를 고정한다. 모든 이러한 사이클 ''q''에 대해, ''f''에 의해 열거된 집합으로부터 |''q''|개의 동일한 색상의 가중치에 의한 생성 함수는 다음과 같다.

:$f\; \backslash left\; (x\_1^$

, x_2^

, x_3^

, \ldots \right ).

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

:$\backslash 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\; (\backslash pi)$로 나타낸다. 이 사실은, 각각의 점을 움직이지 않는 G의 요소의 개수를 세는 것으로 알 수 있다.

4. 예시

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

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

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

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

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

:$$$$

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

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

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

:$Z\_\{\backslash operatorname\{Cyc\}(n)\}(t\_1,\backslash dots,t\_n)=\backslash frac1n\backslash sum\_\{d\backslash mid\; n\}\backslash phi(d)t\_d^\{n/d\}$

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

:$Z\_\{\backslash operatorname\{Cyc\}(n)\}(k,\backslash dots,k)=\backslash frac1n\backslash sum\_\{d\backslash mid\; n\}\backslash phi(d)k^\{n/d\}$

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

:$Z\_\{\backslash operatorname\{Cyc\}(3)\}(t\_1,t\_2,t\_3)=\backslash frac13(t\_1^3+2t\_3)$

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

:$F(c\_1,c\_2,c\_3)=Z\_\{\backslash 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$의 집합 위에, 정이면체군 $\backslash operatorname\{Dih\}(n)$의 작용에 대한 궤도들을 '''팔찌'''라고 한다. $k$가지 색깔을 가질 수 있는, 길이 $n$의 팔찌들의 열거를 생각할 때, 정이면체군 $\backslash operatorname\{Dih\}(n)$의 순환 지표는 다음과 같다.

:$Z\_\{\backslash operatorname\{Dih\}(n)\}(t\_1,\backslash dots,t\_n)=\backslash frac12Z\_\{\backslash operatorname\{Cyc\}(n)\}(t\_1,\backslash dots,t\_n)+\backslash 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\_\{\backslash operatorname\{Dih\}(n)\}(k,\backslash dots,k)=\backslash frac1\{2n\}\backslash sum\_\{d\backslash mid\; n\}\backslash 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=\backslash \{c\_1,c\_2,c\_3\backslash \}$의 무게가 $(1,0,0)$, $(0,1,0)$, $(0,0,1)$인 경우, 순환 지표는 다음과 같다.

:$Z\_\{\backslash operatorname\{Dih\}(3)\}(t\_1,t\_2,t\_3)=\backslash frac16(t\_1^3+3t\_1t\_2+2t\_3)$

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

:$F(c\_1,c\_2,c\_3)=Z\_\{\backslash operatorname\{Dih\}(3)\}\backslash 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\backslash 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=\backslash operatorname\{Sym\}(m)$은 꼭짓점 집합 위의 대칭군이다.
• $X$는 $\backslash textstyle\backslash binom\; m2$개의 가능한 변의 집합이다.
• $Y=\backslash \{0,1\backslash \}$이며, 0은 변이 없는 것, 1은 변이 있는 것을 나타낸다. 0의 무게는 0, 1의 무게는 1이다. (즉, 그래프의 무게는 변의 수이다.)

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

예를 들어, 3개의 꼭짓점을 가지는 그래프의 경우 순환 지표는 다음과 같다.

:$Z\_\{\backslash operatorname\{Sym\}(3)\}(t\_1,\; t\_2,\; t\_3)\; =\; \backslash frac1\{3!\}(t\_1\; ^3\; +\; 2\; t\_3\; +\; 3\; t\_1\; t\_2)$

:$C(y)=1+y$

따라서,

:$F(y)=Z\_\{\backslash 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\_\{\backslash operatorname\{Sym\}(4)\}(t\_1,t\_2,t\_3,t\_4)\; =\; \backslash frac1\{4!\}\backslash left(t\_1^6\; +\; 9\; t\_1^2\; t\_2^2\; +\; 8\; t\_3^2\; +\; 6\; t\_2\; t\_4\backslash right)$

따라서,

:$F(y)=Z\_\{\backslash 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)\}=\backslash \{\backslash bullet\backslash \}$

:$T\_k^\{(i+1)\}=T\_k^\{(i)\}\backslash cup\; \backslash overbrace\{T\_k^\{(i)\}\backslash times\; T\_k^\{(i)\}\backslash times\backslash cdots\backslash times\; T\_k^\{(i)\}\}^k$

:$T\_k=\backslash bigcup\_\{i=0\}^\backslash infty\; T\_k^\{(i)\}$

주어진 마디 수의 k^영어진 트리를 열거하는 문제를 생각해 보자. 이는 포여 열거 정리로 다음과 같이 다룰 수 있다.

• $G=\backslash operatorname\{Sym\}(k)$는 대칭군
• $X=\backslash \{1,\backslash dots,k\backslash \}$
• $Y=T\_k$. 즉, 각 가지의 "색깔"은 가지에 대응하는 부분 k^영어진 트리이다.
• $Y$의 무게는 꼭짓점의 수이다. 즉, 그 생성 함수는 $F(y)$이다.

그렇다면, 포여 열거 정리에 의하여 다음과 같은 점화식을 얻는다.

:$F(y)=1+yZ\_\{\backslash operatorname\{Sym\}(k)\}\backslash left(F(y),F(y^2),\backslash dots,F(y^k)\backslash right)$

이를 재귀적으로 풀어, 주어진 마디 수의 k^영어진 트리의 동형류의 생성 함수 $F$를 계산할 수 있다.

예를 들어, k^영어=2이라고 하자. 이 경우 순환 지표는

:$Z\_\{\backslash operatorname\{Sym\}(2)\}(t\_1,t\_2)=\backslash frac12(t\_1^2+t\_2)$

이다. 따라서

:$F(y)=1+\backslash frac12y\backslash left(F(y)^2+F(y^2)\backslash right)$

=1+y+y^2+2y^3+3y^4+6y^5+\cdots

이다.

마찬가지로, k^영어=3이라고 하자. 이 경우 순환 지표는

:$Z\_\{\backslash operatorname\{Sym\}(3)\}(t\_1,t\_2,t\_3)=\backslash frac16(t\_1^3+3t\_1t\_2+2t\_3)$

이다. 따라서

:$F(y)=1+\backslash frac16y\backslash left(F(y)^3+3F(y)F(y^2)+2F(y^3)\backslash 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)\; =\; \backslash frac\{t\_1^3\; +\; 3\; t\_1\; t\_2\; +\; 2\; t\_3\}\{6\}.$

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

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

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

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

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

:$\backslash 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''는 정육면체의 여섯 면에 작용하며, 이는 구슬과 동등하다. 그 순환 지수는 다음과 같다.^[1]

:$Z\_C(t\_1,t\_2,t\_3,t\_4)\; =\; \backslash frac\{1\}\{24\}\backslash 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\backslash right)$

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

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

:$F(0)=Z\_C(m,m,m,m)\; =\; \backslash frac\{1\}\{24\}\backslash left(m^6+\; 3m^4\; +\; 12\; m^3\; +\; 8\; m^2\backslash 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



이 된다.^[1]

5. 역사

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

참조

_[1] 논문 The theory of group-reduced distributions
_[2] 논문 Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
_[3] 논문 The theory of group-reduced distributions
_[4] 논문 The enumeration methods of Redfield
_[5] 논문 Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen 1937

---

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com