순환 지표

군론과 조합론에서 순환 지표(循環指標, 영어: cycle index)는 유한 집합 위에 충실하게 작용하는 유한군에 대응되는 다변수 다항식 불변량이다. 군의 작용의 궤도들의 크기와 수에 대한 생성 함수이다.

정의[편집]

크기가 $n$ 인 유한 집합 $X$ 및 그 대칭군의 부분군 $G\leq \operatorname {Sym} (X)$ 이 주어졌다고 하자. (즉, $G$ 가 $X$ 위에 충실하게 작용한다고 하자.) $G$ 의 순환 지표(循環指標, 영어: cycle index)

Z_{G}\in \mathbb {Q} [t_{1},t_{2},\dots ,t_{n}]

는 다음과 같은 다항식이다.

Z_{G}(t_{1},t_{2},\dots ,t_{n})={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{c_{1}(g)}t_{2}^{c_{2}(g)}\cdots t_{n}^{c_{n}(g)}

여기서 $c_{i}(g)$ 는 순열 $g\in G$ 의 길이 $i$ 의 순환의 수이다. 즉, $g$ 로 생성되는 $G$ 의 부분군 $\langle g\rangle \leq G$ 이 $X$ 위에 작용할 때, 주어진 크기의 궤도들의 수이다.

추상적으로 서로 동형인 군이라도, 집합 위의 작용이 다르다면 서로 다른 순환 지표를 가질 수 있다.

자명군은 임의의 크기 $n$ 의 유한 집합 위에 충실하게 작용한다. 이 경우 순환 지표는

Z_{1}(t_{1},\dots ,t_{n})=t_{1}^{n}

이다.

$n$ 차 순환군 $\operatorname {Cyc} (n)$ 은 크기가 $n$ 인 집합 위에

\operatorname {Cyc} (n)=\{(1)(2)(3)\cdots (n),(123\cdots n),(1357\cdots ),(147\cdots ),(15\cdots )\}

와 같이 작용한다. 이 작용을 갖춘 순환군 $\operatorname {Cyc} (n)$ 의 경우

Z_{\operatorname {Cyc} (n)}(t_{1},\dots ,t_{n})={\frac {1}{n}}\sum _{d\mid n}\phi (d)t_{d}^{n/d}

이다. 여기서 $\phi$ 는 오일러 피 함수이다.

$n$ 차 정이면체군 $\operatorname {Dih} (n)=\langle a,b|a^{n}=b^{2}=(ba)^{2}=1\rangle$ 은 크기 $n$ 의 집합 위에 다음과 같이 작용한다.

a\mapsto (1234\cdots n)

b\colon {\begin{cases}(1n)(2,n-1)\cdots (n/2,n/2+1)&2\mid n\\(1n)(2,n-1)\cdots ((n+1)/2)&2\nmid n\end{cases}}

정이면체군 $\operatorname {Dih} (n)$ 의 순환 지표는 다음과 같다.

Z_{\operatorname {Dih} (n)}(t_{1},\dots ,t_{n})={\frac {1}{2}}Z_{\operatorname {Cyc} (n)}(t_{1},\dots ,t_{n})+{\begin{cases}{\frac {1}{4}}(t_{2}^{n/2}+t_{1}^{2}t_{2}^{n/2-1})&2\mid n\\{\frac {1}{2}}t_{1}t_{2}^{(n-1)/2}&2\nmid n\end{cases}}

크기 $n!$ 의 대칭군 $\operatorname {Sym} (n)$ 은 크기 $n$ 의 집합 위에 자연스럽게 작용한다. 이 경우 순환 지표는 다음과 같다.

Z_{\operatorname {Sym} (n)}(t_{1},t_{2},\dots ,t_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}{\frac {1}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k=1}^{n}t_{k}^{j_{k}}

이 합에서 $(j_{1},j_{2},\dots ,j_{n})$ 의 항은 크기 $i$ 의 순환이 $j_{i}$ 개 있는 순열에 대응한다.

크기 $n!/2$ 의 교대군 $\operatorname {Alt} (n)\leq \operatorname {Sym} (n)$ 역시 크기 $n$ 의 집합 위에 자연스럽게 작용한다. 이 경우 순환 지표는 다음과 같다.

Z_{\operatorname {Alt} (n)}(t_{1},t_{2},\dots ,t_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}{\frac {1+(-1)^{j_{2}+j_{4}+\cdots }}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k=1}^{n}t_{k}^{j_{k}}

이 합에서 $1+(-1)^{j_{2}+j_{4}+\cdots }$ 은 짝순열의 경우 2이며 홀순열의 경우 0이다.

정육면체 및 정팔면체의 방향 보존 대칭군 $O\leq \operatorname {SO} (3)$ 은 $\operatorname {Sym} (4)$ 와 동형인, 크기가 24인 유한군이다. 이는 정육면체의 6개의 면 (또는 정팔면체의 6개의 꼭짓점)에 충실하게 작용한다. 이 경우, 순환 지표는 다음과 같다.

Z_{O}(t_{1},t_{2},\dots ,t_{6})={\frac {1}{24}}\left(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}\right)

여기서 각 항은 다음과 같은 켤레류에 대응한다.

$O$ 는 또한 정육면체의 8개의 꼭짓점(또는 정팔면체의 8개의 면)에 충실하게 작용한다. 이 경우, 순환 지표는 다음과 같다.

Z_{O}(t_{1},t_{2},\dots ,t_{6})={\frac {1}{24}}\left(t_{1}^{8}+6t_{4}^{2}+9t_{2}^{4}+8t_{1}^{3}t_{3}^{2}\right)

여기서 각 항은 다음과 같은 켤레류에 대응한다.

정사면체의 대칭군 $T\leq \operatorname {SO} (3)$ 은 교대군 $\operatorname {Alt} (4)$ 와 동형인, 크기 12의 유한군이다. 이는 정사면체의 4개의 면 (또는 4개의 꼭짓점)에 충실하게 작용한다.

이 경우, 순환 지표는 다음과 같다.

Z_{T}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{12}}\left(t_{1}^{4}+8t_{1}t_{3}+t_{2}^{2}\right)

여기서 각 항은 다음과 같은 켤레류에 대응한다.

헝가리의 수학자 포여 죄르지가 1937년에 포여 열거 정리에 사용하기 위하여 도입하였다.^[1]

↑ Pólya, G. (1937). “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen”. 《Acta Mathematica》 (독일어) 68 (1): 145–254. doi:10.1007/BF02546665. ISSN 0001-5962. Zbl 0017.23202.

Tucker, Alan (1974년 11월). “Polya’s enumeration formula by example” (PDF). 《Mathematics Magazine》 (영어) 47 (5): 248–256. doi:10.2307/2688047. JSTOR 2688047. Zbl 0297.05007. 2015년 6월 16일에 원본 문서 (PDF)에서 보존된 문서. 2016년 1월 17일에 확인함.

Weisstein, Eric Wolfgang. “Cycle index”. 《Wolfram MathWorld》 (영어). Wolfram Research.
Yuan, Qiaochu (2009년 6월 21일). “GILA V: The Polya enumeration theorem and applications”. 《Annoying Precision》 (영어).
Yuan, Qiaochu (2009년 6월 24일). “GILA VI: The cycle index polynomials of the symmetric groups”. 《Annoying Precision》 (영어).