사이클지수

조합 수학에서 주기 지수는 여러 변수의 다항식이며, 순열 집단이 집합에 작용하는 방법에 대한 정보를 계수 및 지수에서 간단히 읽을 수 있는 방식으로 구성된다.대수적 형태로 정보를 저장하는 이 콤팩트한 방법은 결합체 열거에 자주 사용된다.

사이클로 설정된 유한한 객체 파티션 집합의 각 순열 π; 사이클 인덱스 cycle은 변수 a₁, a₂, …의 단수로서 이 파티션의 유형(사이클 타입 π): a의_i 지수는 크기 i의 π 사이클 수입니다.순열 그룹의 주기 지수 다항식은 해당 요소의 주기 지수 단항 평균이다.문구 주기 표시기는 주기 지수 대신 사용되기도 한다.

순열 그룹의 주기 지수 다항식을 알면 그룹의 작용으로 인한 동등성 클래스를 열거할 수 있다.Polya 열거정리의 주성분이다.이러한 다항식들에 대해 형식 대수학 및 미분학 연산을 수행하고 그 결과를 조합적으로 해석하는 것은 종 이론의 핵심에 있다.

순열 그룹 및 그룹 작업

집합 X에서 그 자체로 이어지는 생체 지도를 X의 순열이라고 하며, X의 모든 순열의 집합은 X의 대칭 그룹이라고 하는 매핑의 구성 아래 그룹을 형성하고 Sym(X)을 가리킨다.Sym(X)의 모든 부분군을 X 학위의 순열 그룹이라고 한다.^[1] G는 G에서 Sym(X)로 그룹 동형성 φ을 가진 추상적인 그룹이 되도록 한다.이미지 φ(G)는 순열 그룹이다.그룹 동형성은 그룹 G가 세트 X에 대해 "행동"할 수 있도록 허용하는 수단이라고 생각할 수 있다(G의 요소와 관련된 순열 사용).그러한 집단 동형주의는 공식적으로 집단행동이라고 불리며 동형주의 이미지는 G의 순열적 표현이다. 주어진 집단은 다른 행동에 해당하는 여러 가지 순열적 표현을 가질 수 있다.^[2]

그룹 G가 집합 X에 대해 작용한다고 가정합시다(즉, 그룹 작업이 존재함).조합 어플리케이션에서 관심사는 세트 X에 있다. 예를 들어, X에서 사물을 세고 G가 불변으로 남겨질 수 있는 구조를 아는 것은 그러한 환경에서 순열 그룹과 함께 작업하면 소실되기 때문이다. 따라서 이러한 어플리케이션에서는 그룹이 고려될 때, 그것은 그룹과 함께 작업할 그룹의 순열 표현이다.따라서 그룹 액션을 지정해야 한다.반면에 대수학자들은 집단 자체에 더 관심이 있고 집단에서 순열 표현으로 전달되는 과정에서 얼마나 많은 손실이 발생하는지를 측정하는 집단 행동의 알맹이에 더 관심을 가질 것이다.^[3]

순열의 분리 주기 표현

