순열

수학에서 순열(順列, 문화어: 차례무이, 영어: permutation 퍼뮤테이션^[*]) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 정의역과 공역이 같은 전단사 함수이다. ${\displaystyle n}$개의 원소에 대한 순열의 수는 ${\displaystyle n}$의 계승

${\displaystyle n!=n(n-1)(n-2)\cdots \cdot 2\cdot 1}$

다른 뜻에 대해서는 순열 (동음이의) 문서를 참고하십시오.

3개의 서로 다른 공에 대한 총 6가지의 순열

루빅스 큐브의 면에 대한 회전은 그 면의 9개의 부분에 대한 한 가지 순열이다.

과 같다.

주어진 집합의 순열은 함수의 합성에 따라 대칭군이라고 불리는 군을 이룬다. 이와 같이 주어진 집합의 전부 또는 일부 순열들로 구성된 군(즉, 대칭군의 부분군)을 순열군(順列群, 영어: permutation group)이라고 일컫기도 한다. 예를 들어, 모든 짝순열의 집합은 대칭군의 부분군이며, 이를 교대군이라고 한다.

조합론에서는 더 많은 순열의 개념들이 사용된다. 예컨대 ${\displaystyle n}$개의 원소에서 ${\displaystyle k}$개의 원소를 골라 배열하는 방법들의 가짓수는 하강 계승

${\displaystyle P(n,k)=n(n-1)\cdots (n-k+1)}$

과 같다.

정의

집합 ${\displaystyle X}$의 순열은 전단사 함수 ${\displaystyle X\to X}$이다. 유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 순열 ${\displaystyle \sigma }$은 다음과 같이 표를 통해 표기할 수 있다.

${\displaystyle \sigma ={\begin{pmatrix}1&2&\cdots &n\\\sigma (1)&\sigma (2)&\cdots &\sigma (n)\end{pmatrix}}}$

모든 ${\displaystyle X}$의 순열은 함수의 합성에 따라 군을 이루며, 이를 ${\displaystyle X}$의 대칭군 ${\displaystyle \operatorname {Sym} (X)}$ 또는 ${\displaystyle S_{X}}$이라고 한다. 유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 순열의 대칭군은 ${\displaystyle \operatorname {Sym} (n)}$ 또는 ${\displaystyle S_{n}}$으로 표기한다.

순환

양의 정수 ${\displaystyle k}$가 주어졌을 때, 집합 ${\displaystyle X}$의 길이 ${\displaystyle k}$의 순환(-循環, 영어: cycle of length ${\displaystyle k}$) ${\displaystyle {\begin{pmatrix}x_{1}&x_{2}&\cdots &x_{k}\end{pmatrix}}}$은 다음과 같은 꼴의 순열이다. (여기서 ${\displaystyle x_{i}\in X}$는 서로 다른 원소이다.)

${\displaystyle x_{1}\mapsto x_{2}\mapsto \cdots \mapsto x_{k}\mapsto x_{1}}$

${\displaystyle x\mapsto x\qquad \forall x\in X\setminus \{x_{1},x_{2},\dotsc ,x_{k}\}}$

또한, 길이 ${\displaystyle \aleph _{0}}$의 순환(-循環, 영어: cycle of length ${\displaystyle \aleph _{0}}$) 또는 무한 순환(無限循環, 영어: infinite cycle) ${\displaystyle {\begin{pmatrix}\cdots &x_{-1}&x_{0}&x_{1}&\cdots \end{pmatrix}}}$은 다음과 같은 꼴의 순열이다. (여기서 ${\displaystyle x_{i}\in X}$는 서로 다른 원소이다.)

${\displaystyle \cdots \mapsto x_{-1}\mapsto x_{0}\mapsto x_{1}\mapsto \cdots }$

${\displaystyle x\mapsto x\qquad \forall x\in X\setminus \{\dots ,x_{-1},x_{0},x_{1},\dots \}}$

특히, 호환(互換, 영어: transposition) ${\displaystyle {\begin{pmatrix}x&y\end{pmatrix}}}$은 2-순환 ${\displaystyle x\mapsto y\mapsto x}$이다. 특히, 유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 인접 호환(隣接互換, 영어: adjecent transposition) ${\displaystyle {\begin{pmatrix}x&x+1\end{pmatrix}}}$은 인접한 두 수에 대한 호환 ${\displaystyle x\mapsto x+1\mapsto x}$이다.

