순열의 홀짝성

1. 개요2. 홀짝성

2.1. 예2.2. 순열 합성함수의 예

3. 우순열의 중첩4. 관련 문서

1. 개요

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

주어진 물건 가운데서 몇 개를 취하여 어떤 순서로 나열하는 일. n개의 것에서 r개를 취한 순열의 수는 [math({}_n{\rm P}_r)][1]로 나타낸다.
일반적으로 [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,₃,)임을 조사할수있다.

(123)
(231)
(312)

(321)
(132)
(213)

이제 S,₃, 와 [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,₃, 의 우순열(짝순열)로 만 이루어진 교대군(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)속의 교대군이라고 할 수 있는 중요한 역할을 한다고 알려져 있다.[6][7][8]

4. 관련 문서

순열 생성 알고리즘

[1] 외국에서는 도널드 커누스가 제안한 [math(n^{\underline r})]가 많이 쓰인다. [2] <JSTOR>journal article On the Definition of Even and Odd Permutations W. Phillips The American Mathematical Monthly Vol. 74, No. 10 (Dec., 1967), pp. 1249-1251 (3 pages) Published By: Taylor & Francis, Ltd. doi:10.2307/2315694 https://www.jstor.org/stable/2315694 [3] \[참고\] 사이언스올 -홀순열(odd permutation) https://www.scienceall.com/%ED%99%80%EC%88%9C%EC%97%B4odd-permutation/ [가] 긱스포기스 - Even and Odd Permutations and their theorems https://www.geeksforgeeks.org/even-and-odd-permutations-and-their-theorems/ [가] [6] <Project Gutenberg> Groups of the Order p^m Which Contain Cyclic Subgroups of Order p^(m-3) by Neikirk, Lewis Irving 1905 https://www.gutenberg.org/ebooks/9930 [7] Theory of Groups of Finite Order by William Burnside 1897 CAMBRIDGE: AT THE UNIVERSITY PRESS https://www.gutenberg.org/ebooks/40395 [8] <Project Gutenberg> journal article, Generation of Permutations by Adjacent Transposition, Selmer M. Johnson, Mathematics of Computation, Vol. 17, No. 83 (Jul., 1963), pp. 282-285 (4 pages), Published By: American, Mathematical Society, Mathematics of Computation, doi:10.2307/2003846 https://www.jstor.org/stable/2003846