유한 순열은 대부분 집합 X = {1,2, ..., n. 이 설정의 순열은 두 개의 선 표기법으로 나타낼 수 있다.그러므로,

${\displaystyle \left\put}2&3&4&5\\2&3&4&5&1&#1\end{put}\오른쪽)}$

X = {1, 2, 3, 4, 5}에 대한 편향에 해당하며, 1, 2, 2, 3, 3, 4, 5, 1을 전송한다.이것은 표기법에서 읽을 수 있다.맨 위 행이 적절한 순서로 X의 요소로 이해되면 두 번째 행만 작성하면 된다.이 한 줄 표기법에서, 우리의 예는 [2 3 4 5 1]^[4]이다.이 예는 주변의 숫자와 그것에 대한 세 번째 표기법이 (1 2 3 4 5)이기 때문에 주기적인 순열이라고 알려져 있다.이 주기 표기법은 다음과 같이 읽어야 한다: 각 원소는 그 오른쪽에 있는 원소로 보내지만, 마지막 원소는 첫 번째 원소로 보내진다(이 "주기"에서 시작까지).사이클 표기법을 사용하면 사이클이 어디서 시작되는지는 중요하지 않으므로 (1 2 3 4 5)와 (3 4 5 1 2)와 (5 1 2 3 4) 모두 같은 순열을 나타낸다.주기의 길이는 주기의 원소 수입니다.

모든 순열이 순환 순열인 것은 아니지만, 모든 순열은 본질적으로 한 가지 방법으로 분리(공통 요소가 없는) 주기들의 산물로^[5] 기록될 수 있다.^[6]순열은 고정된 점(순열로 변하지 않는 요소)을 가질 수 있으므로, 이는 길이 1의 사이클로 나타낼 것이다.예를 들면 다음과 같다.^[7]

${\displaystyle \left \party}1&3&3&4&5&6\\\2&3&3&5&6&4}\end{front}}=(12)(3)(456.}$

이 순열은 길이 2의 하나, 길이 3의 하나, 그리고 고정된 점의 세 사이클의 산물이다.이 사이클의 원소는 X의 공동 부분 집합이며 X의 분할을 형성한다.

순열의 주기 구조는 다음과 같은 방법으로 여러 (더미) 변수에서 대수적 단조로 코딩될 수 있다. 순열의 주기 분해에 나타나는 주기의 각 고유 주기 길이에 변수가 필요하다.앞의 예에서는 세 개의 주기 길이가 있었으므로 세₁ 개의₂ 변수, a, a 및 a를₃ 사용할 것이다(일반적으로 변수 a를_k 길이 k 주기에 대응하도록 사용).변수 a는_i j_i(g) 검정력으로 상승하며, 여기서_i j(g)는 순열 g의 주기 분해에서 길이 i의 주기 수입니다.그런 다음 사이클 지수 단수화를 연결할 수 있다.

${\displaystyle \prod _{k=1}^{n}a_{k}^{j_{k}(g)}}}}}$

순열 g까지이 예제의 주기 지수 단수는 aaa이고₁₂₃, 순열의 주기 지수 단수는 aaa₁³₂²₄²(12)(34)(5)(6 7 8 9)(10 11 12 13)(14)(15)이다.

정의

순열 그룹 G의 주기 지수는 G의 모든 순열 g의 주기 지수 단수 평균이다.

좀 더 형식적으로 G를 순서 m과 정도 n의 순열 그룹이 되게 하라.G의 모든 순열 g는 분해 주기로 분해되는 독특한 분해를 가지고 있다. 예를 들어 c₁ c₂₃ ...라고 하자. c 사이클의 길이를 c로 나타내도록 하라.

이제_k j(g)를 길이 k의 주기(cycle)가 되도록 한다.

${\displaystyle 0\leq j_{k}(g)\leq \lfloor n/k\box{\\mbox{\}}}\{k=1}^{nk\,j_{k}(g)\=n.}$

우리는 단조로운 사람과 교제한다.

${\displaystyle \prod _{c\in g}a_{c}}}{k=1}prod_{k=1}^{na_{k}^{j_{k}(g)}}}}}}}}}$

변수₁ a, a₂, ..., a에서_n.

그 다음 G의 사이클 지수 Z(G)는 다음과 같이 주어진다.

${\displaystyle Z(G)={\frac {1}{{\1}{g\sum_{g\in G}\prod_{k=1}^{n}a_{k}^{j_{k}(g)}}}}}$

예