반전

순열 ${\displaystyle \sigma \in \operatorname {Sym} (n)}$에 대하여, 튜플 ${\displaystyle (x,y)\in \{1,2,\dotsc ,n\}^{2}}$이 다음 두 조건을 만족시키면, ${\displaystyle \sigma }$의 반전(反轉 영어: inversion)이라고 한다.

• ${\displaystyle \sigma ^{-1}(x)<\sigma ^{-1}(y)}$
• ${\displaystyle x>y}$

또한, ${\displaystyle \sigma }$의 반전 벡터(反轉-, 영어: inversion vector) ${\displaystyle \operatorname {inv\,vec} (\sigma )\in \{0,1,\dotsc ,n-1\}^{n-1}}$는 ${\displaystyle y}$번째 성분이 ${\displaystyle y}$로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다.

${\displaystyle \operatorname {inv\,vec} (\sigma )_{y}=|\{x\in \{1,2,\dotsc ,n\}\colon \sigma ^{-1}(x)<\sigma ^{-1}(y),\;x>y\}|\qquad y=1,2,\dotsc ,n-1}$

또한, ${\displaystyle \sigma }$의 반전수(反轉數, 영어: inversion number) ${\displaystyle \operatorname {inv\,num} (\sigma )}$ 또는 ${\displaystyle N(\sigma )}$는 ${\displaystyle \sigma }$의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.

궤도

순열 ${\displaystyle \sigma \in \operatorname {Sym} (X)}$의 순환군 ${\displaystyle \langle \sigma \rangle }$은 ${\displaystyle X}$의 왼쪽에서 자연스럽게 작용한다. 즉, ${\displaystyle \sigma }$가 ${\displaystyle x\in X}$에 작용한 결과는 ${\displaystyle \sigma (x)}$이다. 이 작용의 각 궤도 ${\displaystyle \langle \sigma \rangle (x)}$ (${\displaystyle x\in X}$)를 ${\displaystyle \sigma }$의 궤도(軌道, 영어: orbit)라고 한다.

순열 ${\displaystyle \sigma \in \operatorname {Sym} (n)}$의 감소량(減少量, 영어: decrement) ${\displaystyle \operatorname {dec} (\sigma )}$는 ${\displaystyle n}$에서 ${\displaystyle \sigma }$의 궤도의 개수를 뺀 것이다. 즉, 이는 다음과 같다. (이는 ${\displaystyle \sigma }$를 몇 차 대칭군의 원소로 여기는지와 무관하다.)

${\displaystyle \operatorname {dec} (\sigma )=n-|\{\langle \sigma \rangle (x)\colon x\in \{1,2,\dotsc ,n\}\}|=\sum _{\langle \sigma \rangle (x)\colon \sigma (x)\neq x}(|\langle \sigma \rangle (x)|-1)}$

부호

순열의 부호(符號, 영어: sign) ${\displaystyle \operatorname {sgn} \colon \operatorname {Sym} (n)\to \{-1,1\}}$은 다음 조건을 만족시키는 유일한 군 준동형이다.

${\displaystyle -1=\operatorname {sgn}({\begin{pmatrix}1&2\end{pmatrix}})=\operatorname {sgn}({\begin{pmatrix}2&3\end{pmatrix}})=\cdots =\operatorname {sgn}({\begin{pmatrix}n-1&n\end{pmatrix}})}$

구체적으로, ${\displaystyle \sigma }$의 부호 ${\displaystyle \operatorname {sgn}(\sigma )}$는 다음의 두 값과 같다.

${\displaystyle \operatorname {sgn}(\sigma )=(-1)^{\operatorname {inv\,num} (\sigma )}=(-1)^{\operatorname {dec} (\sigma )}}$

홀짝성

반전수·감소량·부호를 통해 유한 집합의 순열의 홀짝성(-性, 영어: parity)을 정의할 수 있다. 순열 ${\displaystyle \sigma \in \operatorname {Sym} (n)}$에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 ${\displaystyle \sigma }$를 홀순열(-順列, 영어: odd permutation)이라고 한다.

