순환 지표

2.1. 순환 지표의 정의

크기가 n인 유한 집합 X와 그 대칭군의 부분군 G가 주어졌을 때, G의 순환 지표는 각 원소 g에 대해, g를 순환 분해했을 때 나타나는 순환들의 길이를 변수로 하는 다항식으로 표현된다.

이는 다음과 같이 정의된다.

:$Z\_G(t\_1,t\_2,\backslash dots,t\_n)=\backslash frac1$

3. 예시

유클리드 평면 상의 정사각형의 회전 대칭 그룹 G를 고려해 보자. 그 요소는 정사각형의 꼭짓점의 이미지로 완전히 결정된다. 이 꼭짓점에 1, 2, 3, 4의 레이블을 붙여서 (예를 들어 시계 방향으로 연속적으로) G의 요소를 집합 X = {1,2,3,4}의 순열로 나타낼 수 있다. G의 순열 표현은 90°, 180°, 270°, 360°의 반시계 방향 회전을 나타내는 네 개의 순열 (1 4 3 2), (1 3)(2 4), (1 2 3 4) 및 e = (1)(2)(3)(4)로 구성된다. 이 표현에서 항등 순열 e는 고정점을 가진 유일한 순열이다. 추상적인 그룹으로서, G는 순환군 C₄로 알려져 있으며, 이 순열 표현은 정규 표현이다. 사이클 지수 단항식은 각각 a₄, a₂², a₄, 및 a₁⁴이다. 따라서, 이 순열 그룹의 사이클 지수는 다음과 같다.
: \(Z(C_4) = \frac{1}{4} \left( a_1^4 + a_2^2 + 2a_4 \right).\)

그룹 C₄는 자연스러운 방식으로 X의 요소의 정렬되지 않은 쌍에도 작용한다. 임의의 순열 g는 {x,y} → {x^g, y^g} (여기서 x^g는 순열 g하에서 요소 x의 이미지)로 보낼 것이다. 집합 X는 이제 A = {1,2}, B = {2,3}, C = {3,4}, D = {1,4}, E = {1,3} 및 F = {2,4}이다. 이 요소들은 정사각형의 변과 대각선 또는 완전히 다른 설정에서는 완전 그래프 K₄의 모서리로 생각할 수 있다. 이 새로운 집합에서 작용하면, 네 개의 그룹 요소는 이제 (A D C B)(E F), (A C)(B D)(E)(F), (A B C D)(E F) 및 e = (A)(B)(C)(D)(E)(F)로 표현되며, 이 작용의 사이클 지수는 다음과 같다.
: \(Z(C_4) = \frac{1}{4} \left( a_1^6 + a_1^2 a_2^2 + 2a_2a_4 \right).\)

그룹 C₄는 동일한 자연스러운 방식으로 X의 요소의 정렬된 쌍에도 작용할 수 있다. 임의의 순열 g는 (x,y) → (x^g, y^g)로 보낼 것이다 (이 경우 (x, x) 형식의 정렬된 쌍도 가질 것이다). X의 요소는 완전 유향 그래프 D₄의 호로 생각할 수 있다 (각 꼭짓점에 루프가 있음). 이 경우 사이클 지수는 다음과 같다.
: \(Z(C_4) = \frac{1}{4} \left( a_1^{16} + a_2^8 + 2a_4^4 \right).\)

3.1. 자명군 (Trivial group)

자명군은 항등원만을 원소로 갖는 군이다. 이 경우, 순환 지표는 모든 변수가 1의 거듭제곱으로 표현된다. 즉, 임의의 크기 $n$의 유한 집합 위에 충실하게 작용하는 자명군의 순환 지표는 다음과 같다.

:$Z\_1(t\_1,\backslash dots,t\_n)=t\_1^n$

이는 모든 요소를 고정하는 하나의 순열을 포함하며, 자연스러운 작용을 나타낸다.

:$Z(E\_n)\; =\; a\_1^n.$

3.2. 순환군 (Cyclic group)

순환군 $C\_n$은 하나의 생성원으로 생성되는 군이다. 정$n$각형의 회전군, 즉 원 주위에 똑같이 간격을 둔 $n$개의 원소로 이루어진 군으로 생각할 수 있다. 이 군은 $n$의 각 약수 $d$에 대해 위수가 $d$인 $\backslash phi(d)$개의 원소를 가지며, 여기서 $\backslash phi(d)$는 $d$보다 작고 $d$와 서로소인 자연수의 개수를 나타내는 오일러 피 함수이다.

$n$차 순환군 $\backslash operatorname\{Cyc\}(n)$은 크기가 $n$인 집합 위에 다음과 같이 작용한다.

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