유클리드 평면에 있는 사각형의 회전 대칭의 그룹 G를 고려한다.그러한 대칭은 정사각형의 모서리만 찍은 영상에 의해 완전히 결정된다.이러한 코너에 1, 2, 3, 4(시계 방향으로 연속적으로 이동)라는 레이블을 붙임으로써 우리는 G의 요소를 세트 X = {1,2,3,4}^[8]의 순열로 나타낼 수 있다.G의 순열 표현은 각각 90도, 180도, 270도, 360도 시계 반대 방향 회전을 나타내는 4개의 순열(1 4 3), (1)(2)(2)(3)(4)로 구성된다.아이덴티티 순열 e는 G의 이 표현에서 고정점을 갖는 유일한 순열이라는 점에 유의하십시오. 추상 그룹으로서 G는 순환 그룹 C로₄ 알려져 있으며, 이 순열 표현은 그 정규 표현이다.주기지수 일변수는 각각 a₄, a, a₂²₄, a₁⁴, a이다.따라서 이 순열 그룹의 주기 지수는 다음과 같다.

${\displaystyle Z(C_{4}={\frac {1}{1}}}}{4}}}\왼쪽(a_{1}^{4}+a_{2)}^{2}+2a_{4}\오른쪽).}$

그룹₄ C는 또한 X의 무질서한 요소 쌍에 자연적인 방법으로 작용한다.임의의 순열 g는 {x,y} → {x^g, y^g}을(를) 전송한다(여기서 x는^g 순열 g 아래의 x 요소의 이미지임).^[9]집합 X는 이제 {A, B, C, D, E, F}이며 여기서 A = {1,2}, B = {2,3}, C = {3,4}, D = {1,4}, E = {1,3}, F = {2,4}.이러한 원소는 정사각형의 면과 대각선으로, 또는 완전히 다른 설정에서 전체 그래프 K의₄ 가장자리라고 생각할 수 있다.Acting on this new set, the four group elements are now represented by (A D C B)(E F), (A C)(B D)(E)(F), (A B C D)(E F) and e = (A)(B)(C)(D)(E)(F) and the cycle index of this action is:

${\displaystyle Z(C_{4}={\frac {1}{1}}}{4}}\왼쪽(a_{1}^{6}+a_{1})}^{2}a_{2}^{2}+2a_{2}a_{4}\오른쪽).}$

또한 그룹₄ C는 동일한 자연적인 방법으로 X의 정렬된 요소 쌍에 대해 행동할 수 있다.모든 순열 g는 (x,y) → (x^g,y^g) → (x, y) (이 경우 우리는 또한 양식 쌍(x, x)을 주문했을 것이다.X의 원소는 완전한 digraph D₄(각 꼭지점에 루프가 있는)의 호라고 생각할 수 있었다.이 경우 사이클 지수는 다음과 같을 것이다.

${\displaystyle Z(C_{4}={\frac {1}{1}}}{4}}\왼쪽(a_{1}^{16}+a_{2)}^{8}+2a_{4}^{4}\오른쪽).}$

작업 유형

위의 예에서 알 수 있듯이, 주기 지수는 추상적인 그룹이 아니라 그룹 작용에 따라 달라진다.추상적인 집단의 순열 표현이 많으므로, 그것들을 구별할 수 있는 몇 가지 용어를 갖는 것이 유용하다.

추상적인 집단이 순열의 관점에서 정의되면 순열집단이고 집단행동은 정체성 동형성이다.이것을 자연 작용이라고 한다.

자연 작용에서 대칭 그룹 S는₃ 원소를^[10] 가지고 있다.

${\displaystyle S_{3}=\{e,(23), (12),(123),(132), (132)\}}$

따라서 주기 지수는 다음과 같다.

${\displaystyle Z(S_{3}}={\frac {1}{6}}\왼쪽(a_{1}^{3}+3a_{1}a_{2}+2a_{3}}\오른쪽).}$

X의 각 원소 쌍에 대해 y = x와^g y와 같은 G가 하나 이상 있을 경우, X의 순열 그룹 G는 전이적이다. 고정점을 갖는 그룹에서 순열만이 ID 순열일 경우, 전이 순열 그룹은 정규(또는 때로는 날카롭게 전이되는 것으로 언급되기도 한다)이다.

