순환 지표

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

1. 개요
2. 정의
- 2.1. 순환 지표의 정의
- 2.2. 순환 지표의 계산
3. 예시
4. 순환 지표의 응용
5. 역사
참조

1. 개요

순환 지표는 유한 집합 위의 순열군에 대한 다항식으로, 순열의 순환 구조를 나타낸다. 크기 n인 유한 집합 X와 대칭군(부분군) G가 주어지면, G의 순환 지표는 각 원소 g의 순환 길이를 변수로 하는 다항식으로 표현된다. 순환 지표는 군의 작용에 따라 달라지며, 추상적인 군과 순열 표현을 구별하는 데 유용하다. 순환 지표는 조합론적 문제 해결에 응용되며, 특히 폴리 열거 정리, 번사이드 보조정리, 알고리즘 분석 등에 활용된다. 헝가리 수학자 포여 죄르지가 1937년 포여 열거 정리에 사용하기 위해 순환 지표를 도입했다.

더 읽어볼만한 페이지

열거조합론 - 카탈랑 수
카탈랑 수는 조합론에서 여러 개수 세기 문제의 해답으로 나타나는 수열로, 괄호 구조, 이진 트리, 다각형 분할 등 다양한 조합론적 대상의 개수를 나타내며 여러 분야에 응용된다.
열거조합론 - 오일러 수 (조합론)
오일러 수는 조합론에서 집합의 순열 중 특정 조건을 만족하는 순열의 개수를 나타내는 수로, 주로 집합 $\{1,2,\ldots,n\}$ 의 순열에서 $a_i>a_{i+1}$ 인 $i$ 가 정확히 $m$ 개 있는 순열의 개수를 나타내며, 오일러 다항식 및 관련 성질과 함께 1755년 레온하르트 오일러에 의해 소개되었다.
군론 - 점군
점군은 도형의 병진 조작을 제외한 대칭 조작들의 집합으로 군론의 공리를 만족하며, 쉐인플리스 기호나 허먼-모건 기호로 표기되고, 대칭 조작에 대응하는 행렬 표현은 가약 표현과 기약 표현으로 분해될 수 있다.
군론 - 파울리 행렬
파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.

순환 지표

2. 정의

크기가 $n$ 인 유한 집합 $X$ 및 그 대칭군의 부분군 $G\le\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)=\frac1$

\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\le G

이

X

위에 작용할 때, 주어진 크기의 궤도들의 수이다.

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

집합 ''X''에서 자기 자신으로의 전단사 함수는 ''X''의 순열이라고 하며, ''X''의 모든 순열 집합은 함수 합성 하에서 군을 형성하며, 이를 ''X''의 대칭군이라고 부르고 Sym(''X'' )로 표기한다.^[1] Sym(''X'' )의 모든 부분군은 |''X'' |를 ''차수''로 하는 순열군이라고 한다.^[1]

군 ''G''가 집합 ''X''에 작용한다고 가정하자(즉, 군 작용이 존재한다). 조합론적 응용에서 관심은 집합 ''X''에 있으며, 예를 들어 ''X''에서 항목을 세고 ''G''에 의해 어떤 구조가 불변으로 유지될 수 있는지를 아는 것이다. 이러한 설정에서 순열군으로 작업함으로써 손실되는 것은 거의 없으므로, 이러한 응용에서는 군을 고려할 때, 작업할 군의 순열 표현이며, 따라서 군 작용을 지정해야 한다.^[3] 반면에 대수학자들은 군 자체에 더 관심이 있으며 군 작용의 핵에 더 관심이 있을 것이며, 이는 군에서 순열 표현으로 넘어갈 때 얼마나 손실되는지를 측정한다.^[3]

순환 지표는 순열군 ''G''에 속하는 모든 순열 ''g''의 순환 지표 단항식의 평균이다.

좀 더 형식적으로, ''G''를 차수가 ''m''이고 차수가 ''n''인 순열군이라고 하자.

''G''에 속하는 모든 순열 ''g''는 서로소인 사이클로 고유하게 분해될 수 있으며, 다음과 같이 나타낼 수 있다.

''c''₁ ''c''₂ ''c''₃ ... .

사이클 ''c''의 길이를 |''c'' |로 나타내자.

이제 ''j''_''k''(''g'')를 길이 ''k''인 ''g''의 사이클의 개수라고 하자. 여기서

