포여 열거 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''포여 열거 정리'''(Pólya列擧定理, {{llang|en|Pólya enumeration theorem}})는 [[군의 작용]]에 대한 궤도의 수를 주어진 무게에 따라 [[순환 지표]]를 사용하여 열거하는 정리이다. [[번사이드 보조정리]]의 일반화이다.

== 정의 ==
=== 무게가 없는 경우의 열거 정리 ===
다음과 같은 데이터가 주어졌다고 하자.
* [[유한군]] <math>G</math>
* [[유한 집합]] <math>X</math>. 그 원소를 '''구슬'''({{llang|en|bead}})이라고 하자.
* <math>G</math>의 <math>X</math> 위의 왼쪽 [[충실한 작용]]
* [[유한 집합]] <math>Y</math>. 그 원소를 '''색깔'''({{llang|en|color}})이라고 하자.
그렇다면 <math>G</math>는 함수 집합 <math>Y^X</math> 위에도 역시 다음과 같이 [[왼쪽 작용]]을 갖는다.
:<math>g\cdot (y_x)_{x\in X}=(y_{g^{-1}\cdot x})_{x\in X}</math>
그렇다면, '''포여 열거 정리'''에 따르면, <math>Y^X</math>의 궤도의 수 <math>|Y^X/G|</math>는 다음과 같다.
:<math>|Y^X/G| = \frac1{|G|}\sum_{g \in G} |Y|^{c(g)} </math>
여기서
* <math>c(g)</math>는 <math>g</math>를 <math>X</math> 위의 [[순열]]로 생각하였을 때 순환들의 수이다.

=== 일반적 열거 정리 ===
다음과 같은 데이터가 주어졌다고 하자.
* [[유한군]] <math>G</math>
* 크기 <math>n</math>의 [[유한 집합]] <math>X</math>. 그 원소를 '''구슬'''({{llang|en|bead}})이라고 하자.
* <math>G</math>의 <math>X</math> 위의 왼쪽 [[충실한 작용]]
* 각 [[다중지표]] <math>\vec w\in\mathbb N^k</math>에 대하여, [[유한 집합]] <math>Y_{\vec w}</math>. 그 원소를 '''무게 <math>\vec w</math>의 색깔'''({{llang|en|color of weight <math>\vec w</math>}})이라고 하고, <math>\textstyle Y=\bigsqcup_{\vec w\in\mathbb N^k}Y_{\vec w}</math>라고 하자. <math>Y</math>는 [[무한 집합]]일 수 있다. 즉, 무게 함수 <math>\vec w\colon Y\to\mathbb N^k</math>에 대하여 각 자연수의 [[원상 (수학)|원상]]은 유한 집합이다.
그렇다면, <math>G</math>는 역시 함수 집합 <math>Y^X</math> 위에 작용한다. 함수 <math>f\colon X\to Y</math>의 무게 <math>\vec W(f)\in\mathbb N^k</math>는 각 구슬의 색깔의 무게의 합이다.
:<math>\vec W(f)=\sum_{w\in\mathbb N}\sum_{x\in X}\vec w(f(x))</math>

다음과 같은 생성 함수를 정의하자.
:<math>F(y_1,\dots,y_k)=\sum_{\vec w\in\mathbb N^k} |W^{-1}(\{\vec w\})/G|x^{\vec w}</math>
여기서
:<math>y^{\vec w}=y_1^{w_1}y_2^{w_2}\cdots y_k^{w_k}</math>
이다. 즉, <math>F(y_1,\dots,y_k)</math>의 <math>y^{\vec w}</math> 항의 계수는 <math>Y^X</math> 속이의 함수 가운데, 무게가 <math>\vec w</math>인 것들의 수이다. 또한, 다음과 같은 생성 함수를 정의하자.
:<math>C(y_1,\dots,y_k)=\sum_{\vec w\in\mathbb N^k} |Y_{\vec w}|y^{\vec w}</math>
즉, <math>C(y_1,\dots,y_k)</math>의 <math>y^{\vec w}</math> 항의 계수는 무게가 <math>\vec w</math>인 색깔의 수이다.

'''포여 열거 정리'''에 따르면, 다음이 성립한다.
:<math>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)</math>
좌변에서 <math>Z_G</math>는 순열군 <math>G</math>의 [[순환 지표]]이다. 즉, 계산하고자 하는 생성 함수 <math>F</math>는 [[순환 지표]] <math>Z_G</math>의 특정한 값이다.

무게의 간단한 예로, 색깔 집합 <math>Y</math>가 유한 집합이며, 무게 집합은 <math>\mathbb N^y</math>이며, 색깔 <math>y\in Y</math>의 무게가
:<math>w(y)=(0,0,\dots,0,1,0,\dots,0)</math>
의 꼴이라고 잡을 수 있다. 이 경우, 생성 함수의 형식적 변수 <math>y_1,\dots,y_k</math>는 <math>Y</math>의 원소로 생각할 수 있다.

== 예 ==
=== 목걸이 ===
{{본문|목걸이 (조합론)}}
크기 <math>n</math>의 집합 위의, 순환군 <math>\operatorname{Cyc}(n)</math>의 작용에 대한 궤도들을 '''[[목걸이 (조합론)|목걸이]]'''라고 한다. <math>k</math>가지의 색깔을 가질 수 있는, 길이 <math>n</math>의 목걸이들의 열거를 생각하자. 이 경우
* <math>G=\operatorname{Cyc}(n)</math> (3차 [[순환군]])
* <math>X</math>는 크기 <math>n</math>의 집합
* <math>Y</math>는 크기 <math>k</math>의 집합
가 된다. 순환군 <math>\operatorname{Cyc}(n)</math>의 [[순환 지표]]는
:<math>Z_{\operatorname{Cyc}(n)}(t_1,\dots,t_n)=\frac1n\sum_{d\mid n}\phi(d)t_d^{n/d}</math>
이다. 여기서 <math>\phi</math>는 [[오일러 피 함수]]이다. 따라서, 목걸이의 수는
:<math>Z_{\operatorname{Cyc}(n)}(k,\dots,k)=\frac1n\sum_{d\mid n}\phi(d)k^{n/d}</math>
이다.

무게를 달리 하여 주어진 색깔들의 [[중복집합]]을 갖는 목걸이의 수를 셀 수도 있다. 예를 들어, <math>n=k=3</math>이며, 각 색깔 <math>Y=\{c_1,c_2,c_3\}</math>의 무게가 <math>(1,0,0)</math>, <math>(0,1,0)</math>, <math>(0,0,1)</math>이라고 하자. 이 경우 [[순환 지표]]는
:<math>Z_{\operatorname{Cyc}(3)}(t_1,t_2,t_3)=\frac13(t_1^3+2t_3)</math>
이며, 포여 열거 정리에 의해 다음과 같은 [[생성 함수 (수학)|생성 함수]]를 얻는다.
:<math>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</math>
예를 들어, <math>c_1^2 c_2</math>의 계수가 1이므로 <math>c_1</math> 색깔의 구슬 두 개와 <math>c_2</math> 색깔의 구슬 하나로 이루어진 [[목걸이 (조합론)|목걸이]]의 수는 하나이다.

=== 팔찌 ===
{{본문|목걸이 (조합론)}}
크기 <math>n</math>의 집합 위의, [[정이면체군]] <math>\operatorname{Dih}(n)</math>의 작용에 대한 궤도들을 '''[[팔찌 (조합론)|팔찌]]'''라고 한다. <math>k</math>가지의 색깔을 가질 수 있는, 길이 <math>n</math>의 팔찌들의 열거를 생각하자. 이 경우
* <math>G=\operatorname{Cyc}(n)</math>
* <math>X</math>는 크기 <math>n</math>의 집합
* <math>Y</math>는 크기 <math>k</math>의 집합
가 된다. [[정이면체군]] <math>\operatorname{Dih}(n)</math>의 [[순환 지표]]는
:<math>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}</math>
이다. 따라서, 팔찌의 수는
:<math>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}</math>
이다.

무게를 달리 하여 주어진 색깔들의 [[중복집합]]을 갖는 팔찌의 수를 셀 수도 있다. 예를 들어, <math>n=k=3</math>이며, 각 색깔 <math>Y=\{c_1,c_2,c_3\}</math>의 무게가 <math>(1,0,0)</math>, <math>(0,1,0)</math>, <math>(0,0,1)</math>이라고 하자. 이 경우 [[순환 지표]]는
:<math>Z_{\operatorname{Dih}(3)}(t_1,t_2,t_3)=\frac16(t_1^3+3t_1t_2+2t_3)</math>
이며, 포여 열거 정리에 의해 다음과 같은 [[생성 함수 (수학)|생성 함수]]를 얻는다.
:<math>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</math>
예를 들어, <math>c_1^2 c_2</math>의 계수가 1이므로 <math>c_1</math> 색깔의 구슬 두 개와 <math>c_2</math> 색깔의 구슬 하나로 이루어진 [[팔찌 (조합론)|팔찌]]의 수는 하나이다.

=== 그래프 ===
{{본문|그래프}}
<math>m</math>개의 [[꼭짓점]]을 가지는 [[그래프]]의 동형류를 열거한다고 하자. 이는 다음과 같이 생각할 수 있다.
* <math>G=\operatorname{Sym}(m)</math>은 꼭짓점 집합 위의 [[대칭군 (군론)|대칭군]]이다.
* <math>X</math>는 <math>\textstyle\binom m2</math>개의 가능한 변의 집합이다.
* <math>Y=\{0,1\}</math>. 0은 변이 없는 것, 1은 변이 있는 것을 나타낸다. 0의 무게는 0, 1의 무게는 1이라고 하자. (즉, 그래프의 무게는 변의 수이다.)
예를 들어, 3개의 꼭짓점을 가지는 그래프를 생각하자. 이 경우 [[순환 지표]]는
:<math>Z_{\operatorname{Sym}(3)}(t_1, t_2, t_3) = \frac1{3!}(t_1 ^3 + 2 t_3 + 3 t_1 t_2)</math>
:<math>C(y)=1+y</math>
이며, 따라서
:<math>F(y)=Z_{\operatorname{Sym}(3)}(1+y,1+y^2,1+y^3)=y^3+y^2+y+1</math>
이다. 즉, 3개의 꼭짓점과 3개의 변을 가지는 그래프 1개, 3개의 꼭짓점과 2개의 변을 가지는 그래프 1개, 3개의 꼭짓점과 1개의 변을 가지는 그래프 1개, 3개의 꼭짓점과 0개의 변을 가지는 그래프 1개가 존재한다.

마찬가지로, 4개의 꼭짓점을 가지는 그래프를 생각하자. 이 경우 [[순환 지표]]는
:<math>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)</math>
이며, 따라서
:<math>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</math>
이다. 즉, (예를 들어) 4개의 쪽짓점과 3개의 변을 가지는 그래프의 동형류는 3개가 있다.

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

주어진 마디 수의 <math>k</math>진 트리를 열거하는 문제를 생각해 보자. 이는 포여 열거 정리로 다음과 같이 다룰 수 있다.
* <math>G=\operatorname{Sym}(k)</math>는 [[대칭군 (군론)|대칭군]]
* <math>X=\{1,\dots,k\}</math>
* <math>Y=T_k</math>. 즉, 각 가지의 "색깔"은 가지에 대응하는 부분 <math>k</math>진 트리이다.
* <math>Y</math>의 무게는 꼭짓점의 수이다. 즉, 그 생성 함수는 <math>F(y)</math>이다.
그렇다면, 포여 열거 정리에 의하여 다음과 같은 점화식을 얻는다.
:<math>F(y)=1+yZ_{\operatorname{Sym}(k)}\left(F(y),F(y^2),\dots,F(y^k)\right)</math>
이를 재귀적으로 풀어, 주어진 마디 수의 <math>k</math>진 트리의 동형류의 생성 함수 <math>F</math>를 계산할 수 있다.

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

마찬가지로, <math>k=3</math>이라고 하자. 이 경우 [[순환 지표]]는
:<math>Z_{\operatorname{Sym}(3)}(t_1,t_2,t_3)=\frac16(t_1^3+3t_1t_2+2t_3)</math>
이다. 따라서
:<math>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</math>
이다. {{OEIS|A598}}

== 역사 ==
1927년에 미국의 수학자 존 하워드 레드필드({{llang|en|John Howard Redfield}}, 1879~1944)가 발견하였으나 널리 알려지지 못했다.<ref>{{저널 인용
 | last = Redfield
 | first = John Howard
 | title = The theory of group-reduced distributions
 | journal = American Journal of Mathematics
 | volume = 49
 | year = 1927
 | issue = 3
 | pages = 433–455
 | doi = 10.2307/2370675
 |mr=1506633
| jstor=2370675 | jfm=53.0106.03 | 언어=en}}</ref><ref>{{저널 인용
 | 이름 = Frank |성=Harary
 |이름2=Ed |성2=Palmer
 | title = The enumeration methods of Redfield
 | journal = American Journal of Mathematics
 | volume = 89
 | year = 1967
 | issue = 2
 | pages = 373–384
 | doi = 10.2307/2373127
 |mr=0214487
| jstor=2373127 | zbl=0178.00903|언어=en}}</ref> 이후 [[헝가리]]의 수학자 [[포여 죄르지]]가 1937년에 같은 정리를 독자적으로 발견하였고, 이를 [[화합물]]의 수를 세는 데 응용하였다.<ref>{{저널 인용|이름=G.|성=Pólya|저자링크=포여 죄르지|제목=Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen|저널=Acta Mathematica|권=68|호=1|날짜=1937|쪽=145–254|doi=10.1007/BF02546665|issn=0001-5962|zbl=0017.23202|언어=de}}</ref>

== 각주 ==
{{각주}}
* {{저널 인용|제목=Polya’s enumeration formula by example|jstor=2688047|doi=10.2307/2688047|저널=Mathematics Magazine|이름=Alan|성=Tucker|권=47|호=5|날짜=1974-11|쪽=248–256|url=http://apollonius.math.nthu.edu.tw/d1/disk5/js/discrete-math/tucker.pdf|zbl=0297.05007|언어=en|확인날짜=2016-01-16|보존url=https://web.archive.org/web/20150616043122/http://apollonius.math.nthu.edu.tw/d1/disk5/js/discrete-math/tucker.pdf#|보존날짜=2015-06-16|url-status=dead}}
* {{서적 인용
  | 이름 = G. |성=Pólya |저자링크=포여 죄르지
  |이름2=R. C.|성2= Read
  | title = Combinatorial enumeration of groups, graphs, and chemical compounds
  | publisher = Springer
  | date = 1987
  |mr=0884155 |doi=10.1007/978-1-4612-4664-0|isbn=978-1-4612-9105-3|언어=en}}

== 외부 링크 ==
* {{eom|title=Pólya theorem}}
* {{매스월드|id=PolyaEnumerationTheorem|title=Pólya enumeration theorem}}
* {{매스월드|id=CycleIndex|title=Cycle index}}
* {{웹 인용|url=https://qchu.wordpress.com/2009/06/21/gila-v-the-polya-enumeration-theorem-and-applications/|제목=GILA V: The Polya enumeration theorem and applications|날짜=2009-06-21|이름=Qiaochu|성=Yuan|웹사이트=Annoying Precision|언어=en}}

[[분류:군론]]
[[분류:열거조합론]]
[[분류:대수학 정리]]
[[분류:조합론 정리]]