세트 X에 있는 유한 전이적 순열 그룹 G는 G = X ^[11]. Cayley의 정리에서는 모든 추상 그룹에는 (우측) 곱셈에 의해 스스로 (세트로서) 작용하는 그룹에 의해 주어지는 정기 순열 표현이 있다고 명시되어 있는 경우에만 정규 순열 그룹 G가 된다.이것을 집단의 정기적 대표라고 한다.

주기 그룹 C의₆ 정규 표현은 6개의 순열을 포함한다(순열의 한 줄 형식이 먼저 주어진다).

[1 2 3 4 5 6] = (1)(2)(3)(4)(5)(6)

[2 3 4 5 6 1] = (1 2 3 4 5 6)

[3 4 5 6 1 2] = (1 3 5)(2 4 6)

[4 5 6 1 2 3] = (1 4)(2 5)(3 6)

[5 6 1 2 3 4] = (1 5 3)(2 6 4)

[6 1 2 3 4 5] = (1 6 5 4 3 2).

따라서 주기 지수는 다음과 같다.

${\displaystyle Z(C_{6}}={\frac {1}{6}}}\왼쪽(a_{1}^{6}+a_{2)}^{3}+2a_{3}^{2}+2a_{6}\오른쪽).}$

종종, 저자가 집단 행동 용어 사용을 원하지 않을 때, 관련된 순열 그룹에는 그 행동이 무엇인지 암시하는 이름이 주어진다.다음의 세 가지 예는 이 점을 예증한다.

세 개의 꼭지점에 있는 전체 그래프의 에지 순열 그룹의 주기 지수

우리는 유클리드 평면에서 정삼각형의 완전한 그래프 K를₃ 확인할 것이다.이를 통해 우리는 등변 삼각형의 대칭으로 관련된 순열을 설명하는 기하학적 언어를 사용할 수 있다.정점 순열의 그룹 S의₃ 모든₃ 순열은 가장자리 순열을 유도한다.순열은 다음과 같다.

• ID:정점이 없고, 가장자리가 없으며, 기여도가 ${\displaystyle {\mathrm{}}_{}^{}}$ 3${\displaystyle {}_{}^{}}$. ${\displaystyle a_{1}^{3}$이다.$}$
• 정점과 반대쪽 가장자리의 중간점을 통과하는 축의 세 개의 반사:이들은 하나의 가장자리(정점에 발생하지 않은 가장자리)를 고정하고 나머지 두 개의 가장자리를 교환한다. 기여도는 3 ${\displaystyle {}_{}}$ $1{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}{}_{}}$ 2 ${\displaystyle {a\mathrm{}}_{}}$ 2 .${\displaystyle 3a_{1}a_{2$}이다$.$$}$
• 두 바퀴 회전, 하나는 시계 방향, 다른 하나는 시계 반대 방향:이렇게 하면 세 개의 가장자리 주기가 생성된다. 기여도는 $2{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ .${\displaystyle 2a_{3}.$$}$

S에서₃ 정점 순열에 의해 유도된 가장자리 순열의 G 그룹의 주기 지수는 다음과 같다.

${\displaystyle Z(G)={\frac {1}{6}\왼쪽(a_{1}^{3}+3a_{1}a_{1}a_{2}+2a_{3}}\오른쪽).}$

전체 그래프 K가₃ 자체 선 그래프(Vertex-edge dual)에 이형성이므로 정점 순열 그룹에 의해 유도되는 에지 순열 그룹은 정점 순열 그룹, 즉 S와₃ 같고 주기 지수는 Z(S₃)이다.정점(n)보다${\displaystyle }$에지(n 2$){\$2$\}\})$가 엄격히 더 많기 때문에 정점(${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$) ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{이상}}{}}$의 전체 그래프는 그렇지 않다.

네 개의 정점에 있는 전체 그래프의 에지 순열 그룹의 주기 지수

이것은 3베르크스 사례와 완전히 유사하다.이것들은 그들이 유도하는 정점 순열(자연 작용에서의 S₄)과 가장자리 순열(순서가 없는 쌍에 작용하는 S₄)이다.