• ${\displaystyle \operatorname {inv\,num} (\sigma )}$는 홀수이다.
• ${\displaystyle \operatorname {dec} (\sigma )}$는 홀수이다.
• ${\displaystyle \operatorname {sgn}(\sigma )=-1}$

홀순열이 아닌 순열을 짝순열(-順列, 영어: even permutation)이라고 한다. 즉, 순열 ${\displaystyle \sigma \in \operatorname {Sym} (n)}$에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 ${\displaystyle \sigma }$를 짝순열이라고 한다.

• ${\displaystyle \operatorname {inv\,num} (\sigma )}$는 짝수이다.
• ${\displaystyle \operatorname {dec} (\sigma )}$는 짝수이다.
• ${\displaystyle \operatorname {sgn}(\sigma )=1}$

순열의 수

유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 모든 순열의 수는 ${\displaystyle n}$의 계승 ${\displaystyle n!}$이다. 이들 가운데 홀순열의 수는 다음과 같다.

${\displaystyle {\begin{cases}0&n=0,1\\n!/2&n\geq 2\end{cases}}}$

또한, 짝순열의 수는 다음과 같다.

${\displaystyle {\begin{cases}1&n=0,1\\n!/2&n\geq 2\end{cases}}}$

순열이 고정점을 갖지 않는다면, 이 순열을 완전 순열이라고 한다. 유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 완전 순열의 수는 준계승 ${\displaystyle !n}$으로 주어진다.

유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 순열의 항이 번갈아 가면서 커졌다 작아졌다 (또는 작아졌다 커졌다) 하면, 이 순열을 교대 순열(交代順列, 영어: alternating permutation)이라고 한다. 교대 순열의 수 ${\displaystyle A_{n}}$은 점화식을 통해 주어진다.

조합론에서는 조금 더 일반화된 순열의 수가 연구되며, 이는 다음과 같다.

k-순열

음이 아닌 정수 ${\displaystyle k}$가 주어졌을 때, 집합 ${\displaystyle X}$의 ${\displaystyle k}$-순열(-順列, 영어: ${\displaystyle k}$-permutation)은 단사 함수 ${\displaystyle \{1,2,\dotsc ,k\}\to X}$이다. 특히, 유한 집합 ${\displaystyle X=\{1,2,\dotsc ,n\}}$의 경우 이를 ${\displaystyle n}$의 ${\displaystyle k}$-순열이라고 한다. 이 경우, 원래의 유한 순열은 ${\displaystyle n}$의 ${\displaystyle n}$-순열이다. 풀어 말해, ${\displaystyle n}$의 ${\displaystyle k}$-순열은 서로 다른 ${\displaystyle n}$개의 원소 가운데 중복 없이 ${\displaystyle k}$개를 골라서 순서 있게 나열한 것이다. ${\displaystyle n}$의 ${\displaystyle k}$-순열의 수는 ${\displaystyle n^{\underline {k}},{}_{n}P_{k},P_{n,k},P(n,k)}$와 같이 표기하며, 다음과 같이 하강 계승으로 주어진다.

${\displaystyle n^{\underline {k}}=n(n-1)(n-2)\cdots (n-k+1)}$

예를 들어, 6곡의 노래 가운데 3곡을 골라 재생 목록을 만드는 방법의 수는 다음과 같다.

${\displaystyle 6^{\underline {3}}=6\times 5\times 4=120}$

${\displaystyle n}$의 ${\displaystyle k}$-순열의 수와 ${\displaystyle n}$의 ${\displaystyle k}$-조합의 수(이항 계수)의 관계는 다음과 같다.

${\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}}$

중복 순열

음이 아닌 정수 ${\displaystyle k}$가 주어졌을 때, 집합 ${\displaystyle X}$의 ${\displaystyle k}$-중복 순열(重複順列, 영어: ${\displaystyle k}$-permutation with repetition)은 ${\displaystyle X}$의 ${\displaystyle k}$-튜플을 뜻한다. 특히, 유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 ${\displaystyle k}$-튜플을 생각할 수 있으며, 이는 풀어 말해 ${\displaystyle n}$개의 원소 가운데 중복이 가능한 ${\displaystyle k}$개를 골라서 순서 있게 나열한 것이다. 그 수는 ${\displaystyle n^{k}}$이다. 예를 들어, 26개의 알파벳으로 구성된 3글자 단어의 수는 ${\displaystyle 26^{3}=17576}$이다.