이 작용을 갖춘 순환군 $\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$는 오일러 피 함수이다. $C\_n$의 정규 표현에서, 위수가 $d$인 순열은 길이 $d$의 $n/d$개의 사이클을 가지므로, 순환 지표는 다음과 같이 표현된다.

:$Z(C\_n)\; =\; \backslash frac\{1\}\{n\}\; \backslash sum\_\{d|n\}\; \backslash varphi(d)\; a\_d^\{n/d\}.$

3.3. 정이면체군 (Dihedral group)

정이면체군 \(\operatorname{Dih}(n)=\langle a,b|a^n=b^2=(ba)^2=1\rangle\)은 크기 \(n\)의 집합 위에 작용한다. 여기서 \(a\)는 \(n\)차 순환, \(b\)는 반사 변환을 나타낸다.

* \(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)=\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(D_n) = \frac{1}{2} Z(C_n) +
\begin{cases}
\frac{1}{2} a_1 a_2^{(n-1)/2}, & n \mbox{ 홀수, } \\
\frac{1}{4} \left( a_1^2 a_2^{(n-2)/2} + a_2^{n/2} \right), & n \mbox{ 짝수.}
\end{cases}\)

3.4. 대칭군과 교대군 (Symmetric and Alternating groups)

대칭군 $\backslash operatorname\{Sym\}(n)$은 크기 $n$의 집합의 모든 순열을 포함하는 군이며, 크기는 $n!$이다. 교대군 $\backslash operatorname\{Alt\}(n)$은 짝순열만을 포함하는 대칭군의 부분군이며, 크기는 $n!/2$이다.

대칭군 $\backslash operatorname\{Sym\}(n)$의 순환 지표는 다음과 같은 공식으로 주어진다.
:$Z\_\{\backslash operatorname\{Sym\}(n)\}(t\_1,t\_2,\backslash dots,t\_n)=\backslash sum\_\{j\_1+2\; j\_2\; +\; 3\; j\_3\; +\; \backslash cdots\; +\; n\; j\_n\; =\; n\}\; \backslash frac1\{\backslash prod\_\{k=1\}^n\; k^\{j\_k\}\; j\_k!\}\; \backslash prod\_\{k=1\}^n\; t\_k^\{j\_k\}$
이 합에서 $(j\_1,j\_2,\backslash dots,j\_n)$의 항은 크기 $i$의 순환이 $j\_i$개 있는 순열에 대응한다.

이는 완전한 벨 다항식을 사용하여 다음과 같이 나타낼 수도 있다.
:$Z(S\_n)\; =\; \backslash frac\{B\_n(0!\backslash ,a\_1,\; 1!\backslash ,a\_2,\; \backslash dots,\; (n-1)!\backslash ,a\_n)\}\{n!\}.$

대칭군의 순환 지수에 대한 재귀 공식은 다음과 같다.
:$Z(S\_n)\; =\; \backslash frac\{1\}\{n\}\; \backslash sum\_\{l=1\}^n\; a\_l\; \backslash ;\; Z(S\_\{n-l\}).$

교대군 $\backslash operatorname\{Alt\}(n)$의 순환 지표는 다음과 같다.
:$Z\_\{\backslash operatorname\{Alt\}(n)\}(t\_1,t\_2,\backslash dots,t\_n)=\backslash sum\_\{j\_1+2\; j\_2\; +\; 3\; j\_3\; +\; \backslash cdots\; +\; n\; j\_n\; =\; n\}\; \backslash frac\{1\; +\; (-1)^\{j\_2+j\_4+\backslash cdots\}\}\{\backslash prod\_\{k=1\}^n\; k^\{j\_k\}\; j\_k!\}\; \backslash prod\_\{k=1\}^n\; t\_k^\{j\_k\}$
이 합에서 $1\; +\; (-1)^\{j\_2+j\_4+\backslash cdots\}$은 짝순열의 경우 2이며 홀순열의 경우 0이다.

3.5. 정다면체의 대칭군

정다면체의 방향 보존 대칭군은 유한군이며, 순환 지표를 통해 그 구조를 파악할 수 있다.