• ID:이 순열은 모든 정점(따라서, 가장자리)을 자신에게 매핑하며 기여도는 $1{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$. ${\displaystyle a_{1}^{6}$이다.$}$
• 두 개의 정점을 교환하는 여섯 개의 순열:이러한 순열은 교환되지 않은 두 정점을 연결하는 가장자리뿐만 아니라 두 정점을 연결하는 가장자리를 보존한다.나머지 가장자리는 두 개의 2 사이클을 형성하며 기여도는 $6{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 1 2 ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {2\mathrm{}}_{}^{}}$ .${\displaystyle 6a_{1}^{2}a_{2}^{2}.$$}$
• 하나의 정점을 고정하고 고정되지 않은 정점 세 개에 대해 3 사이클을 생성하는 8개의 순열:이러한 순열은 두 개의 세 사이클의 가장자리를 생성하는데, 하나는 정점에 발생하지 않은 가장자리와 다른 하나는 정점에 발생한 가장자리의 경우를 포함한다. 기여도는 8 $a{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}^{}}$ a ${\displaystyle {3\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$. ${\displaystyle 8a_{3}^{2}.$$}$
• 두 꼭지점 쌍을 동시에 교환하는 세 개의 순열:이러한 순열은 두 쌍을 연결하는 두 가장자리를 보존한다.나머지 가장자리는 두 개의 2 사이클을 형성하며 기여도는 $3{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ a ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}{}_{}^{}}$ ${\displaystyle {2\mathrm{}}_{}^{}}$ a${\displaystyle {\mathrm{}}_{}^{}}$. {\$displaystyle 3a_{1}^{2}a_{2}^{2}.$$}$
• 4 사이클에서 정점을 순환하는 6개의 순열:이러한 순열은 (주기에 놓여 있는) 네 사이클의 가장자리를 생성하고 나머지 두 가장자리를 교환한다. 기여도는 $6{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}}$ 2 ${\displaystyle {a\mathrm{}}_{}}$ 4 ${\displaystyle {a\mathrm{}}_{}}$ 4${\displaystyle {}_{}}$. ${\displaystyle 6a_{2}a_{4}$이다.$}$

우리는 정사면체의 대칭으로서 기하학적으로 순열의 유형을 시각화할 수 있다.이것은 순열 유형에 대한 다음과 같은 설명을 산출한다.

• 아이덴티
• 하나의 가장자리와 가장자리의 반대쪽 가장자리의 중간점을 포함하는 평면의 반사.
• 정점을 통과하는 축과 반대 면의 중간점을 중심으로 120도 회전한다.
• 두 개의 반대쪽 가장자리의 중간점을 연결하는 축을 180도 회전시킨다.
• 6개의 회전각 90도

K의₄ 에지 순열 그룹 G의 주기 지수는 다음과 같다.

${\displaystyle Z(G)={\frac {1}{1}:{24}\왼쪽(a_{1}^{6}+9a_{1}}^{2}a_{2}^{2}^{2}+8a_{3}^{2}+6a_{2}a_{4}\오른쪽).}$

큐브 면 순열의 주기 지수

3공간의 일반 큐브와 그 대칭의 그룹(자형성)을 C라고 한다.그것은 큐브의 여섯 얼굴을 허용한다.(가장자리 순열 또는 꼭지 순열도 고려할 수 있다.)24개의 자동화가 있다.

• ID:

그런 순열이 하나 있고 그 기여는 ${\displaystyle {\mathrm{}}_{}^{}}$ 6${\displaystyle {}_{}^{}}$. ${\displaystyle a_{1}^{6}$이다.$}$

• 90도 얼굴 회전 6회:

우리는 얼굴의 중심을 통과하는 축과 마주보는 얼굴을 중심으로 회전한다.이렇게 하면 마주보는 얼굴과 얼굴이 고정되고 회전축과 평행한 얼굴 4사이클이 만들어진다.기여도는 $6{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}{}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$. ${\displaystyle 6a_{1}^{2}a_{4}$이다.$}$

• 180도 얼굴 회전 3회:

우리는 앞의 경우와 같은 축을 중심으로 회전하지만, 지금은 축과 평행한 면의 4 사이클이 아니라 오히려 2 사이클이 있다.기여도는 $3{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ a 2 ${\displaystyle {\mathrm{}}_{}^{}}$ .${\displaystyle 3a_{1}^{2}a_{2}^{$$2$}.$}$

• 120도 정점 회전 8개:

이번에는 두 개의 정점(주 대각선의 끝점)을 통과하는 축을 중심으로 회전한다.이렇게 하면 두 개의 세 개의 얼굴 주기가 생성된다(동일한 꼭지점에서 발생한 얼굴들이 순환을 형성한다).기여도는 $8{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {3\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$. ${\displaystyle 8a_{3}^{2}.$$}$

• 180도 에지 회전 6회:

이러한 가장자리 회전은 같은 면에 충돌하지 않고 서로 평행하게 반대쪽 가장자리의 중간점을 통과하는 축을 중심으로 회전하며, 첫 번째 가장자리에서 발생하는 두 면, 두 번째 가장자리에서 발생하는 두 면, 두 정점을 공유하지만 두 가장자리와 가장자리는 없는 두 면, 즉 t가 있다.hree 2주기, 기여는 $6{\displaystyle \mathrm{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {2\mathrm{}}_{}^{}}$ a ${\displaystyle {}_{}^{}}$. ${\displaystyle 6a_{2}^{3}.$$}$

결론은 C그룹의 사이클 지수는

${\displaystyle Z(C)={\frac {1}{1}}{24}\왼쪽(a_{1}^{6}+6a_{11)}^{2}a_{4}+3a_{1}^{2}a_{2}^{2}^{2}+8a_{3}^{2}+6a_{2}^{3}\오른쪽).}$

일부 순열 그룹의 주기 지수

ID_n 그룹 E

이 그룹에는 모든 요소를 고정하는 순열이 하나 포함되어 있다(이것은 자연스러운 작용임에 틀림없다).

${\displaystyle Z(E_{n}=a_{1}^{n}.}$

순환군_n C

순환군 C는_n 원 둘레에 균등하게 간격을 두고 있는 n-곤의 회전군이다.이 소분류는 n의 각 d에 대해 φ(d) 순서 d 요소를 가지며, 여기서 φ(d)는 오일러 φ 함수로서, d에 상대적으로 소수인 자연수의 수를 d보다 적게 부여한다.C의_n 정규 표현에서 순서 d의 순열은 길이 d의 n/d 주기를 가지므로 다음과 같다.^[12]

${\displaystyle Z(C_{n}}={\frac {1}{n}\sum _{dn}\varphi (d)a_{d}^{n/d}.}$

디헤드랄군_n D

2면체 그룹은 순환 그룹과 같으나 반사도 포함한다.자연적인 작용으로 볼 때론

${\displaystyle Z(D_{n})={\frac {1}{2}}Z(C_{n})+{\begin{cases}{\frac {1}{2}}a_{1}a_{2}^{(n-1)/2},&n{\mbox{ odd, }}\\{\frac {1}{4}}\left(a_{1}^{2}a_{2}^{(n-2)/2}+a_{2}^{n/2}\right),&n{\mbox{ even.}}}\end{case}}$

교류_n 그룹 A

순열 그룹으로서의 자연 작용에서 교대 그룹의 주기 지수는 다음과 같다.

${\displaystyle Z(A_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}{\frac {1+(-1)^{j_{2}+j_{4}+\cdots }}{\prod _{k=1}^{n^{j_{k}j_{k}j_{k}!}}}\prod _{k=1}^{n}a_{k}^{j_{k}}}}$

분자는 짝수 순열의 경우 2이고 홀수 순열의 경우 0이다.${\displaystyle \frac{{1An}_{}{}_{}}{}}$= ${\displaystyle \frac{2n}{}}$! ${\$$}}}$.

대칭군_n S

자연 작용에서 대칭 그룹 S의_n 주기 지수는 다음과 같은 공식으로 주어진다.

${\displaystyle Z(S_{n})=\sum _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}{\frac {1}{1}{k=1}^{n^{k_{k}}!}}}\prod _{k=1}^{n}a_{k}^{j_{k}}}}}$