중복집합 순열

집합의 순열과 달리, 중복집합 순열에서는 같은 색깔의 원소들을 구별이 불가능하다고 여기며, 이에 따라 순열의 수가 줄어들게 된다.

크기 ${\displaystyle n}$의 중복집합 ${\displaystyle n_{1}\{1\}+n_{2}\{2\}+\cdots +n_{k}\{k\}}$의 중복집합 순열(重複集合順列, 영어: multiset permutation) 또는 같은 것이 있는 순열(-順列)은 다음 조건을 만족시키는 함수 ${\displaystyle \sigma \colon \{1,2,\dotsc ,n\}\to \{1,2,\dotsc ,k\}}$이다.

${\displaystyle |\sigma ^{-1}(x)|=m(x)\qquad x=1,2,\dotsc ,k}$

풀어 말해, 중복집합 순열은 중복집합의 각 원소를 그 중복도만큼씩 순서 있게 나열한 것이다. 다시 말해, 원래의 순열의 정의에서, 주어진 방식대로 짝지어진 원소들을 같다고 여겨 얻는 개념이다. 그 수는 다음과 같이 다항 계수로 주어진다.

${\displaystyle {\binom {n}{n_{1},n_{2},\dotsc ,n_{k}}}={\frac {n!}{n_{1}!n_{2}!\cdots n_{k}!}}}$

예를 들어, 영어 단어 "MISSISSIPPI"의 어구전철의 수는 다음과 같다.

${\displaystyle {\binom {11}{1,4,4,2}}={\frac {11!}{1!\times 4!\times 4!\times 2!}}=34650}$

원순열

유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 원순열(圓順列, 영어: circular permutation)은 ${\displaystyle \langle {\begin{pmatrix}1&2&\cdots &n\end{pmatrix}}\rangle }$의 ${\displaystyle \operatorname {Sym} (n)}$ 위의 오른쪽 작용의 궤도를 뜻한다. 이는 ${\displaystyle \{1,2,\dotsc ,n\}}$의 ${\displaystyle n}$-순환(즉, ${\displaystyle {\begin{pmatrix}1&2&\cdots &n\end{pmatrix}}}$의 켤레 원소)과 일대일 대응한다. 풀어 말해, 이는 ${\displaystyle n}$개의 원소를 원형 탁자에 둘러앉힌 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 원순열의 수는 다음과 같다.

${\displaystyle {\begin{cases}1&n=0\\(n-1)!&n\geq 1\end{cases}}}$

이는 원래의 ${\displaystyle n!}$에서 겹치는 배수인 ${\displaystyle n}$을 나눈 것이다. 예를 들어, 중심 대칭 시계 속의 1~12를 다시 배열하였을 때 얻을 수 있는 서로 다른 기능의 시계의 수는 ${\displaystyle 11!=39916800}$이다.

염주 순열

유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 염주 순열(念珠順列) 또는 목걸이 순열(영어: necklace permutation)은 ${\displaystyle \langle {\begin{pmatrix}1&2&\cdots &n\end{pmatrix}},n+1-\operatorname {id} _{n}\rangle }$의 ${\displaystyle \{1,2,\dotsc ,n\}}$ 위의 오른쪽 작용의 궤도를 뜻한다. 풀어 말해, 이는 ${\displaystyle n}$개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다.

${\displaystyle {\begin{cases}1&n=0,1,2\\(n-1)!/2&n\geq 3\end{cases}}}$

이는 원래의 ${\displaystyle n!}$에서 겹치는 배수인 ${\displaystyle 2n}$을 나눈 것이다. 예를 들어, 팔찌에 7개의 무지개색 구슬을 꿰었을 때 얻을 수 있는 서로 다른 모양의 팔찌의 수는 ${\displaystyle 6!/2=360}$이다. 처음 몇 염주 순열의 수는 다음과 같다. (${\displaystyle n=1,2,\dots }$)

1, 1, 1, 3, 12, 60, 360, 2520, ... (OEIS의 수열 A001710)

성질

연산에 대한 닫힘

집합 ${\displaystyle X}$의 순열의 집합 ${\displaystyle \operatorname {Sym} (X)}$는 군을 이룬다. 즉, 다음이 성립한다.

