수학 에서 순열 (順列, 문화어 : 차례무이, 영어 : permutation 퍼뮤테이션[* ] ) 또는 치환 (置換)은 순서가 부여된 임의의 집합 을 다른 순서로 뒤섞는 연산이다. 즉, 정의역 과 공역 이 같은 전단사 함수 이다. n {\displaystyle n} 개의 원소에 대한 순열의 수는 n {\displaystyle n} 의 계승
3개의 서로 다른 공에 대한 총 6가지의 순열 루빅스 큐브 의 면에 대한 회전은 그 면의 9개의 부분에 대한 한 가지 순열이다. n ! = n ( n − 1 ) ( n − 2 ) ⋯ ⋅ 2 ⋅ 1 {\displaystyle n!=n(n-1)(n-2)\cdots \cdot 2\cdot 1} 과 같다.
주어진 집합의 순열은 함수의 합성 에 따라 대칭군 이라고 불리는 군 을 이룬다. 이와 같이 주어진 집합의 전부 또는 일부 순열들로 구성된 군(즉, 대칭군의 부분군 )을 순열군 (順列群, 영어 : permutation group )이라고 일컫기도 한다. 예를 들어, 모든 짝순열의 집합은 대칭군의 부분군 이며, 이를 교대군 이라고 한다.
조합론 에서는 더 많은 순열의 개념들이 사용된다. 예컨대 n {\displaystyle n} 개의 원소에서 k {\displaystyle k} 개의 원소를 골라 배열하는 방법들의 가짓수는 하강 계승
P ( n , k ) = n ( n − 1 ) ⋯ ( n − k + 1 ) {\displaystyle P(n,k)=n(n-1)\cdots (n-k+1)} 과 같다.
집합 X {\displaystyle X} 의 순열 은 전단사 함수 X → X {\displaystyle X\to X} 이다. 유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 순열 σ {\displaystyle \sigma } 은 다음과 같이 표를 통해 표기할 수 있다.
σ = ( 1 2 ⋯ n σ ( 1 ) σ ( 2 ) ⋯ σ ( n ) ) {\displaystyle \sigma ={\begin{pmatrix}1&2&\cdots &n\\\sigma (1)&\sigma (2)&\cdots &\sigma (n)\end{pmatrix}}} 모든 X {\displaystyle X} 의 순열은 함수의 합성 에 따라 군 을 이루며, 이를 X {\displaystyle X} 의 대칭군 Sym ( X ) {\displaystyle \operatorname {Sym} (X)} 또는 S X {\displaystyle S_{X}} 이라고 한다. 유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 순열의 대칭군은 Sym ( n ) {\displaystyle \operatorname {Sym} (n)} 또는 S n {\displaystyle S_{n}} 으로 표기한다.
양의 정수 k {\displaystyle k} 가 주어졌을 때, 집합 X {\displaystyle X} 의 길이 k {\displaystyle k} 의 순환 (-循環, 영어 : cycle of length k {\displaystyle k} ) ( x 1 x 2 ⋯ x k ) {\displaystyle {\begin{pmatrix}x_{1}&x_{2}&\cdots &x_{k}\end{pmatrix}}} 은 다음과 같은 꼴의 순열이다. (여기서 x i ∈ X {\displaystyle x_{i}\in X} 는 서로 다른 원소이다.)
x 1 ↦ x 2 ↦ ⋯ ↦ x k ↦ x 1 {\displaystyle x_{1}\mapsto x_{2}\mapsto \cdots \mapsto x_{k}\mapsto x_{1}} x ↦ x ∀ x ∈ X ∖ { x 1 , x 2 , … , x k } {\displaystyle x\mapsto x\qquad \forall x\in X\setminus \{x_{1},x_{2},\dotsc ,x_{k}\}} 또한, 길이 ℵ 0 {\displaystyle \aleph _{0}} 의 순환 (-循環, 영어 : cycle of length ℵ 0 {\displaystyle \aleph _{0}} ) 또는 무한 순환 (無限循環, 영어 : infinite cycle ) ( ⋯ x − 1 x 0 x 1 ⋯ ) {\displaystyle {\begin{pmatrix}\cdots &x_{-1}&x_{0}&x_{1}&\cdots \end{pmatrix}}} 은 다음과 같은 꼴의 순열이다. (여기서 x i ∈ X {\displaystyle x_{i}\in X} 는 서로 다른 원소이다.)
⋯ ↦ x − 1 ↦ x 0 ↦ x 1 ↦ ⋯ {\displaystyle \cdots \mapsto x_{-1}\mapsto x_{0}\mapsto x_{1}\mapsto \cdots } x ↦ x ∀ x ∈ X ∖ { … , x − 1 , x 0 , x 1 , … } {\displaystyle x\mapsto x\qquad \forall x\in X\setminus \{\dots ,x_{-1},x_{0},x_{1},\dots \}} 특히, 호환 (互換, 영어 : transposition ) ( x y ) {\displaystyle {\begin{pmatrix}x&y\end{pmatrix}}} 은 2-순환 x ↦ y ↦ x {\displaystyle x\mapsto y\mapsto x} 이다. 특히, 유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 인접 호환 (隣接互換, 영어 : adjecent transposition ) ( x x + 1 ) {\displaystyle {\begin{pmatrix}x&x+1\end{pmatrix}}} 은 인접한 두 수에 대한 호환 x ↦ x + 1 ↦ x {\displaystyle x\mapsto x+1\mapsto x} 이다.
순열 σ ∈ Sym ( n ) {\displaystyle \sigma \in \operatorname {Sym} (n)} 에 대하여, 튜플 ( x , y ) ∈ { 1 , 2 , … , n } 2 {\displaystyle (x,y)\in \{1,2,\dotsc ,n\}^{2}} 이 다음 두 조건을 만족시키면, σ {\displaystyle \sigma } 의 반전 (反轉 영어 : inversion )이라고 한다.
σ − 1 ( x ) < σ − 1 ( y ) {\displaystyle \sigma ^{-1}(x)<\sigma ^{-1}(y)} x > y {\displaystyle x>y} 또한, σ {\displaystyle \sigma } 의 반전 벡터 (反轉-, 영어 : inversion vector ) i n v v e c ( σ ) ∈ { 0 , 1 , … , n − 1 } n − 1 {\displaystyle \operatorname {inv\,vec} (\sigma )\in \{0,1,\dotsc ,n-1\}^{n-1}} 는 y {\displaystyle y} 번째 성분이 y {\displaystyle y} 로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다.
i n v v e c ( σ ) y = | { x ∈ { 1 , 2 , … , n } : σ − 1 ( x ) < σ − 1 ( y ) , x > y } | y = 1 , 2 , … , n − 1 {\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 ) i n v n u m ( σ ) {\displaystyle \operatorname {inv\,num} (\sigma )} 또는 N ( σ ) {\displaystyle N(\sigma )} 는 σ {\displaystyle \sigma } 의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.
순열 σ ∈ Sym ( X ) {\displaystyle \sigma \in \operatorname {Sym} (X)} 의 순환군 ⟨ σ ⟩ {\displaystyle \langle \sigma \rangle } 은 X {\displaystyle X} 의 왼쪽에서 자연스럽게 작용 한다. 즉, σ {\displaystyle \sigma } 가 x ∈ X {\displaystyle x\in X} 에 작용한 결과는 σ ( x ) {\displaystyle \sigma (x)} 이다. 이 작용의 각 궤도 ⟨ σ ⟩ ( x ) {\displaystyle \langle \sigma \rangle (x)} ( x ∈ X {\displaystyle x\in X} )를 σ {\displaystyle \sigma } 의 궤도 (軌道, 영어 : orbit )라고 한다.
순열 σ ∈ Sym ( n ) {\displaystyle \sigma \in \operatorname {Sym} (n)} 의 감소량 (減少量, 영어 : decrement ) dec ( σ ) {\displaystyle \operatorname {dec} (\sigma )} 는 n {\displaystyle n} 에서 σ {\displaystyle \sigma } 의 궤도 의 개수를 뺀 것이다. 즉, 이는 다음과 같다. (이는 σ {\displaystyle \sigma } 를 몇 차 대칭군의 원소로 여기는지와 무관하다.)
dec ( σ ) = n − | { ⟨ σ ⟩ ( x ) : x ∈ { 1 , 2 , … , n } } | = ∑ ⟨ σ ⟩ ( x ) : σ ( x ) ≠ x ( | ⟨ σ ⟩ ( x ) | − 1 ) {\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 ) sgn : Sym ( n ) → { − 1 , 1 } {\displaystyle \operatorname {sgn} \colon \operatorname {Sym} (n)\to \{-1,1\}} 은 다음 조건을 만족시키는 유일한 군 준동형 이다.
− 1 = sgn ( ( 1 2 ) ) = sgn ( ( 2 3 ) ) = ⋯ = sgn ( ( n − 1 n ) ) {\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 } 의 부호 sgn ( σ ) {\displaystyle \operatorname {sgn}(\sigma )} 는 다음의 두 값과 같다.
sgn ( σ ) = ( − 1 ) i n v n u m ( σ ) = ( − 1 ) dec ( σ ) {\displaystyle \operatorname {sgn}(\sigma )=(-1)^{\operatorname {inv\,num} (\sigma )}=(-1)^{\operatorname {dec} (\sigma )}} 반전수·감소량·부호를 통해 유한 집합의 순열의 홀짝성 (-性, 영어 : parity )을 정의할 수 있다. 순열 σ ∈ Sym ( n ) {\displaystyle \sigma \in \operatorname {Sym} (n)} 에 대하여, 다음 세 조건이 서로 동치 이며, 이를 만족시키는 σ {\displaystyle \sigma } 를 홀순열 (-順列, 영어 : odd permutation )이라고 한다.
i n v n u m ( σ ) {\displaystyle \operatorname {inv\,num} (\sigma )} 는 홀수 이다. dec ( σ ) {\displaystyle \operatorname {dec} (\sigma )} 는 홀수이다. sgn ( σ ) = − 1 {\displaystyle \operatorname {sgn}(\sigma )=-1} 홀순열이 아닌 순열을 짝순열 (-順列, 영어 : even permutation )이라고 한다. 즉, 순열 σ ∈ Sym ( n ) {\displaystyle \sigma \in \operatorname {Sym} (n)} 에 대하여, 다음 세 조건이 서로 동치 이며, 이를 만족시키는 σ {\displaystyle \sigma } 를 짝순열 이라고 한다.
i n v n u m ( σ ) {\displaystyle \operatorname {inv\,num} (\sigma )} 는 짝수 이다. dec ( σ ) {\displaystyle \operatorname {dec} (\sigma )} 는 짝수이다. sgn ( σ ) = 1 {\displaystyle \operatorname {sgn}(\sigma )=1}
유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 모든 순열의 수는 n {\displaystyle n} 의 계승 n ! {\displaystyle n!} 이다. 이들 가운데 홀순열의 수는 다음과 같다.
{ 0 n = 0 , 1 n ! / 2 n ≥ 2 {\displaystyle {\begin{cases}0&n=0,1\\n!/2&n\geq 2\end{cases}}} 또한, 짝순열의 수는 다음과 같다.
{ 1 n = 0 , 1 n ! / 2 n ≥ 2 {\displaystyle {\begin{cases}1&n=0,1\\n!/2&n\geq 2\end{cases}}} 순열이 고정점 을 갖지 않는다면, 이 순열을 완전 순열 이라고 한다. 유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 완전 순열의 수는 준계승 ! n {\displaystyle !n} 으로 주어진다.
유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 순열의 항이 번갈아 가면서 커졌다 작아졌다 (또는 작아졌다 커졌다) 하면, 이 순열을 교대 순열 (交代順列, 영어 : alternating permutation )이라고 한다. 교대 순열의 수 A n {\displaystyle A_{n}} 은 점화식을 통해 주어진다.
조합론 에서는 조금 더 일반화된 순열의 수가 연구되며, 이는 다음과 같다.
음이 아닌 정수 k {\displaystyle k} 가 주어졌을 때, 집합 X {\displaystyle X} 의 k {\displaystyle k} -순열 (-順列, 영어 : k {\displaystyle k} -permutation)은 단사 함수 { 1 , 2 , … , k } → X {\displaystyle \{1,2,\dotsc ,k\}\to X} 이다. 특히, 유한 집합 X = { 1 , 2 , … , n } {\displaystyle X=\{1,2,\dotsc ,n\}} 의 경우 이를 n {\displaystyle n} 의 k {\displaystyle k} -순열 이라고 한다. 이 경우, 원래의 유한 순열은 n {\displaystyle n} 의 n {\displaystyle n} -순열이다. 풀어 말해, n {\displaystyle n} 의 k {\displaystyle k} -순열은 서로 다른 n {\displaystyle n} 개의 원소 가운데 중복 없이 k {\displaystyle k} 개를 골라서 순서 있게 나열한 것이다. n {\displaystyle n} 의 k {\displaystyle k} -순열의 수는 n k _ , n P k , P n , k , P ( n , k ) {\displaystyle n^{\underline {k}},{}_{n}P_{k},P_{n,k},P(n,k)} 와 같이 표기하며, 다음과 같이 하강 계승 으로 주어진다.
n k _ = n ( n − 1 ) ( n − 2 ) ⋯ ( n − k + 1 ) {\displaystyle n^{\underline {k}}=n(n-1)(n-2)\cdots (n-k+1)} 예를 들어, 6곡의 노래 가운데 3곡을 골라 재생 목록을 만드는 방법의 수는 다음과 같다.
6 3 _ = 6 × 5 × 4 = 120 {\displaystyle 6^{\underline {3}}=6\times 5\times 4=120} n {\displaystyle n} 의 k {\displaystyle k} -순열의 수와 n {\displaystyle n} 의 k {\displaystyle k} -조합 의 수(이항 계수 )의 관계는 다음과 같다.
( n k ) = n k _ k ! {\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}} 음이 아닌 정수 k {\displaystyle k} 가 주어졌을 때, 집합 X {\displaystyle X} 의 k {\displaystyle k} -중복 순열 (重複順列, 영어 : k {\displaystyle k} -permutation with repetition)은 X {\displaystyle X} 의 k {\displaystyle k} -튜플 을 뜻한다. 특히, 유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 k {\displaystyle k} -튜플을 생각할 수 있으며, 이는 풀어 말해 n {\displaystyle n} 개의 원소 가운데 중복이 가능한 k {\displaystyle k} 개를 골라서 순서 있게 나열한 것이다. 그 수는 n k {\displaystyle n^{k}} 이다. 예를 들어, 26개의 알파벳으로 구성된 3글자 단어의 수는 26 3 = 17576 {\displaystyle 26^{3}=17576} 이다.
집합의 순열과 달리, 중복집합 순열에서는 같은 색깔의 원소들을 구별이 불가능하다고 여기며, 이에 따라 순열의 수가 줄어들게 된다. 크기 n {\displaystyle n} 의 중복집합 n 1 { 1 } + n 2 { 2 } + ⋯ + n k { k } {\displaystyle n_{1}\{1\}+n_{2}\{2\}+\cdots +n_{k}\{k\}} 의 중복집합 순열 (重複集合順列, 영어 : multiset permutation ) 또는 같은 것이 있는 순열 (-順列)은 다음 조건을 만족시키는 함수 σ : { 1 , 2 , … , n } → { 1 , 2 , … , k } {\displaystyle \sigma \colon \{1,2,\dotsc ,n\}\to \{1,2,\dotsc ,k\}} 이다.
| σ − 1 ( x ) | = m ( x ) x = 1 , 2 , … , k {\displaystyle |\sigma ^{-1}(x)|=m(x)\qquad x=1,2,\dotsc ,k} 풀어 말해, 중복집합 순열은 중복집합의 각 원소를 그 중복도만큼씩 순서 있게 나열한 것이다. 다시 말해, 원래의 순열의 정의에서, 주어진 방식대로 짝지어진 원소들을 같다고 여겨 얻는 개념이다. 그 수는 다음과 같이 다항 계수 로 주어진다.
( n n 1 , n 2 , … , n k ) = n ! n 1 ! n 2 ! ⋯ n k ! {\displaystyle {\binom {n}{n_{1},n_{2},\dotsc ,n_{k}}}={\frac {n!}{n_{1}!n_{2}!\cdots n_{k}!}}} 예를 들어, 영어 단어 "MISSISSIPPI"의 어구전철 의 수는 다음과 같다.
( 11 1 , 4 , 4 , 2 ) = 11 ! 1 ! × 4 ! × 4 ! × 2 ! = 34650 {\displaystyle {\binom {11}{1,4,4,2}}={\frac {11!}{1!\times 4!\times 4!\times 2!}}=34650} 유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 원순열 (圓順列, 영어 : circular permutation )은 ⟨ ( 1 2 ⋯ n ) ⟩ {\displaystyle \langle {\begin{pmatrix}1&2&\cdots &n\end{pmatrix}}\rangle } 의 Sym ( n ) {\displaystyle \operatorname {Sym} (n)} 위의 오른쪽 작용의 궤도를 뜻한다. 이는 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 n {\displaystyle n} -순환(즉, ( 1 2 ⋯ n ) {\displaystyle {\begin{pmatrix}1&2&\cdots &n\end{pmatrix}}} 의 켤레 원소)과 일대일 대응한다. 풀어 말해, 이는 n {\displaystyle n} 개의 원소를 원형 탁자에 둘러앉힌 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 원순열의 수는 다음과 같다.
{ 1 n = 0 ( n − 1 ) ! n ≥ 1 {\displaystyle {\begin{cases}1&n=0\\(n-1)!&n\geq 1\end{cases}}} 이는 원래의 n ! {\displaystyle n!} 에서 겹치는 배수인 n {\displaystyle n} 을 나눈 것이다. 예를 들어, 중심 대칭 시계 속의 1~12를 다시 배열하였을 때 얻을 수 있는 서로 다른 기능의 시계의 수는 11 ! = 39916800 {\displaystyle 11!=39916800} 이다.
유한 집합 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 의 염주 순열 (念珠順列) 또는 목걸이 순열 (영어 : necklace permutation )은 ⟨ ( 1 2 ⋯ n ) , n + 1 − id n ⟩ {\displaystyle \langle {\begin{pmatrix}1&2&\cdots &n\end{pmatrix}},n+1-\operatorname {id} _{n}\rangle } 의 { 1 , 2 , … , n } {\displaystyle \{1,2,\dotsc ,n\}} 위의 오른쪽 작용의 궤도를 뜻한다. 풀어 말해, 이는 n {\displaystyle n} 개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다.
{ 1 n = 0 , 1 , 2 ( n − 1 ) ! / 2 n ≥ 3 {\displaystyle {\begin{cases}1&n=0,1,2\\(n-1)!/2&n\geq 3\end{cases}}} 이는 원래의 n ! {\displaystyle n!} 에서 겹치는 배수인 2 n {\displaystyle 2n} 을 나눈 것이다. 예를 들어, 팔찌에 7개의 무지개색 구슬을 꿰었을 때 얻을 수 있는 서로 다른 모양의 팔찌의 수는 6 ! / 2 = 360 {\displaystyle 6!/2=360} 이다. 처음 몇 염주 순열의 수는 다음과 같다. ( n = 1 , 2 , … {\displaystyle n=1,2,\dots } )
1, 1, 1, 3, 12, 60, 360, 2520, ... (OEIS 의 수열 A001710 )
집합 X {\displaystyle X} 의 순열의 집합 Sym ( X ) {\displaystyle \operatorname {Sym} (X)} 는 군 을 이룬다. 즉, 다음이 성립한다.
항등 함수 id X : x ↦ x {\displaystyle \operatorname {id} _{X}\colon x\mapsto x} 는 X {\displaystyle X} 의 순열이다. (이는 군의 항등원 이다.)임의의 X {\displaystyle X} 의 순열 σ , τ {\displaystyle \sigma ,\tau } 에 대하여, 그 합성 τ σ : x ↦ τ ( σ ( x ) ) {\displaystyle \tau \sigma \colon x\mapsto \tau (\sigma (x))} 역시 X {\displaystyle X} 의 순열이다. (이는 군의 곱셈 이며, 결합 법칙 을 만족한다.) 임의의 X {\displaystyle X} 의 순열 σ {\displaystyle \sigma } 에 대하여, 그 역 σ − 1 : σ ( x ) ↦ x {\displaystyle \sigma ^{-1}\colon \sigma (x)\mapsto x} 역시 X {\displaystyle X} 의 순열이다. (이는 군의 역원 연산이다.) 유한 집합의 순열의 반전수·감소량에 대하여, 다음과 같은 부등식이 성립한다.
0 ≤ i n v n u m ( σ ) ≤ ( n 2 ) {\displaystyle 0\leq \operatorname {inv\,num} (\sigma )\leq {\binom {n}{2}}} 0 ≤ dec ( σ ) ≤ { 0 n = 0 n − 1 n ≥ 1 {\displaystyle 0\leq \operatorname {dec} (\sigma )\leq {\begin{cases}0&n=0\\n-1&n\geq 1\end{cases}}} 또한, 다음과 같은 점화식이 성립한다.
i n v n u m ( σ ( x x + 1 ) ) = { i n v n u m ( σ ) + 1 σ ( x ) < σ ( x + 1 ) i n v n u m ( σ ) − 1 σ ( x ) > σ ( x + 1 ) {\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}}} dec ( ( x y ) σ ) = { dec ( σ ) + 1 y ∉ { σ ( x ) , σ 2 ( x ) , … } dec ( σ ) − 1 y ∈ { σ ( x ) , σ 2 ( x ) , … } {\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}}} 또한, 서로 역순열의 반전수·감소량는 서로 같다. 즉, 다음과 같은 항등식이 성립한다.
i n v n u m ( σ ) = i n v n u m ( σ − 1 ) {\displaystyle \operatorname {inv\,num} (\sigma )=\operatorname {inv\,num} (\sigma ^{-1})} dec ( σ ) = dec ( σ − 1 ) {\displaystyle \operatorname {dec} (\sigma )=\operatorname {dec} (\sigma ^{-1})} 순열 σ ∈ Sym ( X ) {\displaystyle \sigma \in \operatorname {Sym} (X)} 의 궤도 ⟨ σ ⟩ ( x ) {\displaystyle \langle \sigma \rangle (x)} ( x ∈ X {\displaystyle x\in X} )들은 X {\displaystyle X} 의 분할 을 이루며, 각 궤도에서의 제한은 다음과 같이 어떤 순환이다.
σ | ⟨ σ ⟩ ( x ) = { ( ⋯ σ − 1 ( x ) x σ ( x ) ⋯ ) | ⟨ σ ⟩ ( x ) | ≥ ℵ 0 ( x σ ( x ) ⋯ σ | ⟨ σ ⟩ ( x ) | − 1 ( x ) ) | ⟨ σ ⟩ ( x ) | < ℵ 0 {\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 )라고 한다. 순환 분해의 길이(=곱해지는 비자명 순환의 개수)는 비자명 궤도의 개수
| { ⟨ σ ⟩ ( x ) : σ ( x ) ≠ x } | {\displaystyle |\{\langle \sigma \rangle (x)\colon \sigma (x)\neq x\}|} 와 같다. 특히, 쌍대 유한 고정점 집합을 갖는 순열은 항상 서로소 비자명 유한 순환들의 곱으로 유일하게 분해할 수 있다. 특히, 유한 집합의 순열 σ ∈ Sym ( n ) {\displaystyle \sigma \in \operatorname {Sym} (n)} 의 순환 분해는 구체적으로 다음과 같다.
σ = ( min { x : σ ( x ) ≠ x } ⋯ ) ( min ( { x : σ ( x ) ≠ x } ∖ ⟨ σ ⟩ ( min { x : σ ( x ) ≠ x } ) ) ⋯ ) ⋯ {\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 } 유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻는다. 또한, 구체적으로 다음과 같은 분해식들이 성립한다.
( x 1 x 2 ⋯ x j ⋯ x k ) = ( x 1 x 2 ⋯ x j ) ( x j x j + 1 ⋯ x k ) = ( x 1 x 2 ) ( x 2 x 3 ) ⋯ ( x k − 1 x k ) {\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}}} ( x 1 x 2 ⋯ x k ) = ( x 1 x k ) ( x 1 x k − 1 ) ⋯ ( x 1 x 2 ) {\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}}} 홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다.
유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 σ ∈ Sym ( n ) {\displaystyle \sigma \in \operatorname {Sym} (n)} 에 대하여, 다음이 성립한다.
dec ( σ ) = min { l ∈ N : σ = ( x 1 y 1 ) ⋯ ( x l y l ) , x i , y i ∈ { 1 , 2 , … , 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\}\}} 유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다.
( x y ) = ( x x + 1 ⋯ y ) ( y − 1 y − 2 ⋯ x ) = ( x x + 1 ) ⋯ ( y − 1 y ) ( y − 1 y − 2 ) ⋯ ( x + 1 x ) {\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}}} 유한 집합의 순열의 인접 호환 분해의 최소 길이는 반전수와 같다. 즉, 순열 σ ∈ Sym ( n ) {\displaystyle \sigma \in \operatorname {Sym} (n)} 에 대하여, 다음이 성립한다.
i n v n u m ( σ ) = min { l ∈ N : σ = ( x 1 x 1 + 1 ) ⋯ ( x l x l + 1 ) , x i ∈ { 1 , 2 , … , n − 1 } } {\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\}\}} 순열 σ ∈ Sym ( X ) {\displaystyle \sigma \in \operatorname {Sym} (X)} 의 위수 는 다음과 같다.
ord ( σ ) = { lcm x ∈ X | ⟨ σ ⟩ ( x ) | { | ⟨ σ ⟩ ( x ) | : x ∈ X } ∈ P < ℵ 0 ( Z + ) ℵ 0 { | ⟨ σ ⟩ ( x ) | : x ∈ X } ∉ P < ℵ 0 ( Z + ) {\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}}} 특히, 순환의 위수는 그 길이와 같다.
대칭군 Sym ( X ) {\displaystyle \operatorname {Sym} (X)} 의 켤레류 는 | X | {\displaystyle |X|} 를 양의 기수들의 합으로 나타내는 방법과 자연스럽게 일대일 대응한다. 즉, 순열 σ , τ ∈ Sym ( X ) {\displaystyle \sigma ,\tau \in \operatorname {Sym} (X)} 에 대하여, 다음 두 조건이 서로 동치 이다.
σ , τ {\displaystyle \sigma ,\tau } 는 서로 켤레이다. σ , τ {\displaystyle \sigma ,\tau } 의 궤도의 개수와 각 궤도의 크기는 각각 서로 같다.대칭군 Sym ( n ) {\displaystyle \operatorname {Sym} (n)} 의 켤레류 는 n {\displaystyle n} 의 분할 과 자연스럽게 일대일 대응한다. 즉, 순열 σ , τ ∈ Sym ( n ) {\displaystyle \sigma ,\tau \in \operatorname {Sym} (n)} 에 대하여, 다음 두 조건이 서로 동치 이다.
σ , τ {\displaystyle \sigma ,\tau } 는 서로 켤레이다. σ , τ {\displaystyle \sigma ,\tau } 의 서로소 순환 분해의 길이와 각 순환의 길이는 각각 서로 같다.유한 집합의 순열의 홀짝성에 대하여, 다음이 성립한다.
항등 함수는 짝순열이다. 두 홀순열의 합성은 짝순열이며, 두 짝순열의 합성 역시 짝순열이다. 홀순열과 짝순열의 합성은 홀순열이다. 홀순열의 역은 홀순열이며, 짝순열의 역은 짝순열이다. 달리 말해, 순열의 부호 함수 sgn : Sym ( n ) → { − 1 , 1 } {\displaystyle \operatorname {sgn} \colon \operatorname {Sym} (n)\to \{-1,1\}} 는 군 준동형 이다. 즉, 다음이 성립한다.
sgn ( id n ) = 1 {\displaystyle \operatorname {sgn}(\operatorname {id} _{n})=1} sgn ( τ σ ) = sgn ( τ ) sgn ( σ ) {\displaystyle \operatorname {sgn}(\tau \sigma )=\operatorname {sgn}(\tau )\operatorname {sgn}(\sigma )} sgn ( σ − 1 ) = sgn ( σ ) {\displaystyle \operatorname {sgn}(\sigma ^{-1})=\operatorname {sgn}(\sigma )} 이에 따라, 짝순열들은 대칭군의 부분군 Alt ( n ) {\displaystyle \operatorname {Alt} (n)} 을 이루며, 이를 교대군 이라고 한다. 사실, 교대군은 이 부호 함수의 핵 이므로, 대칭군의 정규 부분군 이다.
Alt ( n ) = ker sgn ⊲ Sym ( n ) {\displaystyle \operatorname {Alt} (n)=\ker \operatorname {sgn} \vartriangleleft \operatorname {Sym} (n)} 홀순열의 집합은 부분군이 아니다. 또한, n = 0 , 1 {\displaystyle n=0,1} 의 경우 홀순열이 존재하지 않는다. 그러나, n ≥ 2 {\displaystyle n\geq 2} 의 경우 홀순열의 집합은 크기가 교대군과 같으며, 교대군의 (자기 자신을 제외하면 유일한) 잉여류 이다.
순열의 합성의 한 가지 예는 다음과 같다.
( 1 2 3 4 5 3 2 1 5 4 ) ( 1 2 3 4 5 2 5 4 3 1 ) = ( 2 5 4 3 1 2 4 5 1 3 ) ( 1 2 3 4 5 2 5 4 3 1 ) = ( 1 2 3 4 5 2 4 5 1 3 ) {\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}}} 순열의 역의 한 가지 예는 다음과 같다.
( 1 2 3 4 5 6 7 3 1 4 7 6 5 2 ) − 1 = ( 2 7 1 3 6 5 4 1 2 3 4 5 6 7 ) − 1 = ( 1 2 3 4 5 6 7 2 7 1 3 6 5 4 ) {\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}}} 순열의 서로소 순환 분해의 한 가지 예는 다음과 같다.
( 1 2 3 4 5 4 1 5 2 3 ) = ( 1 4 2 3 5 4 2 1 5 3 ) = ( 1 4 2 ) ( 3 5 ) {\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의 대칭군 Sym ( 3 ) {\displaystyle \operatorname {Sym} (3)} 의 켤레류 는 다음과 같다.
( 1 2 3 ) ∼ ( 1 3 2 ) {\displaystyle {\begin{pmatrix}1&2&3\end{pmatrix}}\sim {\begin{pmatrix}1&3&2\end{pmatrix}}} ( 1 2 ) ( 3 ) ∼ ( 1 3 ) ( 2 ) ∼ ( 2 3 ) ( 1 ) {\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}}} ( 1 ) ( 2 ) ( 3 ) {\displaystyle {\begin{pmatrix}1\end{pmatrix}}{\begin{pmatrix}2\end{pmatrix}}{\begin{pmatrix}3\end{pmatrix}}} 이들에 대응하는 3의 분할 은 각각 다음과 같다.
3 = 3 {\displaystyle 3=3} 3 = 2 + 1 {\displaystyle 3=2+1} 3 = 1 + 1 + 1 {\displaystyle 3=1+1+1} 순열의 반전수의 몇 가지 예는 다음과 같다.
i n v n u m ( id n ) = 0 {\displaystyle \operatorname {inv\,num} (\operatorname {id} _{n})=0} i n v n u m ( ( x y ) ) = | { ( y , x + 1 ) , ( y , x + 2 ) , … , ( y , y − 1 ) , ( x + 1 , x ) , ( x + 2 , x ) , … , ( y − 1 , x ) , ( y , x ) } | = 2 | y − x | − 1 {\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} i n v n u m ( ( 1 2 ⋯ n n n − 1 ⋯ 1 ) ) = ( n 2 ) = { 0 n = 0 , 1 n ( n − 1 ) / 2 n ≥ 2 {\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}}}