또한 완전한 Bell 다항식(bell polyomials)의 관점에서 다음과 같이 명시할 수 있다.

${\displaystyle Z(S_{n})={\frac {B_{n}(0!\,a_{1},1!\,a_{2},\dots,(n-1)!\,a_{n}}}{n!}{n!}}.}$

이 공식은 주어진 순열 모양이 몇 번 발생할 수 있는지를 세어 구한다.세 가지 단계가 있다: 먼저 n개의 라벨 세트를 하위 집합으로 분할한다. 여기서 k 크기의 $j{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$ 하위$$ 집합이 있다.그러한 모든 하위 집합은 $k{\displaystyle }$!${\displaystyle }$/ ${\displaystyle k}$ ${\displaystyle k!/k}$ 사이클의$$ 길이 k를 생성한다.그러나 우리는 동일한 크기의 사이클을 구별하지 않는다. 즉, $사이클$은 ${\displaystyle {S{}_{}}_{}}$ j ${\displaystyle {k_{}}_{}}${\$displaystyle S_{j_{k}}$에 의해 순열된다$.$ 이 수율은

$디스플레이 스타일 {\frac {n!}{\prod _{k=1}^{n}(k!)^{j_{k}}}}\prod _{k=1}^{n}\left({\frac {k!}}{k}\오른쪽)^{j_{k}}\prod _{k=1}^{n}{\frac {1}{j_{k}!}}}={\frac{n!}{\prod _{k=1}^{n}k^{j_{k}j_{k}j_{k}!}}.}$

대칭 그룹의 주기 지수에 대한 유용한 재귀 공식이 있다.${\displaystyle \mathrm{Z}}$( ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$)${\displaystyle }$= 1 ${\displaystyle Z(S_{0}}=1$}을$($를) 설정하고$$ n을 포함하는 사이클의 l 크기를 고려하십시오. 여기서 $1{\displaystyle \begin{array}{c}\mathrm{}\end{array}}$≤ ${\displaystyle \begin{array}{c}l\end{array}}$ ${\displaystyle \begin{array}{c}\le \end{array}}$ ${\displaystyle \begin{array}{c}n.\end{array}}$ ${\displaystyle$ {\$begin{matrix}1\leq l\leq$ l\leq $n.$${\displaystyle \backslash }$$end$$}}}$의 $나머지$ l - 1 ${\displaystyle${\$begin${matrix$}{n-1 \선택$ $\displaystyl-1}$ 요소를$$ 선택하는 방법이$$ 있으며$$$,{\displaystyle \begin{array}{c}\end{array}}$ 이러한 선택마다 ${\displaystyle \begin{array}{c}\frac{}{!}\end{array}}$ l! ${\$$}}{l}\end{matrix}}$ 다른 주기$$

이것은 재발을 낳는다.

