순열의 홀짝성

1. 개요[편집]

---

순열(permutation)을 다음과 같이 정의해볼 수 있다.

주어진 물건 가운데서 몇 개를 취하여 어떤 순서로 나열하는 일. n개의 것에서 r개를 취한 순열의 수는 [math({}_n{\rm P}_r)][1]

외국에서는 도널드 커누스가 제안한 [math(n^{\underline r})]가 많이 쓰인다.

로 나타낸다.
일반적으로 [math(\displaystyle {}_n{\rm P}_r=n(n-1)(n-2)……(n-r+1)= {{n!}\over{(n-r)!}} )]이다. (순열 - 표준국어대사전)

따라서 n개의 것에서 n개를 취하여 나열한다면 그 모든 경우의 수는 계승 [math(n!)]이다.
이것은 순열의 홀짝성(parity)에 있어서 주요한 컨텍스트(맥락,context)라고 할수있다. 팩토리얼은 그 성질상 항상 짝수개이다. 따라서 이러한 맥락(context)은 그 기순열(홀순열)의 개수 만큼 그 우순열(짝순열) 역시 똑같은 개수가 존재하는 대칭성을 이룰수있는것과 관련있다. [2][3]

2. 홀짝성[편집]

---

순열의 홀짝성(parity)은 다음과 같은 성질을 보여준다.[가]

• 우순열과 우순열의 합성은 우순열이며 기순열과 기순열의 합성도 우순열이다.
• 우(기)순열과 기(우)순열의 합성은 기순열이다.

2.1. 예[편집]

---

순열의 정의에 따라 모든 순열을 조사하였다면 순열의 홀짝성(parity)에 따라 그 순열들을 자기 자신으로 한번 합성연산함으로써 빠르게 우순열(짝순열)을 조사할수있다. [가] 따라서 [math( \text{짝순열} ={{\text{짝순열} + \text{홀순열}}\over{2}} )]이다.

2.2. 순열 합성함수의 예[편집]

---

P={1,2,3}이고 집합P 에서 6개의 치환군(순열군,S_,P,)은 다음과 같이 대칭성을 갖는 대칭군(S_,3,)임을 조사할수있다.
이제 S_,3, 와 [math(\circ)](합성함수)는 군(group)의 공리를 만족시킬수있다.
순열의 홀짝성(parity)에서 우(짝)순열과 우(짝)순열의 합성은 우순열이고 기(홀)순열과 기(홀)순열의 합성도 우순열이므로
[math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} )]
[math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} )]
[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} )]
[math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} )]
[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} )]
[math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} )]
위와같이 순환군(cyclic group) 의 첫번째 합성에서 대칭군 S_,3, 의 우순열(짝순열)로 만 이루어진 교대군(alternating group) S_,A, 를 조사할수있다.
S_,A, = [math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix})]

3. 우순열의 중첩[편집]

---

원시원소가 3개인 P={1,2,3}인 집합P 에서 6개의 순열군(S_,P,)은 자기 자신으로 한번 합성연산에서 [math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix})]우순열의 중첩(겹침)을 4번이나 보여준다. 이러한 우순열의 중첩(겹침) 원소들은 위수가 커질수록 그 군(group)의 부분군인 교대군의 가해성(solvability) 조사에서 라그랑주 정리와 관련해 교대군(alternating group)속의 교대군이라고 할수있는 중요한 역할을 한다고 알려져있다.[4][5][6]

4. 관련 문서[편집]

---

• 순열 생성 알고리즘