순열 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻}}
[[파일:Permutations RGB.svg|대체글=빨강·초록·파랑의 공을 6가지의 순서대로 배열한 것|섬네일|3개의 서로 다른 공에 대한 총 6가지의 순열]]
[[파일:Rubik's cube.svg|대체글=3x3x3 루빅스 큐브|섬네일|[[루빅스 큐브]]의 면에 대한 회전은 그 면의 9개의 부분에 대한 한 가지 순열이다.]]
[[수학]]에서 '''순열'''(順列, {{문화어|차례무이}}, {{llang|en|permutation|퍼뮤테이션}}) 또는 '''치환'''(置換)은 순서가 부여된 임의의 [[집합]]을 다른 순서로 뒤섞는 연산이다. 즉, [[정의역]]과 [[공역]]이 같은 [[전단사 함수]]이다. <math>n</math>개의 원소에 대한 순열의 수는 <math>n</math>의 [[계승 (수학)|계승]]
:<math>n!=n(n-1)(n-2)\cdots\cdot 2\cdot 1</math>
과 같다.

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

[[조합론]]에서는 더 많은 순열의 개념들이 사용된다. 예컨대 <math>n</math>개의 원소에서 <math>k</math>개의 원소를 골라 배열하는 방법들의 가짓수는 [[하강 계승]]
:<math>P(n,k)=n(n-1)\cdots(n-k+1)</math>
과 같다.

== 정의 ==
집합 <math>X</math>의 '''순열'''은 [[전단사 함수]] <math>X\to X</math>이다. [[유한 집합]] <math>\{1,2,\dotsc,n\}</math>의 순열 <math>\sigma</math>은 다음과 같이 표를 통해 표기할 수 있다.
:<math>\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}</math>
모든 <math>X</math>의 순열은 [[함수의 합성]]에 따라 [[군 (수학)|군]]을 이루며, 이를 <math>X</math>의 '''[[대칭군]]''' <math>\operatorname{Sym}(X)</math> 또는 <math>S_X</math>이라고 한다. 유한 집합 <math>\{1,2,\dotsc,n\}</math>의 순열의 대칭군은 <math>\operatorname{Sym}(n)</math> 또는 <math>S_n</math>으로 표기한다.

=== 순환 ===
양의 정수 <math>k</math>가 주어졌을 때, 집합 <math>X</math>의 '''길이 <math>k</math>의 순환'''(-循環, {{llang|en|cycle of length <math>k</math>}}) <math>\begin{pmatrix}x_1&x_2&\cdots&x_k\end{pmatrix}</math>은 다음과 같은 꼴의 순열이다. (여기서 <math>x_i\in X</math>는 서로 다른 원소이다.)
:<math>x_1\mapsto x_2\mapsto\cdots\mapsto x_k\mapsto x_1</math>
:<math>x\mapsto x\qquad\forall x\in X\setminus\{x_1,x_2,\dotsc,x_k\}</math>
또한, '''길이 <math>\aleph_0</math>의 순환'''(-循環, {{llang|en|cycle of length <math>\aleph_0</math>}}) 또는 '''무한 순환'''(無限循環, {{llang|en|infinite cycle}}) <math>\begin{pmatrix}\cdots&x_{-1}&x_0&x_1&\cdots\end{pmatrix}</math>은 다음과 같은 꼴의 순열이다. (여기서 <math>x_i\in X</math>는 서로 다른 원소이다.)
:<math>\cdots\mapsto x_{-1}\mapsto x_0\mapsto x_1\mapsto\cdots</math>
:<math>x\mapsto x\qquad\forall x\in X\setminus\{\dots,x_{-1},x_0,x_1,\dots\}</math>
특히, '''호환'''(互換, {{llang|en|transposition}}) <math>\begin{pmatrix}x&y\end{pmatrix}</math>은 2-순환 <math>x\mapsto y\mapsto x</math>이다. 특히, 유한 집합 <math>\{1,2,\dotsc,n\}</math>의 '''인접 호환'''(隣接互換, {{llang|en|adjecent transposition}}) <math>\begin{pmatrix}x&x+1\end{pmatrix}</math>은 인접한 두 수에 대한 호환 <math>x\mapsto x+1\mapsto x</math>이다.

=== 반전 ===
순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, [[튜플]] <math>(x,y)\in\{1,2,\dotsc,n\}^2</math>이 다음 두 조건을 만족시키면, <math>\sigma</math>의 '''반전'''(反轉 {{llang|en|inversion}})이라고 한다.
* <math>\sigma^{-1}(x)<\sigma^{-1}(y)</math>
* <math>x>y</math>
또한, <math>\sigma</math>의 '''반전 벡터'''(反轉-, {{llang|en|inversion vector}}) <math>\operatorname{inv\,vec}(\sigma)\in\{0,1,\dotsc,n-1\}^{n-1}</math>는 <math>y</math>번째 성분이 <math>y</math>로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다.
:<math>\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</math>
또한, <math>\sigma</math>의 '''반전수'''(反轉數, {{llang|en|inversion number}}) <math>\operatorname{inv\,num}(\sigma)</math> 또는 <math>N(\sigma)</math>는 <math>\sigma</math>의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.

=== 궤도 ===
순열 <math>\sigma\in\operatorname{Sym}(X)</math>의 [[순환군]] <math>\langle\sigma\rangle</math>은 <math>X</math>의 왼쪽에서 자연스럽게 [[군의 작용|작용]]한다. 즉, <math>\sigma</math>가 <math>x\in X</math>에 작용한 결과는 <math>\sigma(x)</math>이다. 이 작용의 각 궤도 <math>\langle\sigma\rangle(x)</math> (<math>x\in X</math>)를 <math>\sigma</math>의 '''궤도'''(軌道, {{llang|en|orbit}})라고 한다.

순열 <math>\sigma\in\operatorname{Sym}(n)</math>의 '''감소량'''(減少量, {{llang|en|decrement}}) <math>\operatorname{dec}(\sigma)</math>는 <math>n</math>에서 <math>\sigma</math>의 [[군 작용|궤도]]의 개수를 뺀 것이다. 즉, 이는 다음과 같다. (이는 <math>\sigma</math>를 몇 차 대칭군의 원소로 여기는지와 무관하다.)
:<math>\operatorname{dec}(\sigma)=n-|\{\langle\sigma\rangle(x)\colon x\in\{1,2,\dotsc,n\}\}|=
\sum_{\langle\sigma\rangle(x)\colon\sigma(x)\ne x}(|\langle\sigma\rangle(x)|-1)</math>

=== 부호 ===
순열의 '''부호'''(符號, {{llang|en|sign}}) <math>\sgn\colon\operatorname{Sym}(n)\to\{-1,1\}</math>은 다음 조건을 만족시키는 유일한 [[군 준동형]]이다.
:<math>-1=\sgn(\begin{pmatrix}1&2\end{pmatrix})=\sgn(\begin{pmatrix}2&3\end{pmatrix})=\cdots=\sgn(\begin{pmatrix}n-1&n\end{pmatrix})</math>
구체적으로, <math>\sigma</math>의 부호 <math>\sgn(\sigma)</math>는 다음의 두 값과 같다.
:<math>\sgn(\sigma)=(-1)^{\operatorname{inv\,num}(\sigma)}=(-1)^{\operatorname{dec}(\sigma)}</math>

=== 홀짝성 ===
반전수·감소량·부호를 통해 유한 집합의 순열의 '''홀짝성'''(-性, {{llang|en|parity}})을 정의할 수 있다. 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음 세 조건이 서로 [[동치]]이며, 이를 만족시키는 <math>\sigma</math>를 '''홀순열'''(-順列, {{llang|en|odd permutation}})이라고 한다.
* <math>\operatorname{inv\,num}(\sigma)</math>는 [[홀수]]이다.
* <math>\operatorname{dec}(\sigma)</math>는 홀수이다.
* <math>\sgn(\sigma)=-1</math>
홀순열이 아닌 순열을 '''짝순열'''(-順列, {{llang|en|even permutation}})이라고 한다. 즉, 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음 세 조건이 서로 [[동치]]이며, 이를 만족시키는 <math>\sigma</math>를 '''짝순열'''이라고 한다.
* <math>\operatorname{inv\,num}(\sigma)</math>는 [[짝수]]이다.
* <math>\operatorname{dec}(\sigma)</math>는 짝수이다.
* <math>\sgn(\sigma)=1</math>

== 순열의 수 ==
유한 집합 <math>\{1,2,\dotsc,n\}</math>의 모든 순열의 수는 <math>n</math>의 [[계승 (수학)|계승]] <math>n!</math>이다. 이들 가운데 홀순열의 수는 다음과 같다.
:<math>\begin{cases}0&n=0,1\\n!/2&n\ge 2\end{cases}</math>
또한, 짝순열의 수는 다음과 같다.
:<math>\begin{cases}1&n=0,1\\n!/2&n\ge 2\end{cases}</math>
순열이 [[고정점]]을 갖지 않는다면, 이 순열을 '''[[완전 순열]]'''이라고 한다. 유한 집합 <math>\{1,2,\dotsc,n\}</math>의 완전 순열의 수는 [[준계승]] <math>!n</math>으로 주어진다.

유한 집합 <math>\{1,2,\dotsc,n\}</math>의 순열의 항이 번갈아 가면서 커졌다 작아졌다 (또는 작아졌다 커졌다) 하면, 이 순열을 '''[[교대 순열]]'''(交代順列, {{llang|en|alternating permutation}})이라고 한다. 교대 순열의 수 <math>A_n</math>은 점화식을 통해 주어진다.

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

=== ''k''-순열 ===
음이 아닌 정수 <math>k</math>가 주어졌을 때, 집합 <math>X</math>의 '''<math>k</math>-순열'''(-順列, {{llang|en|<math>k</math>-permutation}})은 [[단사 함수]] <math>\{1,2,\dotsc,k\}\to X</math>이다. 특히, 유한 집합 <math>X=\{1,2,\dotsc,n\}</math>의 경우 이를 '''<math>n</math>의 <math>k</math>-순열'''이라고 한다. 이 경우, 원래의 유한 순열은 <math>n</math>의 <math>n</math>-순열이다. 풀어 말해, <math>n</math>의 <math>k</math>-순열은 서로 다른 <math>n</math>개의 원소 가운데 중복 없이 <math>k</math>개를 골라서 순서 있게 나열한 것이다. <math>n</math>의 <math>k</math>-순열의 수는 <math>n^{\underline k},{}_nP_k,P_{n,k},P(n,k)</math>와 같이 표기하며, 다음과 같이 [[하강 계승]]으로 주어진다.
:<math>n^{\underline k}=n(n-1)(n-2)\cdots(n-k+1)</math>
예를 들어, 6곡의 노래 가운데 3곡을 골라 재생 목록을 만드는 방법의 수는 다음과 같다.
:<math>6^{\underline 3}=6\times 5\times 4=120</math>
<math>n</math>의 <math>k</math>-순열의 수와 <math>n</math>의 <math>k</math>-[[조합]]의 수([[이항 계수]])의 관계는 다음과 같다.
:<math>\binom nk=\frac{n^{\underline k}}{k!}</math>

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

=== 중복집합 순열 ===
[[파일:Permutations with repetition.svg|대체글=중복집합을 우선 집합으로 여겨 순열을 취한 뒤, 다시 중복집합으로 여겨 겹치는 순열들을 제외하는 방법으로 중복집합 순열의 수를 계산한 것|섬네일|집합의 순열과 달리, 중복집합 순열에서는 같은 색깔의 원소들을 구별이 불가능하다고 여기며, 이에 따라 순열의 수가 줄어들게 된다.]]
크기 <math>n</math>의 [[중복집합]] <math>n_1\{1\}+n_2\{2\}+\cdots+n_k\{k\}</math>의 '''중복집합 순열'''(重複集合順列, {{llang|en|multiset permutation}}) 또는 '''같은 것이 있는 순열'''(-順列)은 다음 조건을 만족시키는 [[함수]] <math>\sigma\colon\{1,2,\dotsc,n\}\to\{1,2,\dotsc,k\}</math>이다.
:<math>|\sigma^{-1}(x)|=m(x)\qquad x=1,2,\dotsc,k</math>
풀어 말해, 중복집합 순열은 중복집합의 각 원소를 그 중복도만큼씩 순서 있게 나열한 것이다. 다시 말해, 원래의 순열의 정의에서, 주어진 방식대로 짝지어진 원소들을 같다고 여겨 얻는 개념이다. 그 수는 다음과 같이 [[다항 계수]]로 주어진다.
:<math>\binom n{n_1,n_2,\dotsc,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}</math>
예를 들어, 영어 단어 "MISSISSIPPI"의 [[어구전철]]의 수는 다음과 같다.
:<math>\binom{11}{1,4,4,2}=\frac{11!}{1!\times 4!\times 4!\times 2!}=34650</math>

=== 원순열 ===
유한 집합 <math>\{1,2,\dotsc,n\}</math>의 '''원순열'''(圓順列, {{llang|en|circular permutation}})은 <math>\langle\begin{pmatrix}1&2&\cdots&n\end{pmatrix}\rangle</math>의 <math>\operatorname{Sym}(n)</math> 위의 오른쪽 작용의 궤도를 뜻한다. 이는 <math>\{1,2,\dotsc,n\}</math>의 <math>n</math>-순환(즉, <math>\begin{pmatrix}1&2&\cdots&n\end{pmatrix}</math>의 켤레 원소)과 일대일 대응한다. 풀어 말해, 이는 <math>n</math>개의 원소를 원형 탁자에 둘러앉힌 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 원순열의 수는 다음과 같다.
:<math>\begin{cases}1&n=0\\(n-1)!&n\ge 1\end{cases}</math>
이는 원래의 <math>n!</math>에서 겹치는 배수인 <math>n</math>을 나눈 것이다. 예를 들어, 중심 대칭 시계 속의 1~12를 다시 배열하였을 때 얻을 수 있는 서로 다른 기능의 시계의 수는 <math>11!=39916800</math>이다.

=== 염주 순열 ===
유한 집합 <math>\{1,2,\dotsc,n\}</math>의 '''염주 순열'''(念珠順列) 또는 '''목걸이 순열'''({{llang|en|necklace permutation}})은 <math>\langle\begin{pmatrix}1&2&\cdots&n\end{pmatrix},n+1-\operatorname{id}_n\rangle</math>의 <math>\{1,2,\dotsc,n\}</math> 위의 오른쪽 작용의 궤도를 뜻한다. 풀어 말해, 이는 <math>n</math>개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다.
:<math>\begin{cases}1&n=0,1,2\\(n-1)!/2&n\ge 3\end{cases}</math>
이는 원래의 <math>n!</math>에서 겹치는 배수인 <math>2n</math>을 나눈 것이다. 예를 들어, 팔찌에 7개의 무지개색 구슬을 꿰었을 때 얻을 수 있는 서로 다른 모양의 팔찌의 수는 <math>6!/2=360</math>이다. 처음 몇 염주 순열의 수는 다음과 같다. (<math>n=1,2,\dots</math>)
:1, 1, 1, 3, 12, 60, 360, 2520, ... {{OEIS|A001710}}

== 성질 ==
=== 연산에 대한 닫힘 ===
집합 <math>X</math>의 순열의 집합 <math>\operatorname{Sym}(X)</math>는 [[군 (수학)|군]]을 이룬다. 즉, 다음이 성립한다.
* [[항등 함수]] <math>\operatorname{id}_X\colon x\mapsto x</math>는 <math>X</math>의 순열이다. (이는 군의 [[항등원]]이다.)
* 임의의 <math>X</math>의 순열 <math>\sigma,\tau</math>에 대하여, 그 [[함수의 합성|합성]] <math>\tau\sigma\colon x\mapsto\tau(\sigma(x))</math> 역시 <math>X</math>의 순열이다. (이는 군의 [[이항 연산|곱셈]]이며, [[결합 법칙]]을 만족한다.)
* 임의의 <math>X</math>의 순열 <math>\sigma</math>에 대하여, 그 [[역함수|역]] <math>\sigma^{-1}\colon\sigma(x)\mapsto x</math> 역시 <math>X</math>의 순열이다. (이는 군의 [[역원]] 연산이다.)

=== 반전수 ===
유한 집합의 순열의 반전수·감소량에 대하여, 다음과 같은 부등식이 성립한다.
:<math>0\le\operatorname{inv\,num}(\sigma)\le\binom n2</math>
:<math>0\le\operatorname{dec}(\sigma)\le
\begin{cases}0&n=0\\n-1&n\ge 1\end{cases}</math>
또한, 다음과 같은 점화식이 성립한다.
:<math>\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}</math>
:<math>\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}</math>
또한, 서로 역순열의 반전수·감소량는 서로 같다. 즉, 다음과 같은 항등식이 성립한다.
:<math>\operatorname{inv\,num}(\sigma)=\operatorname{inv\,num}(\sigma^{-1})</math>
:<math>\operatorname{dec}(\sigma)=\operatorname{dec}(\sigma^{-1})</math>