${\displaystyle Z(S_{n}={\frac {1}{n!}}}\sum _{g\in S_{n}\prod _{k=1}^{na_{k}^{j_{k}(g)={\frac {1}{n!}}}\sum _{l=1}^{n}{n-1 \선택 l-1\;{\frac {l!}}{l}\;a_{l}\;(n-l)!\;Z(S_{n-l}})}$

또는

${\displaystyle Z(S_{n}}={\frac {1}{n}\sum _{l=1}^{n}a_{l}\;Z(S_{n-l}).}$

적용들

이 절 전체에 걸쳐 변수 이름을 명시적으로 포함하여 주기 지수에 대한 표기법을 약간 수정한다.따라서 순열 그룹 G에 대해 우리는 이제 다음과 같이 쓸 것이다.

${\displaystyle Z(G)=Z(G;a_{1},a_{2},\ldots,a_{n}).}$

G는 또한 X에 작용하는 그룹이 된다. G는 또한 X의 k-subset과 X의 구별되는 요소의 k-tule에 대한 작용을 1 ㎛ k ≤ n에 대해 유도한다. F와_k F는_k 각각 G의 궤도의 수를 나타낸다.관례에 따라 우리는₀ f = F = 1을₀ 설정한다.다음이 있음:^[13]

a) f에_k 대한 일반적인 생성 함수는 다음과 같다.

${\displaystyle \sum _k^{}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle {fk}_{}}$ ${\displaystyle t^{}}$ ${\displaystyle {}_{}{}^{}}$= Z${\displaystyle (G}$; ${\displaystyle 1}$+ ${\displaystyle t}$, 1${\displaystyle }$+ ${\displaystyle {t\mathrm{}}^{}}$ ${\displaystyle {}^{}}$, …${\displaystyle }$,${\displaystyle 1}$ +${\displaystyle {}^{}{t}^{}}$) ,$${\$displaystyle \sum$ _${k=0}^{n}f_{k}t^{k}}=Z(G;1+t,$ 1$+t$^{n})=$Z($G;$1+t,$ 1+t^{n}), {n}}}}}}, 1+$t^{n}),$ 및$$ {n}}

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

${\displaystyle \sum _{k=0}^{n}F_{k}t^{k}/k!=Z(G;1+t,1,\ldots ,1)}$

G를 세트 X에 작용하는 그룹이 되게 하고 X에서 Y까지의 함수를 h로 한다.G의 어떤 g에 대해서도 h(x^g)는 X에서 Y까지의 함수다.따라서 G는 X에서 Y까지의 모든 함수의 설정된 Y에^X 대한 작용을 유도한다.이 작용의 궤도의 수는 Z(G; b, b, ...,b)이며 여기서 b = Y이다.^[14]

이 결과는 궤도 계수 보조정리(번사이드의 보조정리라고도 하지만 전통적으로 번사이드의 보조정리라고도 한다)에서 따르며, 그 결과의 가중치는 폴랴의 열거 정리다.

주기 지수는 여러 변수의 다항식이며 위의 결과는 이 다항식의 특정 평가가 조합적으로 유의미한 결과를 제공한다는 것을 보여준다.다항식으로서 그것들은 또한 공식적으로 추가, 감산, 차별화 및 통합될 수 있다.심볼 콤비네이터의 영역은 이러한 공식 연산의 결과에 대한 조합 해석을 제공한다.

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

메모들

참조

• Brualdi, Richard A. (2010), "14. Pólya Counting", Introductory Combinatorics (5th ed.), Upper Saddle River, NJ: Prentice Hall, pp. 541–575, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), "15. Enumeration under group action", Combinatorics:Topics, Techniques, Algorithms, Cambridge: Cambridge University Press, pp. 245–256, ISBN 0-521-45761-0
• Dixon, John D.; Mortimer, Brian (1996), Permutation Groups, New York: Springer, ISBN 0-387-94599-7
• Roberts, Fred S.; Tesman, Barry (2009), "8.5 The Cycle Index", Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, pp. 472–479, ISBN 978-1-4200-9982-9
• Tucker, Alan (1995), "9.3 The Cycle Index", Applied Combinatorics (3rd ed.), New York: Wiley, pp. 365–371, ISBN 0-471-59504-7
• van Lint, J.H.; Wilson, R.M. (1992), "35.Pólya theory of counting", A Course in Combinatorics, Cambridge: Cambridge University Press, pp. 461–474, ISBN 0-521-42260-4

외부 링크

• Polya의 열거 정리 및 상징적 방법인 마르코 리델
• Marko Redel, 집합 / 다중 집합 연산자의 주기 지수 및 지수 공식
• Harald Fripertinger (1997). "Cycle indices of linear, affine and projective groups". Linear Algebra and Its Applications. 263: 133–156. doi:10.1016/S0024-3795(96)00530-7.
• Harald Fripertinger (1992). "Enumeration in Musical Theory". Beiträge zur Elektronischen Musik. 1.