* 정육면체/정팔면체: 정육면체와 정팔면체의 방향 보존 대칭군 $O\backslash le\backslash operatorname\{SO\}(3)$는 크기가 24인 유한군으로, $\backslash operatorname\{Sym\}(4)$와 동형이다. 이 군은 정육면체의 6개 면(또는 정팔면체의 6개 꼭짓점)에 작용하며, 순환 지표는 다음과 같다.
:$Z\_O(t\_1,t\_2,\backslash dots,t\_6)=\backslash frac1\{24\}\backslash left(t\_1^6+6t\_1^2t\_4+3t\_1^2t\_2^2+8t\_3^2+6t\_2^3\backslash right)$
각 항은 다음 켤레류에 대응한다.
$t\_1^6$: 항등원
$t\_1^2t\_4$: 정육면체 면에 수직인 축으로 90도 회전
$t\_1^2t\_2^2$: 정육면체 면에 수직인 축으로 180도 회전
$t\_3^2$: 정팔면체 면에 수직인 축으로 120도 회전
$t\_2^3$: (정육면체 또는 정팔면체) 변에 수직인 축으로 180도 회전
$O$는 또한 정육면체의 8개 꼭짓점(또는 정팔면체의 8개 면)에 작용하며, 이 경우 순환 지표는 다음과 같다.
:$Z\_O(t\_1,t\_2,\backslash dots,t\_6)=\backslash frac1\{24\}\backslash left(t\_1^8+6t\_4^2+9t\_2^4+8t\_1^3t\_3^2\backslash right)$
여기서 $t\_4^2$는 정육면체 면에 수직인 축으로 90도 회전, $t\_2^4$는 정육면체 면에 수직인 축으로 180도 회전, $t\_1^3t\_3^2$는 정팔면체 면에 수직인 축으로 120도 회전, $t\_2^4$는 (정육면체 또는 정팔면체) 변에 수직인 축으로 180도 회전을 나타낸다.

4. 순환 지표의 응용

순환 지표는 다양한 조합론적 문제 해결에 응용될 수 있다.

이 절 전체에서 순환 지표는 변수의 이름을 명시적으로 포함시켜 표기법을 약간 수정한다. 따라서, 순열군 G에 대해 다음과 같이 쓸 수 있다.

:: $Z(G)\; =\; Z(G;\; a\_1,\; a\_2,\; \backslash ldots,\; a\_n).$

G를 집합 X에 작용하는 군이라고 하자. G는 또한 X의 k-부분집합과 X의 서로 다른 원소의 k-튜플에 작용을 유도한다(k = 2인 경우의 #예시 참조). 1 ≤ k ≤ n의 경우. f_k와 F_k를 각각 이러한 작용에서 G의 궤도의 수라고 하자. 관례에 따라 f₀ = F₀ = 1로 설정한다.

a) f_k에 대한 일반 생성 함수는 다음과 같다.
:: $\backslash sum\_\{k=0\}^n\; f\_k\; t^k\; =\; Z(G;\; 1+t,\; 1+t^2,\; \backslash ldots,\; 1+t^n),$
b) F_k에 대한 지수 생성 함수는 다음과 같다.
:: $\backslash sum\_\{k=0\}^n\; F\_k\; t^k/k!\; =\; Z(G;\; 1+t,\; 1,\; 1,\; \backslash ldots,\; 1).$

G를 집합 X에 작용하는 군이라고 하고, h를 X에서 Y로의 함수라고 하자. G의 임의의 g에 대해, h(x^g) 역시 X에서 Y로의 함수이다. 따라서, G는 모든 함수 X에서 Y로의 집합 Y^X에 작용을 유도한다. 이 작용의 궤도의 수는 Z(G; b, b, ..., b)이며, 여기서 b = |Y |이다.

이 결과는 궤도 계수 보조 정리 (Not Burnside's lemma라고도 하지만 전통적으로 Burnside's lemma라고 함)에서 파생되며, 결과의 가중 버전은 폴리 열거 정리이다.

순환 지표는 여러 변수의 다항식이며 위의 결과는 이 다항식의 특정 평가가 조합론적으로 중요한 결과를 제공한다는 것을 보여준다. 다항식으로서, 또한 형식적으로 더하고, 빼고, 미분하고, 적분할 수 있다. 기호 조합론 영역은 이러한 형식적 연산의 결과에 대한 조합론적 해석을 제공한다.

무작위 순열의 순환 구조가 어떻게 보이는지에 대한 질문은 알고리즘 분석에서 중요한 질문이다. 가장 중요한 결과의 개요는 무작위 순열 통계에서 찾을 수 있다.

4.1. 폴여 열거 정리 (Pólya enumeration theorem)

이 절 전체에서 순환 지표는 변수의 이름을 명시적으로 포함시켜 표기법을 약간 수정한다. 따라서, 순열군 G에 대해 다음과 같이 쓸 수 있다.

:: $Z(G)\; =\; Z(G;\; a\_1,\; a\_2,\; \backslash ldots,\; a\_n).$

