순열

다른 뜻 3개의 서로 다른 공에 대한 총 6가지의 순열 루빅스 큐브의 면에 대한 회전은 그 면의 9개의 부분에 대한 한 가지 순열이다. 수학에서 **순열**(順列, 차례무이, 퍼뮤테이션) 또는 **치환**(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 정의역과 공역이 같은 전단사 함수이다. n개의 원소에 대한 순열의 수는 n의 계승 :n!=n(n-1)(n-2)\cdots\cdot 2\cdot 1 과 같다. 주어진 집합의 순열은 함수의 합성에 따라 대칭군이라고 불리는 군을 이룬다. 이와 같이 주어진 집합의 전부 또는 일부 순열들로 구성된 군(즉, 대칭군의 부분군)을 **순열군**(順列群, permutation group)이라고 일컫기도 한다. 예를 들어, 모든 짝순열의 집합은 대칭군의 부분군이며, 이를 교대군이라고 한다. 조합론에서는 더 많은 순열의 개념들이 사용된다. 예컨대 n개의 원소에서 k개의 원소를 골라 배열하는 방법들의 가짓수는 하강 계승 :P(n,k)=n(n-1)\cdots(n-k+1) 과 같다.
# 정의
집합 X의 **순열**은 전단사 함수 X\to X이다. 유한 집합 \\{1,2,\dotsc,n\\}의 순열 \sigma은 다음과 같이 표를 통해 표기할 수 있다. :\sigma=\begin{pmatrix}1&2&\cdots&n;\\\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix} 모든 X의 순열은 함수의 합성에 따라 군을 이루며, 이를 X의 **대칭군** \operatorname{Sym}(X) 또는 S_X이라고 한다. 유한 집합 \\{1,2,\dotsc,n\\}의 순열의 대칭군은 \operatorname{Sym}(n) 또는 S_n으로 표기한다.
## 순환
양의 정수 k가 주어졌을 때, 집합 X의 **길이 k의 순환**(-循環, cycle of length k) \begin{pmatrix}x_1&x;_2&\cdots&x;_k\end{pmatrix}은 다음과 같은 꼴의 순열이다. (여기서 x_i\in X는 서로 다른 원소이다.) :x_1\mapsto x_2\mapsto\cdots\mapsto x_k\mapsto x_1 :x\mapsto x\qquad\forall x\in X\setminus\\{x_1,x_2,\dotsc,x_k\\} 또한, **길이 \aleph_0의 순환**(-循環, cycle of length \aleph_0) 또는 **무한 순환**(無限循環, infinite cycle) \begin{pmatrix}\cdots&x;_{-1}&x;_0&x;_1&\cdots\end{pmatrix}은 다음과 같은 꼴의 순열이다. (여기서 x_i\in X는 서로 다른 원소이다.) :\cdots\mapsto x_{-1}\mapsto x_0\mapsto x_1\mapsto\cdots :x\mapsto x\qquad\forall x\in X\setminus\\{\dots,x_{-1},x_0,x_1,\dots\\} 특히, **호환**(互換, transposition) \begin{pmatrix}x&y;\end{pmatrix}은 2-순환 x\mapsto y\mapsto x이다. 특히, 유한 집합 \\{1,2,\dotsc,n\\}의 **인접 호환**(隣接互換, adjecent transposition) \begin{pmatrix}x&x;+1\end{pmatrix}은 인접한 두 수에 대한 호환 x\mapsto x+1\mapsto x이다.
## 반전
순열 \sigma\in\operatorname{Sym}(n)에 대하여, 튜플 (x,y)\in\\{1,2,\dotsc,n\\}^2이 다음 두 조건을 만족시키면, \sigma의 **반전**(反轉 inversion)이라고 한다. * \sigma^{-1}(x)y 또한, \sigma의 **반전 벡터**(反轉-, inversion vector) \operatorname{inv\,vec}(\sigma)\in\\{0,1,\dotsc,n-1\\}^{n-1}는 y번째 성분이 y로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다. :\operatorname{inv\,vec}(\sigma)_y=|\\{x\in\\{1,2,\dotsc,n\\}\colon\sigma^{-1}(x)y\\}|\qquad y=1,2,\dotsc,n-1 또한, \sigma의 **반전수**(反轉數, inversion number) \operatorname{inv\,num}(\sigma) 또는 N(\sigma)는 \sigma의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.
## 궤도
순열 \sigma\in\operatorname{Sym}(X)의 순환군 \langle\sigma\rangle은 X의 왼쪽에서 자연스럽게 작용한다. 즉, \sigma가 x\in X에 작용한 결과는 \sigma(x)이다. 이 작용의 각 궤도 \langle\sigma\rangle(x) (x\in X)를 \sigma의 **궤도**(軌道, orbit)라고 한다. 순열 \sigma\in\operatorname{Sym}(n)의 **감소량**(減少量, decrement) \operatorname{dec}(\sigma)는 n에서 \sigma의 궤도의 개수를 뺀 것이다. 즉, 이는 다음과 같다. (이는 \sigma를 몇 차 대칭군의 원소로 여기는지와 무관하다.) :\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)
## 부호
순열의 **부호**(符號, sign) \sgn\colon\operatorname{Sym}(n)\to\\{-1,1\\}은 다음 조건을 만족시키는 유일한 군 준동형이다. :-1=\sgn(\begin{pmatrix}1&2\end{pmatrix})=\sgn(\begin{pmatrix}2&3\end{pmatrix})=\cdots=\sgn(\begin{pmatrix}n-1&n;\end{pmatrix}) 구체적으로, \sigma의 부호 \sgn(\sigma)는 다음의 두 값과 같다. :\sgn(\sigma)=(-1)^{\operatorname{inv\,num}(\sigma)}=(-1)^{\operatorname{dec}(\sigma)}
## 홀짝성
반전수·감소량·부호를 통해 유한 집합의 순열의 **홀짝성**(-性, parity)을 정의할 수 있다. 순열 \sigma\in\operatorname{Sym}(n)에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 \sigma를 **홀순열**(-順列, odd permutation)이라고 한다. * \operatorname{inv\,num}(\sigma)는 홀수이다. * \operatorname{dec}(\sigma)는 홀수이다. * \sgn(\sigma)=-1 홀순열이 아닌 순열을 **짝순열**(-順列, even permutation)이라고 한다. 즉, 순열 \sigma\in\operatorname{Sym}(n)에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 \sigma를 **짝순열**이라고 한다. * \operatorname{inv\,num}(\sigma)는 짝수이다. * \operatorname{dec}(\sigma)는 짝수이다. * \sgn(\sigma)=1
# 순열의 수
유한 집합 \\{1,2,\dotsc,n\\}의 모든 순열의 수는 n의 계승 n!이다. 이들 가운데 홀순열의 수는 다음과 같다. :\begin{cases}0&n;=0,1\\\n!/2&n;\ge 2\end{cases} 또한, 짝순열의 수는 다음과 같다. :\begin{cases}1&n;=0,1\\\n!/2&n;\ge 2\end{cases} 순열이 고정점을 갖지 않는다면, 이 순열을 **완전순열**이라고 한다. 유한 집합 \\{1,2,\dotsc,n\\}의 완전 순열의 수는 준계승 !n으로 주어진다. 유한 집합 \\{1,2,\dotsc,n\\}의 순열의 항이 번갈아 가면서 커졌다 작아졌다 (또는 작아졌다 커졌다) 하면, 이 순열을 **교대 순열**(交代順列, alternating permutation)이라고 한다. 교대 순열의 수 A_n은 점화식을 통해 주어진다. 조합론에서는 조금 더 일반화된 순열의 수가 연구되며, 이는 다음과 같다.
## *k*-순열
음이 아닌 정수 k가 주어졌을 때, 집합 X의 **k-순열**(-順列, k-permutation)은 단사 함수 \\{1,2,\dotsc,k\\}\to X이다. 특히, 유한 집합 X=\\{1,2,\dotsc,n\\}의 경우 이를 **n의 k-순열**이라고 한다. 이 경우, 원래의 유한 순열은 n의 n-순열이다. 풀어 말해, n의 k-순열은 서로 다른 n개의 원소 가운데 중복 없이 k개를 골라서 순서 있게 나열한 것이다. n의 k-순열의 수는 n^{\underline k},{}_nP_k,P_{n,k},P(n,k)와 같이 표기하며, 다음과 같이 하강 계승으로 주어진다. :n^{\underline k}=n(n-1)(n-2)\cdots(n-k+1) 예를 들어, 6곡의 노래 가운데 3곡을 골라 재생 목록을 만드는 방법의 수는 다음과 같다. :6^{\underline 3}=6\times 5\times 4=120 n의 k-순열의 수와 n의 k-조합의 수(이항 계수)의 관계는 다음과 같다. :\binom nk=\frac{n^{\underline k{k!}
## 중복 순열
음이 아닌 정수 k가 주어졌을 때, 집합 X의 k-**중복 순열**(重複順列, k-permutation with repetition)은 X의 k-튜플을 뜻한다. 특히, 유한 집합 \\{1,2,\dotsc,n\\}의 k-튜플을 생각할 수 있으며, 이는 풀어 말해 n개의 원소 가운데 중복이 가능한 k개를 골라서 순서 있게 나열한 것이다. 그 수는 n^k이다. 예를 들어, 26개의 알파벳으로 구성된 3글자 단어의 수는 26^3=17576이다.
## 중복집합 순열
집합의 순열과 달리, 중복집합 순열에서는 같은 색깔의 원소들을 구별이 불가능하다고 여기며, 이에 따라 순열의 수가 줄어들게 된다. 크기 n의 중복집합 n_1\\{1\\}+n_2\\{2\\}+\cdots+n_k\\{k\\}의 **중복집합 순열**(重複集合順列, multiset permutation) 또는 **같은 것이 있는 순열**(-順列)은 다음 조건을 만족시키는 함수 \sigma\colon\\{1,2,\dotsc,n\\}\to\\{1,2,\dotsc,k\\}이다. :|\sigma^{-1}(x)|=m(x)\qquad x=1,2,\dotsc,k 풀어 말해, 중복집합 순열은 중복집합의 각 원소를 그 중복도만큼씩 순서 있게 나열한 것이다. 다시 말해, 원래의 순열의 정의에서, 주어진 방식대로 짝지어진 원소들을 같다고 여겨 얻는 개념이다. 그 수는 다음과 같이 다항 계수로 주어진다. :\binom n{n_1,n_2,\dotsc,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!} 예를 들어, 영어 단어 "MISSISSIPPI"의 어구전철의 수는 다음과 같다. :\binom{11}{1,4,4,2}=\frac{11!}{1!\times 4!\times 4!\times 2!}=34650
## 원순열
유한 집합 \\{1,2,\dotsc,n\\}의 **원순열**(圓順列, circular permutation)은 \langle\begin{pmatrix}1&2&\cdots&n;\end{pmatrix}\rangle의 \operatorname{Sym}(n) 위의 오른쪽 작용의 궤도를 뜻한다. 이는 \\{1,2,\dotsc,n\\}의 n-순환(즉, \begin{pmatrix}1&2&\cdots&n;\end{pmatrix}의 켤레 원소)과 일대일 대응한다. 풀어 말해, 이는 n개의 원소를 원형 탁자에 둘러앉힌 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 원순열의 수는 다음과 같다. :\begin{cases}1&n;=0\\\\(n-1)!&n;\ge 1\end{cases} 이는 원래의 n!에서 겹치는 배수인 n을 나눈 것이다. 예를 들어, 중심 대칭 시계 속의 1~12를 다시 배열하였을 때 얻을 수 있는 서로 다른 기능의 시계의 수는 11!=39916800이다.
## 염주 순열
유한 집합 \\{1,2,\dotsc,n\\}의 **염주 순열**(念珠順列) 또는 **목걸이 순열**(necklace permutation)은 \langle\begin{pmatrix}1&2&\cdots&n;\end{pmatrix},n+1-\operatorname{id}_n\rangle의 \\{1,2,\dotsc,n\\} 위의 오른쪽 작용의 궤도를 뜻한다. 풀어 말해, 이는 n개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다. :\begin{cases}1&n;=0,1,2\\\\(n-1)!/2&n;\ge 3\end{cases} 이는 원래의 n!에서 겹치는 배수인 2n을 나눈 것이다. 예를 들어, 팔찌에 7개의 무지개색 구슬을 꿰었을 때 얻을 수 있는 서로 다른 모양의 팔찌의 수는 6!/2=360이다. 처음 몇 염주 순열의 수는 다음과 같다. (n=1,2,\dots) :1, 1, 1, 3, 12, 60, 360, 2520, ... A001710
# 성질

## 연산에 대한 닫힘
집합 X의 순열의 집합 \operatorname{Sym}(X)는 군을 이룬다. 즉, 다음이 성립한다. * 항등 함수 \operatorname{id}_X\colon x\mapsto x는 X의 순열이다. (이는 군의 항등원이다.) * 임의의 X의 순열 \sigma,\tau에 대하여, 그 합성 \tau\sigma\colon x\mapsto\tau(\sigma(x)) 역시 X의 순열이다. (이는 군의 곱셈이며, 결합 법칙을 만족한다.) * 임의의 X의 순열 \sigma에 대하여, 그 역 \sigma^{-1}\colon\sigma(x)\mapsto x 역시 X의 순열이다. (이는 군의 역원 연산이다.)
## 반전수
유한 집합의 순열의 반전수·감소량에 대하여, 다음과 같은 부등식이 성립한다. :0\le\operatorname{inv\,num}(\sigma)\le\binom n2 :0\le\operatorname{dec}(\sigma)\le \begin{cases}0&n;=0\\\n-1&n;\ge 1\end{cases} 또한, 다음과 같은 점화식이 성립한다. :\operatorname{inv\,num}(\sigma \begin{pmatrix}x&x;+1\end{pmatrix})= \begin{cases} \operatorname{inv\,num}(\sigma)+1&\sigma(x)\sigma(x+1)\end{cases} :\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} 또한, 서로 역순열의 반전수·감소량는 서로 같다. 즉, 다음과 같은 항등식이 성립한다. :\operatorname{inv\,num}(\sigma)=\operatorname{inv\,num}(\sigma^{-1}) :\operatorname{dec}(\sigma)=\operatorname{dec}(\sigma^{-1})
## 순환 분해
순열 \sigma\in\operatorname{Sym}(X)의 궤도 \langle\sigma\rangle(x) (x\in X)들은 X의 분할을 이루며, 각 궤도에서의 제한은 다음과 같이 어떤 순환이다. :\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} 만약 비자명 궤도(=크기가 1이 아닌 궤도)의 개수가 유한하다면, \sigma는 이러한 서로소 비자명 순환들의 곱으로 분해할 수 있다. 서로소 순환들은 항상 가환한데, \sigma의 서로소 비자명 순환 분해는 곱하는 순서를 따지지 않으면 유일하다. 이러한 분해를 \sigma의 **순환 분해**(循環分解, cycle decomposition)라고 한다. 순환 분해의 길이(=곱해지는 비자명 순환의 개수)는 비자명 궤도의 개수 :|\\{\langle\sigma\rangle(x)\colon\sigma(x)\ne x\\}| 와 같다. 특히, 쌍대 유한 고정점 집합을 갖는 순열은 항상 서로소 비자명 유한 순환들의 곱으로 유일하게 분해할 수 있다. 특히, 유한 집합의 순열 \sigma\in\operatorname{Sym}(n)의 순환 분해는 구체적으로 다음과 같다. :\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
## 호환 분해
유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻는다. 또한, 구체적으로 다음과 같은 분해식들이 성립한다. : \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} :\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} 홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다. 유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 \sigma\in\operatorname{Sym}(n)에 대하여, 다음이 성립한다. :\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\\}\\}
## 인접 호환 분해
유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다. : \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} 유한 집합의 순열의 인접 호환 분해의 최소 길이는 반전수와 같다. 즉, 순열 \sigma\in\operatorname{Sym}(n)에 대하여, 다음이 성립한다. :\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\\}\\}
## 군론적 성질
순열 \sigma\in\operatorname{Sym}(X)의 위수는 다음과 같다. :\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} 특히, 순환의 위수는 그 길이와 같다. 대칭군 \operatorname{Sym}(X)의 켤레류는 |X|를 양의 기수들의 합으로 나타내는 방법과 자연스럽게 일대일 대응한다. 즉, 순열 \sigma,\tau\in\operatorname{Sym}(X)에 대하여, 다음 두 조건이 서로 동치이다. * \sigma,\tau는 서로 켤레이다. * \sigma,\tau의 궤도의 개수와 각 궤도의 크기는 각각 서로 같다. 대칭군 \operatorname{Sym}(n)의 켤레류는 n의 분할과 자연스럽게 일대일 대응한다. 즉, 순열 \sigma,\tau\in\operatorname{Sym}(n)에 대하여, 다음 두 조건이 서로 동치이다. * \sigma,\tau는 서로 켤레이다. * \sigma,\tau의 서로소 순환 분해의 길이와 각 순환의 길이는 각각 서로 같다. 유한 집합의 순열의 홀짝성에 대하여, 다음이 성립한다. * 항등 함수는 짝순열이다. * 두 홀순열의 합성은 짝순열이며, 두 짝순열의 합성 역시 짝순열이다. 홀순열과 짝순열의 합성은 홀순열이다. * 홀순열의 역은 홀순열이며, 짝순열의 역은 짝순열이다. 달리 말해, 순열의 부호 함수 \sgn\colon\operatorname{Sym}(n)\to\\{-1,1\\}는 군 준동형이다. 즉, 다음이 성립한다. :\sgn(\operatorname{id}_n)=1 :\sgn(\tau\sigma)=\sgn(\tau)\sgn(\sigma) :\sgn(\sigma^{-1})=\sgn(\sigma) 이에 따라, 짝순열들은 대칭군의 부분군 \operatorname{Alt}(n)을 이루며, 이를 **교대군**이라고 한다. 사실, 교대군은 이 부호 함수의 핵이므로, 대칭군의 정규 부분군이다. :\operatorname{Alt}(n)=\ker\sgn\vartriangleleft\operatorname{Sym}(n) 홀순열의 집합은 부분군이 아니다. 또한, n=0,1의 경우 홀순열이 존재하지 않는다. 그러나, n\ge 2의 경우 홀순열의 집합은 크기가 교대군과 같으며, 교대군의 (자기 자신을 제외하면 유일한) 잉여류이다.
# 예
순열의 합성의 한 가지 예는 다음과 같다. : \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} 순열의 역의 한 가지 예는 다음과 같다. : \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} 순열의 서로소 순환 분해의 한 가지 예는 다음과 같다. : \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의 대칭군 \operatorname{Sym}(3)의 켤레류는 다음과 같다. : \begin{pmatrix}1&2&3\end{pmatrix}\sim \begin{pmatrix}1&3&2\end{pmatrix} : \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} : \begin{pmatrix}1\end{pmatrix} \begin{pmatrix}2\end{pmatrix} \begin{pmatrix}3\end{pmatrix} 이들에 대응하는 3의 분할은 각각 다음과 같다. :3=3 :3=2+1 :3=1+1+1 순열의 반전수의 몇 가지 예는 다음과 같다. :\operatorname{inv\,num}(\operatorname{id}_n)=0 :\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 :\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}
# 관련 개념

## 중복순열
중복순열
## 순열 행렬
순열 행렬 순열의 합성은 순열 행렬의 곱셈에 대응한다. 유한 집합 \\{1,2,\dotsc,n\\}의 순열은 n\times n 순열 행렬과 자연스럽게 일대일 대응한다.