• 항등 함수 ${\displaystyle \operatorname {id} _{X}\colon x\mapsto x}$는 ${\displaystyle X}$의 순열이다. (이는 군의 항등원이다.)
• 임의의 ${\displaystyle X}$의 순열 ${\displaystyle \sigma ,\tau }$에 대하여, 그 합성 ${\displaystyle \tau \sigma \colon x\mapsto \tau (\sigma (x))}$ 역시 ${\displaystyle X}$의 순열이다. (이는 군의 곱셈이며, 결합 법칙을 만족한다.)
• 임의의 ${\displaystyle X}$의 순열 ${\displaystyle \sigma }$에 대하여, 그 역 ${\displaystyle \sigma ^{-1}\colon \sigma (x)\mapsto x}$ 역시 ${\displaystyle X}$의 순열이다. (이는 군의 역원 연산이다.)

반전수

유한 집합의 순열의 반전수·감소량에 대하여, 다음과 같은 부등식이 성립한다.

${\displaystyle 0\leq \operatorname {inv\,num} (\sigma )\leq {\binom {n}{2}}}$

${\displaystyle 0\leq \operatorname {dec} (\sigma )\leq {\begin{cases}0&n=0\\n-1&n\geq 1\end{cases}}}$

또한, 다음과 같은 점화식이 성립한다.

${\displaystyle \operatorname {inv\,num} (\sigma {\begin{pmatrix}x&x+1\end{pmatrix}})={\begin{cases}\operatorname {inv\,num} (\sigma )+1&\sigma (x)<\sigma (x+1)\\\operatorname {inv\,num} (\sigma )-1&\sigma (x)>\sigma (x+1)\end{cases}}}$

${\displaystyle \operatorname {dec} ({\begin{pmatrix}x&y\end{pmatrix}}\sigma )={\begin{cases}\operatorname {dec} (\sigma )+1&y\not \in \{\sigma (x),\sigma ^{2}(x),\dots \}\\\operatorname {dec} (\sigma )-1&y\in \{\sigma (x),\sigma ^{2}(x),\dots \}\end{cases}}}$

또한, 서로 역순열의 반전수·감소량는 서로 같다. 즉, 다음과 같은 항등식이 성립한다.

${\displaystyle \operatorname {inv\,num} (\sigma )=\operatorname {inv\,num} (\sigma ^{-1})}$

${\displaystyle \operatorname {dec} (\sigma )=\operatorname {dec} (\sigma ^{-1})}$

순환 분해

순열 ${\displaystyle \sigma \in \operatorname {Sym} (X)}$의 궤도 ${\displaystyle \langle \sigma \rangle (x)}$ (${\displaystyle x\in X}$)들은 ${\displaystyle X}$의 분할을 이루며, 각 궤도에서의 제한은 다음과 같이 어떤 순환이다.

${\displaystyle \sigma |_{\langle \sigma \rangle (x)}={\begin{cases}{\begin{pmatrix}\cdots &\sigma ^{-1}(x)&x&\sigma (x)&\cdots \end{pmatrix}}&|\langle \sigma \rangle (x)|\geq \aleph _{0}\\{\begin{pmatrix}x&\sigma (x)&\cdots &\sigma ^{|\langle \sigma \rangle (x)|-1}(x)\end{pmatrix}}&|\langle \sigma \rangle (x)|<\aleph _{0}\end{cases}}}$

만약 비자명 궤도(=크기가 1이 아닌 궤도)의 개수가 유한하다면, ${\displaystyle \sigma }$는 이러한 서로소 비자명 순환들의 곱으로 분해할 수 있다. 서로소 순환들은 항상 가환한데, ${\displaystyle \sigma }$의 서로소 비자명 순환 분해는 곱하는 순서를 따지지 않으면 유일하다. 이러한 분해를 ${\displaystyle \sigma }$의 순환 분해(循環分解, 영어: cycle decomposition)라고 한다. 순환 분해의 길이(=곱해지는 비자명 순환의 개수)는 비자명 궤도의 개수

${\displaystyle |\{\langle \sigma \rangle (x)\colon \sigma (x)\neq x\}|}$

와 같다. 특히, 쌍대 유한 고정점 집합을 갖는 순열은 항상 서로소 비자명 유한 순환들의 곱으로 유일하게 분해할 수 있다. 특히, 유한 집합의 순열 ${\displaystyle \sigma \in \operatorname {Sym} (n)}$의 순환 분해는 구체적으로 다음과 같다.