G를 집합 X에 작용하는 군이라고 하자. G는 또한 X의 k-부분집합과 X의 서로 다른 원소의 k-튜플에 작용을 유도한다(k = 2인 경우의 #예시 참조). 1 ≤ k ≤ n의 경우. f_k와 F_k를 각각 이러한 작용에서 G의 궤도의 수라고 하자. 관례에 따라 f₀ = F₀ = 1로 설정한다.

a) f_k에 대한 일반 생성 함수는 다음과 같다.
:: $\backslash sum\_\{k=0\}^n\; f\_k\; t^k\; =\; Z(G;\; 1+t,\; 1+t^2,\; \backslash ldots,\; 1+t^n),$
b) F_k에 대한 지수 생성 함수는 다음과 같다.
:: $\backslash sum\_\{k=0\}^n\; F\_k\; t^k/k!\; =\; Z(G;\; 1+t,\; 1,\; 1,\; \backslash ldots,\; 1).$

G를 집합 X에 작용하는 군이라고 하고, h를 X에서 Y로의 함수라고 하자. G의 임의의 g에 대해, h(x^g) 역시 X에서 Y로의 함수이다. 따라서, G는 모든 함수 X에서 Y로의 집합 Y^X에 작용을 유도한다. 이 작용의 궤도의 수는 Z(G; b, b, ..., b)이며, 여기서 b = |Y |이다.

이 결과는 궤도 계수 보조 정리 (Not Burnside's lemma라고도 하지만 전통적으로 Burnside's lemma라고 함)에서 파생되며, 결과의 가중 버전은 폴여 열거 정리이다.

순환 지표는 여러 변수의 다항식이며 위의 결과는 이 다항식의 특정 평가가 조합론적으로 중요한 결과를 제공한다는 것을 보여준다. 다항식으로서, 또한 형식적으로 더하고, 빼고, 미분하고, 적분할 수 있다. 기호 조합론 영역은 이러한 형식적 연산의 결과에 대한 조합론적 해석을 제공한다.

무작위 순열의 순환 구조가 어떻게 보이는지에 대한 질문은 알고리즘 분석에서 중요한 질문이다. 가장 중요한 결과의 개요는 무작위 순열 통계에서 찾을 수 있다.

한국의 관점: 폴여 열거 정리는 한국의 전통 문양, 건축 디자인 등에서 나타나는 대칭성을 분석하고 새로운 디자인을 창조하는 데 활용될 수 있다.

4.2. 번사이드 보조정리 (Burnside's lemma)

순환 지표는 번사이드 보조정리(궤도 계수 보조 정리)를 통해 군의 작용에 대한 궤도의 개수를 계산하는 데 사용될 수 있다. 이는 여러 변수의 다항식으로 표현되며, 특정 값을 대입하면 조합론적으로 중요한 결과를 얻을 수 있다.

한국의 관점에서 번사이드 보조정리는 사회 집단의 다양성을 분석하고, 사회 통합을 위한 정책 수립에 활용될 수 있다. 예를 들어, 다양한 문화적 배경을 가진 사람들이 모여 사는 지역 사회에서, 서로 다른 집단 간의 상호작용 패턴을 분석하고 문화 교류 프로그램을 기획하는 데 번사이드 보조정리의 아이디어를 활용할 수 있다.

순환 지표는 다항식으로서 형식적으로 더하고, 빼고, 미분하고, 적분할 수 있으며, 기호 조합론은 이러한 연산에 대한 조합론적 해석을 제공한다. 무작위 순열의 순환 구조는 알고리즘 분석에서 중요한 문제이며, 관련 결과는 무작위 순열 통계에서 찾을 수 있다.

4.3. 알고리즘 분석

순환 지표는 여러 변수의 다항식이며, 특정 평가는 조합론적으로 중요한 결과를 제공한다. 순환 지표는 형식적으로 더하고, 빼고, 미분하고, 적분할 수 있으며, 기호 조합론 영역은 이러한 형식적 연산 결과에 대한 조합론적 해석을 제공한다.

무작위 순열의 순환 구조는 알고리즘 분석에서 중요한 문제이며, 주요 결과는 무작위 순열 통계에서 확인할 수 있다. (한국의 관점) 한국의 IT 산업 발전과 함께 알고리즘 효율성과 성능 분석의 중요성이 커지면서, 순환 지표를 활용한 무작위 순열 분석은 알고리즘 개발 및 최적화에 기여하고 있다.

5. 역사

헝가리의 수학자 포여 죄르지가 1937년에 포여 열거 정리에 사용하기 위하여 순환 지표를 도입하였다. 포여 죄르지의 업적은 수학적, 과학적 발전이 사회 문제 해결에 기여할 수 있음을 보여주는 중요한 사례이다. 한국 사회는 과학기술 발전을 통해 사회 문제를 해결하고 지속 가능한 발전을 이루어나가는 데 힘써야 할 것이다.