:

0 \le j_k(g) \le \lfloor n/k \rfloor \mbox{ and } \sum_{k=1}^{n} k \, j_k(g) = n.

''g''에 변수 ''a''₁, ''a''₂, ..., ''a''_''n''에서 단항식

:

\prod_{c\in g} a_

= \prod_{k=1}^n a_k^{j_k(g)}

을 연관시킨다.

그러면 ''G''의 순환 지표 ''Z''(''G'')는 다음과 같이 주어진다.

:

Z(G) = \frac{1}

\sum_{g\in G} \prod_{k=1}^n a_k^{j_k(g)}.

2. 1. 순환 지표의 정의

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

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

:

Z_G(t_1,t_2,\dots,t_n)=\frac1

\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\le G

이

X

위에 작용할 때, 주어진 크기의 궤도들의 수이다.^[1]

추상적으로 서로 동형인 군이라도, 집합 위의 작용이 다르다면 서로 다른 순환 지표를 가질 수 있다.^[2] 집합 X에서 자기 자신으로의 전단사 함수는 X의 순열이라고 하며, X의 모든 순열 집합은 함수 합성 하에서 군을 형성하며, 이를 X의 대칭군이라고 부르고 Sym(X)로 표기한다.^[1] Sym(X)의 모든 부분군은 |X|를 차수로 하는 순열군이라고 한다.^[1]

군 G가 집합 X에 작용할때, 조합론적 응용에서 관심은 집합 X에 있으며, 예를 들어 X에서 항목을 세고 G에 의해 어떤 구조가 불변으로 유지될 수 있는지를 아는 것이다.^[3] 이러한 설정에서 순열군으로 작업함으로써 손실되는 것은 거의 없으므로, 이러한 응용에서는 군을 고려할 때, 작업할 군의 순열 표현이며, 따라서 군 작용을 지정해야 한다.^[3] 반면에 대수학자들은 군 자체에 더 관심이 있으며 군 작용의 핵에 더 관심이 있을 것이며, 이는 군에서 순열 표현으로 넘어갈 때 얼마나 손실되는지를 측정한다.^[3]

모든 순열은 본질적으로 하나의 방식으로 서로소(공통 원소가 없음) 순환의 곱으로 쓸 수 있다.^[5]^[6] 순열은 고정점(순열에 의해 변경되지 않는 원소)을 가질 수 있으므로, 이는 길이 1의 순환으로 표현된다.^[7]

순열의 순환 구조는 여러 (더미) 변수의 대수 단항식으로 다음과 같은 방식으로 코딩할 수 있다:^[1] 변수는 순열의 순환 분해에 나타나는 순환의 각 고유한 순환 길이에 필요하다. 일반적으로 길이 k 순환에 해당하는 변수 a_k을 사용한다. 변수 a_i는 j_i(g) 거듭제곱으로 올릴 것이며, 여기서 j_i(g)는 순열 g의 순환 분해에서 길이 i의 순환의 개수이다. 그런 다음 순환 지수 단항식을 순열 g에 연관시킬 수 있다. 순환 지표는 순열군 G에 속하는 모든 순열 g의 순환 지표 단항식의 평균이다.^[1]

좀 더 형식적으로, G를 차수가 m이고 차수가 n인 순열군이라고 하자. G에 속하는 모든 순열 g는 서로소인 사이클로 고유하게 분해될 수 있으며, 다음과 같이 나타낼 수 있다.

:c₁ c₂ c₃ ... .

사이클 c의 길이를 |c|로 나타내자.

이제 j_k(g)를 길이 k인 g의 사이클의 개수라고 하자. 여기서

:

0 \le j_k(g) \le \lfloor n/k \rfloor \mbox{ and } \sum_{k=1}^{n} k \, j_k(g) = n.

g에 변수 a₁, a₂, ..., a_n에서 단항식

:

\prod_{c\in g} a_

= \prod_{k=1}^n a_k^{j_k(g)}

을 연관시킨다.

그러면 G의 순환 지표 Z(G)는 다음과 같이 주어진다.

:

Z(G) = \frac{1}

\sum_{g\in G} \prod_{k=1}^n a_k^{j_k(g)}.