${\displaystyle \sigma ={\begin{pmatrix}\min\{x\colon \sigma (x)\neq x\}&\cdots \end{pmatrix}}{\begin{pmatrix}\min(\{x\colon \sigma (x)\neq x\}\setminus \langle \sigma \rangle (\min\{x\colon \sigma (x)\neq x\}))&\cdots \end{pmatrix}}\cdots }$

호환 분해

유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻는다. 또한, 구체적으로 다음과 같은 분해식들이 성립한다.

${\displaystyle {\begin{pmatrix}x_{1}&x_{2}&\cdots &x_{j}&\cdots &x_{k}\end{pmatrix}}={\begin{pmatrix}x_{1}&x_{2}&\cdots &x_{j}\end{pmatrix}}{\begin{pmatrix}x_{j}&x_{j+1}&\cdots &x_{k}\end{pmatrix}}={\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}}{\begin{pmatrix}x_{2}&x_{3}\end{pmatrix}}\cdots {\begin{pmatrix}x_{k-1}&x_{k}\end{pmatrix}}}$

${\displaystyle {\begin{pmatrix}x_{1}&x_{2}&\cdots &x_{k}\end{pmatrix}}={\begin{pmatrix}x_{1}&x_{k}\end{pmatrix}}{\begin{pmatrix}x_{1}&x_{k-1}\end{pmatrix}}\cdots {\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}}}$

홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다.

유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 ${\displaystyle \sigma \in \operatorname {Sym} (n)}$에 대하여, 다음이 성립한다.

${\displaystyle \operatorname {dec} (\sigma )=\min\{l\in \mathbb {N} \colon \sigma ={\begin{pmatrix}x_{1}&y_{1}\end{pmatrix}}\cdots {\begin{pmatrix}x_{l}&y_{l}\end{pmatrix}},\;x_{i},y_{i}\in \{1,2,\dotsc ,n\}\}}$

인접 호환 분해

유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다.

${\displaystyle {\begin{pmatrix}x&y\end{pmatrix}}={\begin{pmatrix}x&x+1&\cdots &y\end{pmatrix}}{\begin{pmatrix}y-1&y-2&\cdots &x\end{pmatrix}}={\begin{pmatrix}x&x+1\end{pmatrix}}\cdots {\begin{pmatrix}y-1&y\end{pmatrix}}{\begin{pmatrix}y-1&y-2\end{pmatrix}}\cdots {\begin{pmatrix}x+1&x\end{pmatrix}}}$

유한 집합의 순열의 인접 호환 분해의 최소 길이는 반전수와 같다. 즉, 순열 ${\displaystyle \sigma \in \operatorname {Sym} (n)}$에 대하여, 다음이 성립한다.

${\displaystyle \operatorname {inv\,num} (\sigma )=\min\{l\in \mathbb {N} \colon \sigma ={\begin{pmatrix}x_{1}&x_{1}+1\end{pmatrix}}\cdots {\begin{pmatrix}x_{l}&x_{l}+1\end{pmatrix}},\;x_{i}\in \{1,2,\dotsc ,n-1\}\}}$

군론적 성질

순열 ${\displaystyle \sigma \in \operatorname {Sym} (X)}$의 위수는 다음과 같다.

${\displaystyle \operatorname {ord} (\sigma )={\begin{cases}\operatorname {lcm} _{x\in X}|\langle \sigma \rangle (x)|&\{|\langle \sigma \rangle (x)|\colon x\in X\}\in {\mathcal {P}}_{<\aleph _{0}}(\mathbb {Z} ^{+})\\\aleph _{0}&\{|\langle \sigma \rangle (x)|\colon x\in X\}\not \in {\mathcal {P}}_{<\aleph _{0}}(\mathbb {Z} ^{+})\end{cases}}}$

특히, 순환의 위수는 그 길이와 같다.

대칭군 ${\displaystyle \operatorname {Sym} (X)}$의 켤레류는 ${\displaystyle |X|}$를 양의 기수들의 합으로 나타내는 방법과 자연스럽게 일대일 대응한다. 즉, 순열 ${\displaystyle \sigma ,\tau \in \operatorname {Sym} (X)}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle \sigma ,\tau }$는 서로 켤레이다.
• ${\displaystyle \sigma ,\tau }$의 궤도의 개수와 각 궤도의 크기는 각각 서로 같다.