=== 순환 분해 ===
순열 <math>\sigma\in\operatorname{Sym}(X)</math>의 궤도 <math>\langle\sigma\rangle(x)</math> (<math>x\in X</math>)들은 <math>X</math>의 [[집합의 분할|분할]]을 이루며, 각 궤도에서의 제한은 다음과 같이 어떤 순환이다.
:<math>\sigma|_{\langle\sigma\rangle(x)}=
\begin{cases}
\begin{pmatrix}\cdots&\sigma^{-1}(x)&x&\sigma(x)&\cdots\end{pmatrix}
&|\langle\sigma\rangle(x)|\ge\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}</math>
만약 비자명 궤도(=크기가 1이 아닌 궤도)의 개수가 유한하다면, <math>\sigma</math>는 이러한 서로소 비자명 순환들의 곱으로 분해할 수 있다. 서로소 순환들은 항상 가환한데, <math>\sigma</math>의 서로소 비자명 순환 분해는 곱하는 순서를 따지지 않으면 유일하다. 이러한 분해를 <math>\sigma</math>의 '''순환 분해'''(循環分解, {{llang|en|cycle decomposition}})라고 한다. 순환 분해의 길이(=곱해지는 비자명 순환의 개수)는 비자명 궤도의 개수
:<math>|\{\langle\sigma\rangle(x)\colon\sigma(x)\ne x\}|</math>
와 같다. 특히, [[쌍대 유한]] [[고정점]] 집합을 갖는 순열은 항상 서로소 비자명 유한 순환들의 곱으로 유일하게 분해할 수 있다. 특히, 유한 집합의 순열 <math>\sigma\in\operatorname{Sym}(n)</math>의 순환 분해는 구체적으로 다음과 같다.
:<math>\sigma=
\begin{pmatrix}\min\{x\colon\sigma(x)\ne x\}&\cdots\end{pmatrix}
\begin{pmatrix}\min(\{x\colon\sigma(x)\ne x\}\setminus\langle\sigma\rangle(\min\{x\colon\sigma(x)\ne x\}))&\cdots\end{pmatrix}\cdots</math>