순환 지표는 추상적인 군이 아닌 군 작용에 따라 달라진다.^[1] 추상적인 군에는 많은 순열 표현이 있으므로, 이를 구별하기 위한 용어가 유용하다. 추상적인 군이 순열의 관점에서 정의될 때, 이는 순열군이며 군 작용은 항등 준동형사상이다. 이를 자연 작용이라고 한다.^[1]

케일리의 정리는 모든 추상군이 (집합으로서) 자신에 작용하는 군(오른쪽) 곱셈에 의해 주어진 정규 순열 표현을 갖는다고 명시한다.^[11]

2. 2. 순환 지표의 계산

크기가

n

인 유한 집합

X

와 그 대칭군의 부분군

G\le\operatorname{Sym}(X)

이 주어졌을 때 (즉,

G

가

X

위에 충실하게 작용한다고 할 때),

G

의 '''순환 지표'''는 다음과 같은 다항식으로 계산된다.^[4]

:

Z_G(t_1,t_2,\dots,t_n)=\frac1

\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\le G

이

X

위에 작용할 때, 주어진 크기의 궤도들의 수이다.

작용이 다르다면 서로 동형인 군이라도 서로 다른 순환 지표를 가질 수 있다. 유한 순열은 집합 ''X'' = {1, 2, ..., ''n''}에 대한 군 작용으로 표현될 수 있으며, 두 줄 표기법으로 나타낼 수 있다. 예를 들어,

:

\left(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \end{matrix}\right)

는 1 ↦ 2, 2 ↦ 3, 3 ↦ 4, 4 ↦ 5, 5 ↦ 1로 보내는 ''X'' = {1, 2, 3, 4, 5}에 대한 전단사이다. 이는 한 줄 표기법으로 [2 3 4 5 1]로 표현할 수 있다. 이 예시는 숫자를 순환시키므로 순환 순열이며, (1 2 3 4 5)와 같이 나타낼 수 있다. 순환 표기법에서는 (1 2 3 4 5), (3 4 5 1 2), (5 1 2 3 4)는 모두 같은 순열을 나타낸다.

모든 순열이 순환 순열은 아니지만, 모든 순열은 서로소 순환의 곱으로 표현할 수 있다.^[5]^[6] 순열은 고정점을 가질 수 있으며, 이는 길이 1의 순환으로 표현된다.^[7] 예를 들어,

:

\left( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 2&1&3&5&6&4 \end{matrix} \right) = (1 2)(3)(4 5 6).

과 같이 표현 가능하다.

순열의 순환 구조는 여러 변수의 대수 단항식으로 코딩할 수 있다. 순열의 순환 분해에 나타나는 각 고유한 순환 길이에 대해 변수를 사용한다. 일반적으로 길이 ''k'' 순환에 해당하는 변수 ''a''_''k''를 사용한다. 변수 ''a''_''i''는 ''j''_''i'' (''g'') 거듭제곱으로 올린다. 여기서 ''j''_''i'' (''g'')는 순열 ''g''의 순환 분해에서 길이 ''i''의 순환의 개수이다. 순열 ''g''에 연관시킬 수 있는 ''순환 지수 단항식''은 다음과 같다.

:

\prod_{k=1}^n a_k^{j_k(g)}

순열군 ''G''에 속하는 모든 순열 ''g''의 순환 지표 단항식의 평균이 순환 지표가 된다.

''G''를 차수가 ''m''이고 차수가 ''n''인 순열군이라고 할 때, ''G''에 속하는 모든 순열 ''g''는 서로소인 사이클로 고유하게 분해될 수 있으며, 다음과 같이 표현 가능하다.

:''c''₁ ''c''₂ ''c''₃ ... .

사이클 ''c''의 길이를 |''c'' |로 나타내고, ''j''_''k''(''g'')를 길이 ''k''인 ''g''의 사이클의 개수라고 하면,

:

0 \le j_k(g) \le \lfloor n/k \rfloor \mbox{ and } \sum_{k=1}^{n} k \, j_k(g) = n.

이 성립한다. ''g''에 변수 ''a''₁, ''a''₂, ..., ''a''_''n''에서 단항식

:

\prod_{c\in g} a_

= \prod_{k=1}^n a_k^{j_k(g)}

을 연관시키면, ''G''의 순환 지표 ''Z''(''G'')는 다음과 같이 주어진다.

:

Z(G) = \frac{1}

\sum_{g\in G} \prod_{k=1}^n a_k^{j_k(g)}.