대칭군 ${\displaystyle \operatorname {Sym} (n)}$의 켤레류는 ${\displaystyle n}$의 분할과 자연스럽게 일대일 대응한다. 즉, 순열 ${\displaystyle \sigma ,\tau \in \operatorname {Sym} (n)}$에 대하여, 다음 두 조건이 서로 동치이다.

• ${\displaystyle \sigma ,\tau }$는 서로 켤레이다.
• ${\displaystyle \sigma ,\tau }$의 서로소 순환 분해의 길이와 각 순환의 길이는 각각 서로 같다.

유한 집합의 순열의 홀짝성에 대하여, 다음이 성립한다.

• 항등 함수는 짝순열이다.
• 두 홀순열의 합성은 짝순열이며, 두 짝순열의 합성 역시 짝순열이다. 홀순열과 짝순열의 합성은 홀순열이다.
• 홀순열의 역은 홀순열이며, 짝순열의 역은 짝순열이다.

달리 말해, 순열의 부호 함수 ${\displaystyle \operatorname {sgn} \colon \operatorname {Sym} (n)\to \{-1,1\}}$는 군 준동형이다. 즉, 다음이 성립한다.

${\displaystyle \operatorname {sgn}(\operatorname {id} _{n})=1}$

${\displaystyle \operatorname {sgn}(\tau \sigma )=\operatorname {sgn}(\tau )\operatorname {sgn}(\sigma )}$

${\displaystyle \operatorname {sgn}(\sigma ^{-1})=\operatorname {sgn}(\sigma )}$

이에 따라, 짝순열들은 대칭군의 부분군 ${\displaystyle \operatorname {Alt} (n)}$을 이루며, 이를 교대군이라고 한다. 사실, 교대군은 이 부호 함수의 핵이므로, 대칭군의 정규 부분군이다.

${\displaystyle \operatorname {Alt} (n)=\ker \operatorname {sgn} \vartriangleleft \operatorname {Sym} (n)}$

홀순열의 집합은 부분군이 아니다. 또한, ${\displaystyle n=0,1}$의 경우 홀순열이 존재하지 않는다. 그러나, ${\displaystyle n\geq 2}$의 경우 홀순열의 집합은 크기가 교대군과 같으며, 교대군의 (자기 자신을 제외하면 유일한) 잉여류이다.

예

순열의 합성의 한 가지 예는 다음과 같다.

${\displaystyle {\begin{pmatrix}1&2&3&4&5\\3&2&1&5&4\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}={\begin{pmatrix}2&5&4&3&1\\2&4&5&1&3\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5\\2&4&5&1&3\end{pmatrix}}}$

순열의 역의 한 가지 예는 다음과 같다.

${\displaystyle {\begin{pmatrix}1&2&3&4&5&6&7\\3&1&4&7&6&5&2\end{pmatrix}}^{-1}={\begin{pmatrix}2&7&1&3&6&5&4\\1&2&3&4&5&6&7\end{pmatrix}}^{-1}={\begin{pmatrix}1&2&3&4&5&6&7\\2&7&1&3&6&5&4\end{pmatrix}}}$

순열의 서로소 순환 분해의 한 가지 예는 다음과 같다.

${\displaystyle {\begin{pmatrix}1&2&3&4&5\\4&1&5&2&3\end{pmatrix}}={\begin{pmatrix}1&4&2&3&5\\4&2&1&5&3\end{pmatrix}}={\begin{pmatrix}1&4&2\end{pmatrix}}{\begin{pmatrix}3&5\end{pmatrix}}}$

순열의 홀짝성의 몇 가지 예는 다음과 같다.

• 항등 함수는 짝순열이다.
• 호환은 홀순열이다.
• 짝수 길이의 순환은 홀순열이다.
• 홀수 길이의 순환은 항상 짝순열이다.

크기 3의 대칭군 ${\displaystyle \operatorname {Sym} (3)}$의 켤레류는 다음과 같다.

${\displaystyle {\begin{pmatrix}1&2&3\end{pmatrix}}\sim {\begin{pmatrix}1&3&2\end{pmatrix}}}$