=== 호환 분해 ===
유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻는다. 또한, 구체적으로 다음과 같은 분해식들이 성립한다.
:<math>
\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}</math>
:<math>\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}</math>
홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다.

유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음이 성립한다.
:<math>\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\}\}</math>

=== 인접 호환 분해 ===
유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다.
:<math>
\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}</math>
유한 집합의 순열의 인접 호환 분해의 최소 길이는 반전수와 같다. 즉, 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음이 성립한다.
:<math>\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\}\}</math>

=== 군론적 성질 ===
순열 <math>\sigma\in\operatorname{Sym}(X)</math>의 [[위수 (수학)|위수]]는 다음과 같다.
:<math>\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}</math>
특히, 순환의 위수는 그 길이와 같다.

대칭군 <math>\operatorname{Sym}(X)</math>의 [[켤레류]]는 <math>|X|</math>를 양의 기수들의 합으로 나타내는 방법과 자연스럽게 일대일 대응한다. 즉, 순열 <math>\sigma,\tau\in\operatorname{Sym}(X)</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>\sigma,\tau</math>는 서로 켤레이다.
* <math>\sigma,\tau</math>의 궤도의 개수와 각 궤도의 크기는 각각 서로 같다.
대칭군 <math>\operatorname{Sym}(n)</math>의 [[켤레류]]는 <math>n</math>의 [[자연수의 분할|분할]]과 자연스럽게 일대일 대응한다. 즉, 순열 <math>\sigma,\tau\in\operatorname{Sym}(n)</math>에 대하여, 다음 두 조건이 서로 [[동치]]이다.
* <math>\sigma,\tau</math>는 서로 켤레이다.
* <math>\sigma,\tau</math>의 서로소 순환 분해의 길이와 각 순환의 길이는 각각 서로 같다.
유한 집합의 순열의 홀짝성에 대하여, 다음이 성립한다.
* 항등 함수는 짝순열이다.
* 두 홀순열의 합성은 짝순열이며, 두 짝순열의 합성 역시 짝순열이다. 홀순열과 짝순열의 합성은 홀순열이다.
* 홀순열의 역은 홀순열이며, 짝순열의 역은 짝순열이다.
달리 말해, 순열의 부호 함수 <math>\sgn\colon\operatorname{Sym}(n)\to\{-1,1\}</math>는 [[군 준동형]]이다. 즉, 다음이 성립한다.
:<math>\sgn(\operatorname{id}_n)=1</math>
:<math>\sgn(\tau\sigma)=\sgn(\tau)\sgn(\sigma)</math>
:<math>\sgn(\sigma^{-1})=\sgn(\sigma)</math>
이에 따라, 짝순열들은 대칭군의 [[부분군]] <math>\operatorname{Alt}(n)</math>을 이루며, 이를 '''[[교대군]]'''이라고 한다. 사실, 교대군은 이 부호 함수의 [[핵 (수학)|핵]]이므로, 대칭군의 [[정규 부분군]]이다.
:<math>\operatorname{Alt}(n)=\ker\sgn\vartriangleleft\operatorname{Sym}(n)</math>
홀순열의 집합은 부분군이 아니다. 또한, <math>n=0,1</math>의 경우 홀순열이 존재하지 않는다. 그러나, <math>n\ge 2</math>의 경우 홀순열의 집합은 크기가 교대군과 같으며, 교대군의 (자기 자신을 제외하면 유일한) [[잉여류]]이다.