3. 예시

유클리드 평면 상의 정사각형의 회전 대칭 그룹 ''G''를 고려해 보자. 그 요소는 정사각형의 꼭짓점의 이미지로 완전히 결정된다. 이 꼭짓점에 1, 2, 3, 4의 레이블을 붙여서 (예를 들어 시계 방향으로 연속적으로) ''G''의 요소를 집합 ''X'' = {1,2,3,4}의 순열로 나타낼 수 있다.^[8] ''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''의 이미지)로 보낼 것이다.^[9] 집합 ''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,\dots,t_n)=t_1^n

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

:

Z(E_n) = a_1^n.

3. 2. 순환군 (Cyclic group)

순환군

C_n

은 하나의 생성원으로 생성되는 군이다. 정

n

각형의 회전군, 즉 원 주위에 똑같이 간격을 둔

n

개의 원소로 이루어진 군으로 생각할 수 있다.^[12] 이 군은

n

의 각 약수

d

에 대해 위수가

d

인

\phi(d)

개의 원소를 가지며, 여기서

\phi(d)

는

d

보다 작고

d

와 서로소인 자연수의 개수를 나타내는 오일러 피 함수이다.^[12]

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)=\frac1n\sum_{d\mid n}\phi(d)t_d^{n/d}

여기서

\phi

는 오일러 피 함수이다.

C_n

의 정규 표현에서, 위수가

d

인 순열은 길이

d

의

n/d

개의 사이클을 가지므로, 순환 지표는 다음과 같이 표현된다.^[12]

:

Z(C_n) = \frac{1}{n} \sum_{d|n} \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)

대칭군

\operatorname{Sym}(n)

은 크기

n

의 집합의 모든 순열을 포함하는 군이며, 크기는

n!

이다. 교대군

\operatorname{Alt}(n)

은 짝순열만을 포함하는 대칭군의 부분군이며, 크기는

n!/2

이다.

대칭군

\operatorname{Sym}(n)

의 순환 지표는 다음과 같은 공식으로 주어진다.

:

Z_{\operatorname{Sym}(n)}(t_1,t_2,\dots,t_n)=\sum_{j_1+2 j_2 + 3 j_3 + \cdots + n j_n = n} \frac1{\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

개 있는 순열에 대응한다.

이는 완전한 벨 다항식을 사용하여 다음과 같이 나타낼 수도 있다.

:

Z(S_n) = \frac{B_n(0!\,a_1, 1!\,a_2, \dots, (n-1)!\,a_n)}{n!}.

대칭군의 순환 지수에 대한 재귀 공식은 다음과 같다.

:

Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l \; Z(S_{n-l}).

교대군

\operatorname{Alt}(n)

의 순환 지표는 다음과 같다.

:

Z_{\operatorname{Alt}(n)}(t_1,t_2,\dots,t_n)=\sum_{j_1+2 j_2 + 3 j_3 + \cdots + n j_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이다.

3. 5. 정다면체의 대칭군

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

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

:

Z_O(t_1,t_2,\dots,t_6)=\frac1{24}\left(t_1^6+6t_1^2t_4+3t_1^2t_2^2+8t_3^2+6t_2^3\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,\dots,t_6)=\frac1{24}\left(t_1^8+6t_4^2+9t_2^4+8t_1^3t_3^2\right)

여기서

t_4^2

는 정육면체 면에 수직인 축으로 90도 회전,

t_2^4

는 정육면체 면에 수직인 축으로 180도 회전,

t_1^3t_3^2

는 정팔면체 면에 수직인 축으로 120도 회전,

t_2^4

는 (정육면체 또는 정팔면체) 변에 수직인 축으로 180도 회전을 나타낸다.

정육면체의 경우, 24개의 대칭은 다음과 같이 구체적으로 나타낼 수 있다.

* 항등원 ( $a_1^6$ ): 1개
* 90도 면 회전 ( $6 a_1^2 a_4$ ): 6개
* 180도 면 회전 ( $3 a_1^2 a_2^2$ ): 3개
* 120도 꼭짓점 회전 ( $8 a_3^2$ ): 8개
* 180도 모서리 회전 ( $6 a_2^3$ ): 6개
정사면체: 정사면체의 대칭군 $T\le\operatorname{SO}(3)$ 은 크기 12의 유한군이며, 교대군 $\operatorname{Alt}(4)$ 와 동형이다. 이는 정사면체의 4개 면(또는 4개 꼭짓점)에 작용하며, 순환 지표는 다음과 같다.

:

Z_T(t_1,t_2,t_3,t_4)=\frac1{12}\left(t_1^4+8t_1t_3+t_2^2\right)

각 항은 다음 켤레류에 대응한다.

* $t_1^4$ : 항등원
* $t_1t_3$ : 120도 회전
* $t_2^2$ : 180도 회전
'''정사각형:''' 유클리드 평면 상의 정사각형의 회전 대칭 그룹 ''C''₄의 경우, 순환지표는 다음과 같다.^[8]

::

Z(C_4) = \frac{1}{4} \left( a_1^4 + a_2^2 + 2a_4 \right).

'''완전 그래프 K₃:''' 완전 그래프 ''K''₃을 정삼각형으로 생각하면, 정점 순열 그룹에 의해 유도된 변 순열 그룹의 순환 지표는 다음과 같다.^[9]

:

Z(G) = \frac{1}{6} \left(a_1^3 + 3 a_1 a_2 + 2 a_3 \right).

'''완전 그래프 K₄:''' 완전 그래프 ''K''₄의 경우, 정점 순열 그룹에 의해 유도된 변 순열 그룹의 순환 지표는 다음과 같다.^[9]

:

Z(G) = \frac{1}{24} \left( a_1^6 + 9 a_1^2 a_2^2 + 8 a_3^2 + 6 a_2 a_4 \right).

4. 순환 지표의 응용

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

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

:: $Z(G) = Z(G; a_1, a_2, \ldots, a_n).$

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

a) ''f''_''k''에 대한 일반 생성 함수는 다음과 같다.

:: $\sum_{k=0}^n f_k t^k = Z(G; 1+t, 1+t^2, \ldots, 1+t^n),$

b) ''F''_''k''에 대한 지수 생성 함수는 다음과 같다.