${\displaystyle {\begin{pmatrix}1&2\end{pmatrix}}{\begin{pmatrix}3\end{pmatrix}}\sim {\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}2\end{pmatrix}}\sim {\begin{pmatrix}2&3\end{pmatrix}}{\begin{pmatrix}1\end{pmatrix}}}$

${\displaystyle {\begin{pmatrix}1\end{pmatrix}}{\begin{pmatrix}2\end{pmatrix}}{\begin{pmatrix}3\end{pmatrix}}}$

이들에 대응하는 3의 분할은 각각 다음과 같다.

${\displaystyle 3=3}$

${\displaystyle 3=2+1}$

${\displaystyle 3=1+1+1}$

순열의 반전수의 몇 가지 예는 다음과 같다.

${\displaystyle \operatorname {inv\,num} (\operatorname {id} _{n})=0}$

${\displaystyle \operatorname {inv\,num} ({\begin{pmatrix}x&y\end{pmatrix}})=|\{(y,x+1),(y,x+2),\dotsc ,(y,y-1),(x+1,x),(x+2,x),\dotsc ,(y-1,x),(y,x)\}|=2|y-x|-1}$

${\displaystyle \operatorname {inv\,num} ({\begin{pmatrix}1&2&\cdots &n\\n&n-1&\cdots &1\end{pmatrix}})={\binom {n}{2}}={\begin{cases}0&n=0,1\\n(n-1)/2&n\geq 2\end{cases}}}$

관련 개념

순열 행렬

 이 부분의 본문은 순열 행렬입니다.

순열의 합성은 순열 행렬의 곱셈에 대응한다.

유한 집합 ${\displaystyle \{1,2,\dotsc ,n\}}$의 순열은 ${\displaystyle n\times n}$ 순열 행렬과 자연스럽게 일대일 대응한다.

같이 보기

• 스테인하우스-존슨-트로터 알고리즘

외부 링크

• “Permutation of a set”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
  • “Permutation”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
  • “Signature (permutation)”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
• Weisstein, Eric Wolfgang. “Permutation”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Inverse permutation”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Permutation cycle”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Cyclic permutation”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Transposition”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Permutation inversion”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Inversion vector”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Even permutation”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Odd permutation”. 《Wolfram MathWorld》 (영어). Wolfram Research.
  • Weisstein, Eric Wolfgang. “Circular permutation”. 《Wolfram MathWorld》 (영어). Wolfram Research.
• “Permutation”. 《nLab》 (영어).
  • “Signature of a permutation”. 《nLab》 (영어).
• “Permutation”. 《Groupprops》 (영어).
  • “Two-line notation for permutations”. 《Groupprops》 (영어).
  • “One-line notation for permutations”. 《Groupprops》 (영어).
  • “Cycle decomposition for permutations”. 《Groupprops》 (영어).
  • “Understanding the cycle decomposition”. 《Groupprops》 (영어).
• “Permutation”. 《PlanetMath》 (영어).
  • “Cyclic permutation”. 《PlanetMath》 (영어).
• “Definition:Permutation”. 《ProofWiki》 (영어).
  • “Definition:Cyclic permutation”. 《ProofWiki》 (영어).
  • “Definition:Cycle decomposition”. 《ProofWiki》 (영어).
  • “Definition:Transposition”. 《ProofWiki》 (영어).
  • “Definition:Sign of permutation”. 《ProofWiki》 (영어).
  • “Definition:Sign of permutation on n letters”. 《ProofWiki》 (영어).
  • “Definition:Parity (permutation)”. 《ProofWiki》 (영어).
  • “Definition:Permutation on polynomial”. 《ProofWiki》 (영어).
  • “Construction of permutations”. 《ProofWiki》 (영어).
  • “Composite of permutations is permutation”. 《ProofWiki》 (영어).
  • “Inverse of permutation is permutation”. 《ProofWiki》 (영어).
  • “Existence and uniqueness of cycle decomposition”. 《ProofWiki》 (영어).
  • “Cycle decomposition of conjugate”. 《ProofWiki》 (영어).
  • “k-cycle can be factored into transpositions”. 《ProofWiki》 (영어).
  • “Parity of k-cycle”. 《ProofWiki》 (영어).
  • “Number of permutations”. 《ProofWiki》 (영어).