== 예 ==
순열의 합성의 한 가지 예는 다음과 같다.
:<math>
\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}</math>
순열의 역의 한 가지 예는 다음과 같다.
:<math>
\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}</math>
순열의 서로소 순환 분해의 한 가지 예는 다음과 같다.
:<math>
\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}</math>
순열의 홀짝성의 몇 가지 예는 다음과 같다.
* 항등 함수는 짝순열이다.
* 호환은 홀순열이다.
* 짝수 길이의 순환은 홀순열이다.
* 홀수 길이의 순환은 항상 짝순열이다.
크기 3의 대칭군 <math>\operatorname{Sym}(3)</math>의 [[켤레류]]는 다음과 같다.
:<math>
\begin{pmatrix}1&2&3\end{pmatrix}\sim
\begin{pmatrix}1&3&2\end{pmatrix}</math>
:<math>
\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}</math>
:<math>
\begin{pmatrix}1\end{pmatrix}
\begin{pmatrix}2\end{pmatrix}
\begin{pmatrix}3\end{pmatrix}</math>
이들에 대응하는 3의 [[자연수의 분할|분할]]은 각각 다음과 같다.
:<math>3=3</math>
:<math>3=2+1</math>
:<math>3=1+1+1</math>
순열의 반전수의 몇 가지 예는 다음과 같다.
:<math>\operatorname{inv\,num}(\operatorname{id}_n)=0</math>
:<math>\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</math>
:<math>\operatorname{inv\,num}(
\begin{pmatrix}1&2&\cdots&n\\n&n-1&\cdots&1\end{pmatrix})=\binom n2=
\begin{cases}0&n=0,1\\n(n-1)/2&n\ge 2\end{cases}</math>