:: $\sum_{k=0}^n F_k t^k/k! = Z(G; 1+t, 1, 1, \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'' |이다.^[14]

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

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

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

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

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

::

Z(G) = Z(G; a_1, a_2, \ldots, a_n).

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

a) ''f''_''k''에 대한 일반 생성 함수는 다음과 같다.

::

\sum_{k=0}^n f_k t^k = Z(G; 1+t, 1+t^2, \ldots, 1+t^n),

b) ''F''_''k''에 대한 지수 생성 함수는 다음과 같다.

::

\sum_{k=0}^n F_k t^k/k! = Z(G; 1+t, 1, 1, \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'' |이다.^[14]

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

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

무작위 순열의 순환 구조가 어떻게 보이는지에 대한 질문은 알고리즘 분석에서 중요한 질문이다. 가장 중요한 결과의 개요는 무작위 순열 통계에서 찾을 수 있다.
한국의 관점: 폴여 열거 정리는 한국의 전통 문양, 건축 디자인 등에서 나타나는 대칭성을 분석하고 새로운 디자인을 창조하는 데 활용될 수 있다.

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

순환 지표는 번사이드 보조정리(궤도 계수 보조 정리)를 통해 군의 작용에 대한 궤도의 개수를 계산하는 데 사용될 수 있다.^[14] 이는 여러 변수의 다항식으로 표현되며, 특정 값을 대입하면 조합론적으로 중요한 결과를 얻을 수 있다.^[14]
한국의 관점에서 번사이드 보조정리는 사회 집단의 다양성을 분석하고, 사회 통합을 위한 정책 수립에 활용될 수 있다. 예를 들어, 다양한 문화적 배경을 가진 사람들이 모여 사는 지역 사회에서, 서로 다른 집단 간의 상호작용 패턴을 분석하고 문화 교류 프로그램을 기획하는 데 번사이드 보조정리의 아이디어를 활용할 수 있다.

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

4. 3. 알고리즘 분석

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

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

5. 역사

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

참조

_[1] 서적
_[2] 서적
_[3] 서적
_[4] 문서
_[5] 문서
_[6] 문서
_[7] 서적
_[8] 문서
_[9] 문서
_[10] 문서
_[11] 서적
_[12] 서적
_[13] 서적
_[14] 서적
_[15] 저널 Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen 1937

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

문의하기 : help@durumis.com