== 관련 개념 ==
=== 순열 행렬 ===
{{본문|순열 행렬}}
[[파일:Symmetric group 3; Cayley table; matrices.svg|대체글=순열의 합성과 순열 행렬의 곱셈의 관계에 대한 설명|섬네일|순열의 합성은 순열 행렬의 곱셈에 대응한다.]]
유한 집합 <math>\{1,2,\dotsc,n\}</math>의 순열은 <math>n\times n</math> [[순열 행렬]]과 자연스럽게 일대일 대응한다.

== 같이 보기 ==
* [[스테인하우스-존슨-트로터 알고리즘]]

== 외부 링크 ==
* {{eom|title=Permutation of a set}}
** {{eom|title=Permutation}}
** {{eom|title=Signature (permutation)}}
* {{매스월드|id=Permutation|title=Permutation}}
** {{매스월드|id=InversePermutation|title=Inverse permutation}}
** {{매스월드|id=PermutationCycle|title=Permutation cycle}}
** {{매스월드|id=CyclicPermutation|title=Cyclic permutation}}
** {{매스월드|id=Transposition|title=Transposition}}
** {{매스월드|id=PermutationInversion|title=Permutation inversion}}
** {{매스월드|id=InversionVector|title=Inversion vector}}
** {{매스월드|id=EvenPermutation|title=Even permutation}}
** {{매스월드|id=OddPermutation|title=Odd permutation}}
** {{매스월드|id=CircularPermutation|title=Circular permutation}}
* {{nlab|id=permutation|title=Permutation}}
** {{nlab|id=signature of a permutation|title=Signature of a permutation}}
* {{groupprops|제목=Permutation}}
** {{groupprops|제목=Two-line notation for permutations}}
** {{groupprops|제목=One-line notation for permutations}}
** {{groupprops|제목=Cycle decomposition for permutations}}
** {{groupprops|제목=Understanding the cycle decomposition}}
* {{플래닛매스|urlname=Permutation|title=Permutation}}
** {{플래닛매스|urlname=cyclicpermutation|title=Cyclic permutation}}
* {{proofwiki|제목=Definition:Permutation}}
** {{proofwiki|id=Definition:Cycle Decomposition|제목=Definition:Cyclic permutation}}
** {{proofwiki|id=Definition:Cycle Decomposition|제목=Definition:Cycle decomposition}}
** {{proofwiki|제목=Definition:Transposition}}
** {{proofwiki|id=Definition:Sign of Permutation|제목=Definition:Sign of permutation}}
** {{proofwiki|id=Definition:Sign of Permutation on n Letters|제목=Definition:Sign of permutation on n letters}}
** {{proofwiki|id=Definition:Parity (Permutation)|제목=Definition:Parity (permutation)}}
** {{proofwiki|id=Definition:Permutation on Polynomial|제목=Definition:Permutation on polynomial}}
** {{proofwiki|id=Construction of Permutations|제목=Construction of permutations}}
** {{proofwiki|id=Composite of Permutations is Permutation|제목=Composite of permutations is permutation}}
** {{proofwiki|id=Inverse of Permutation is Permutation|제목=Inverse of permutation is permutation}}
** {{proofwiki|id=Existence and Uniqueness of Cycle Decomposition|제목=Existence and uniqueness of cycle decomposition}}
** {{proofwiki|id=Cycle Decomposition of Conjugate|제목=Cycle decomposition of conjugate}}
** {{proofwiki|id=K-Cycle can be Factored into Transpositions|제목=k-cycle can be factored into transpositions}}
** {{proofwiki|id=Parity of K-Cycle|제목=Parity of k-cycle}}
** {{proofwiki|id=Number of Permutations|제목=Number of permutations}}

{{전거 통제}}

[[분류:순열| ]]
[[분류:계승과 이항식 주제| ]]