순열

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

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

수학에서 순열(順列, 틀:문화어, 틀:Llang) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 정의역과 공역이 같은 전단사 함수이다. $n$개의 원소에 대한 순열의 수는 $n$의 계승

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

과 같다.

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

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

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

과 같다.

정의

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

$\sigma =\left(\begin{array}{cccc}1& 2& \cdots & n\\ \sigma (1)& \sigma (2)& \cdots & \sigma (n)\end{array}\right)$

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

순환

양의 정수 $k$가 주어졌을 때, 집합 $X$의 길이 $k$의 순환(-循環, 틀:Llang) $\left(\begin{array}{cccc}{x}_1& x_2& \cdots & x_k\end{array}\right)$은 다음과 같은 꼴의 순열이다. (여기서 $x_i\in X$는 서로 다른 원소이다.)

$x_1\mapsto x_2\mapsto \cdots \mapsto x_k\mapsto x_1$

$x\mapsto x\mathrm{\forall }x\in X\setminus \{x_1,x_2,\dots ,x_k\}$

또한, 길이 ${\mathrm{\aleph }}_0$의 순환(-循環, 틀:Llang) 또는 무한 순환(無限循環, 틀:Llang) $\left(\begin{array}{ccccc}\cdots & x_{-1}& x_0& x_1& \cdots \end{array}\right)$은 다음과 같은 꼴의 순열이다. (여기서 $x_i\in X$는 서로 다른 원소이다.)

$\cdots \mapsto x_{-1}\mapsto x_0\mapsto x_1\mapsto \cdots$

$x\mapsto x\mathrm{\forall }x\in X\setminus \{\dots ,x_{-1},x_0,x_1,\dots \}$

특히, 호환(互換, 틀:Llang) $\left(\begin{array}{cc}x& y\end{array}\right)$은 2-순환 $x\mapsto y\mapsto x$이다. 특히, 유한 집합 $\{1,2,\dots ,n\}$의 인접 호환(隣接互換, 틀:Llang) $\left(\begin{array}{cc}x& x+1\end{array}\right)$은 인접한 두 수에 대한 호환 $x\mapsto x+1\mapsto x$이다.

반전

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

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

또한, $\sigma$의 반전 벡터(反轉-, 틀:Llang) $\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{v}\mathrm{e}\mathrm{c}(\sigma )\in \{0,1,\dots ,n-1{\}}^{n-1}$는 $y$번째 성분이 $y$로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다.

$\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{v}\mathrm{e}\mathrm{c}(\sigma {)}_y=|\{x\in \{1,2,\dots ,n\}:{\sigma }^{-1}(x)<{\sigma }^{-1}(y),x>y\}|y=1,2,\dots ,n-1$

또한, $\sigma$의 반전수(反轉數, 틀:Llang) $\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )$ 또는 $N(\sigma )$는 $\sigma$의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.

궤도

순열 $\sigma \in \mathrm{Sym}(X)$의 순환군 $⟨\sigma ⟩$은 $X$의 왼쪽에서 자연스럽게 작용한다. 즉, $\sigma$가 $x\in X$에 작용한 결과는 $\sigma (x)$이다. 이 작용의 각 궤도 $⟨\sigma ⟩(x)$ ($x\in X$)를 $\sigma$의 궤도(軌道, 틀:Llang)라고 한다.

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

$\mathrm{dec}(\sigma )=n-|\{⟨\sigma ⟩(x):x\in \{1,2,\dots ,n\}\}|=\sum _{⟨\sigma ⟩(x):\sigma (x)\ne x}(|⟨\sigma ⟩(x)|-1)$

부호

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

$-1=\mathrm{sgn}(\left(\begin{array}{cc}1& 2\end{array}\right))=\mathrm{sgn}(\left(\begin{array}{cc}2& 3\end{array}\right))=\cdots =\mathrm{sgn}(\left(\begin{array}{cc}n-1& n\end{array}\right))$

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

$\mathrm{sgn}(\sigma )=(-1{)}^{\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )}=(-1{)}^{\mathrm{dec}(\sigma )}$

홀짝성

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

• $\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )$는 홀수이다.
• $\mathrm{dec}(\sigma )$는 홀수이다.
• $\mathrm{sgn}(\sigma )=-1$

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

• $\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )$는 짝수이다.
• $\mathrm{dec}(\sigma )$는 짝수이다.
• $\mathrm{sgn}(\sigma )=1$

순열의 수

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

$\{\begin{array}{cc}0& n=0,1\\ n!/2& n\ge 2\end{array}$

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

$\{\begin{array}{cc}1& n=0,1\\ n!/2& n\ge 2\end{array}$

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

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

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

k-순열

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

$n^{\underset{\_}{k}}=n(n-1)(n-2)\cdots (n-k+1)$

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

$6^{\underset{\_}{3}}=6\times 5\times 4=120$

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

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n^{\underset{\_}{k}}}{k!}$

중복 순열

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

중복집합 순열

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

크기 $n$의 중복집합 $n_1\{1\}+n_2\{2\}+\cdots +n_k\{k\}$의 중복집합 순열(重複集合順列, 틀:Llang) 또는 같은 것이 있는 순열(-順列)은 다음 조건을 만족시키는 함수 $\sigma :\{1,2,\dots ,n\}\to \{1,2,\dots ,k\}$이다.

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

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

$(\genfrac{}{}{0ex}{}{n}{n_1,n_2,\dots ,n_k})=\frac{n!}{n_1!n_2!\cdots n_k!}$

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

$(\genfrac{}{}{0ex}{}{11}{1,4,4,2})=\frac{11!}{1!\times 4!\times 4!\times 2!}=34650$

원순열

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

$\{\begin{array}{cc}1& n=0\\ (n-1)!& n\ge 1\end{array}$

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

염주 순열

유한 집합 $\{1,2,\dots ,n\}$의 염주 순열(念珠順列) 또는 목걸이 순열(틀:Llang)은 $⟨\left(\begin{array}{cccc}1& 2& \cdots & n\end{array}\right),n+1-{\mathrm{id}}_n⟩$의 $\{1,2,\dots ,n\}$ 위의 오른쪽 작용의 궤도를 뜻한다. 풀어 말해, 이는 $n$개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다.

$\{\begin{array}{cc}1& n=0,1,2\\ (n-1)!/2& n\ge 3\end{array}$

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

1, 1, 1, 3, 12, 60, 360, 2520, ... 틀:OEIS

성질

연산에 대한 닫힘

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

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

반전수

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

$0\le \mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )\le (\genfrac{}{}{0ex}{}{n}{2})$

$0\le \mathrm{dec}(\sigma )\le \{\begin{array}{cc}0& n=0\\ n-1& n\ge 1\end{array}$

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

$\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma \left(\begin{array}{cc}x& x+1\end{array}\right))=\{\begin{array}{cc}\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )+1& \sigma (x)<\sigma (x+1)\\ \mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )-1& \sigma (x)>\sigma (x+1)\end{array}$

$\mathrm{dec}(\left(\begin{array}{cc}x& y\end{array}\right)\sigma )=\{\begin{array}{cc}\mathrm{dec}(\sigma )+1& y\in ̸\{\sigma (x),{\sigma }^2(x),\dots \}\\ \mathrm{dec}(\sigma )-1& y\in \{\sigma (x),{\sigma }^2(x),\dots \}\end{array}$

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

$\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )=\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}({\sigma }^{-1})$

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

순환 분해

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

$\sigma {|}_{⟨\sigma ⟩(x)}=\{\begin{array}{cc}\left(\begin{array}{ccccc}\cdots & {\sigma }^{-1}(x)& x& \sigma (x)& \cdots \end{array}\right)& |⟨\sigma ⟩(x)|\ge {\mathrm{\aleph }}_0\\ \left(\begin{array}{cccc}x& \sigma (x)& \cdots & {\sigma }^{|⟨\sigma ⟩(x)|-1}(x)\end{array}\right)& |⟨\sigma ⟩(x)|<{\mathrm{\aleph }}_0\end{array}$

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

$|\{⟨\sigma ⟩(x):\sigma (x)\ne x\}|$

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

$\sigma =\left(\begin{array}{cc}\min \{x:\sigma (x)\ne x\}& \cdots \end{array}\right)\left(\begin{array}{cc}\min (\{x:\sigma (x)\ne x\}\setminus ⟨\sigma ⟩(\min \{x:\sigma (x)\ne x\}))& \cdots \end{array}\right)\cdots$

호환 분해

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

$\left(\begin{array}{cccccc}{x}_1& x_2& \cdots & x_j& \cdots & x_k\end{array}\right)=\left(\begin{array}{cccc}{x}_1& x_2& \cdots & x_j\end{array}\right)\left(\begin{array}{cccc}{x}_j& x_{j+1}& \cdots & x_k\end{array}\right)=\left(\begin{array}{cc}{x}_1& x_2\end{array}\right)\left(\begin{array}{cc}{x}_2& x_3\end{array}\right)\cdots \left(\begin{array}{cc}{x}_{k-1}& x_k\end{array}\right)$

$\left(\begin{array}{cccc}{x}_1& x_2& \cdots & x_k\end{array}\right)=\left(\begin{array}{cc}{x}_1& x_k\end{array}\right)\left(\begin{array}{cc}{x}_1& x_{k-1}\end{array}\right)\cdots \left(\begin{array}{cc}{x}_1& x_2\end{array}\right)$

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

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

$\mathrm{dec}(\sigma )=\min \{l\in \mathbb{N}:\sigma =\left(\begin{array}{cc}{x}_1& y_1\end{array}\right)\cdots \left(\begin{array}{cc}{x}_l& y_l\end{array}\right),x_i,y_i\in \{1,2,\dots ,n\}\}$

인접 호환 분해

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

$\left(\begin{array}{cc}x& y\end{array}\right)=\left(\begin{array}{cccc}x& x+1& \cdots & y\end{array}\right)\left(\begin{array}{cccc}y-1& y-2& \cdots & x\end{array}\right)=\left(\begin{array}{cc}x& x+1\end{array}\right)\cdots \left(\begin{array}{cc}y-1& y\end{array}\right)\left(\begin{array}{cc}y-1& y-2\end{array}\right)\cdots \left(\begin{array}{cc}x+1& x\end{array}\right)$

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

$\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\sigma )=\min \{l\in \mathbb{N}:\sigma =\left(\begin{array}{cc}{x}_1& x_1+1\end{array}\right)\cdots \left(\begin{array}{cc}{x}_l& x_l+1\end{array}\right),x_i\in \{1,2,\dots ,n-1\}\}$

군론적 성질

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

$\mathrm{ord}(\sigma )=\{\begin{array}{cc}{\mathrm{lcm}}_{x\in X}|⟨\sigma ⟩(x)|& \{|⟨\sigma ⟩(x)|:x\in X\}\in {𝒫}_{<{\mathrm{\aleph }}_0}({\mathbb{Z}}^{+})\\ {\mathrm{\aleph }}_0& \{|⟨\sigma ⟩(x)|:x\in X\}\in ̸{𝒫}_{<{\mathrm{\aleph }}_0}({\mathbb{Z}}^{+})\end{array}$

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

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

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

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

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

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

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

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

$\mathrm{sgn}({\mathrm{id}}_n)=1$

$\mathrm{sgn}(\tau \sigma )=\mathrm{sgn}(\tau )\mathrm{sgn}(\sigma )$

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

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

$\mathrm{Alt}(n)=\ker \mathrm{sgn}⊲\mathrm{Sym}(n)$

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

예

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

$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 2& 1& 5& 4\end{array}\right)\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right)=\left(\begin{array}{ccccc}2& 5& 4& 3& 1\\ 2& 4& 5& 1& 3\end{array}\right)\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right)=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 4& 5& 1& 3\end{array}\right)$

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

${\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 3& 1& 4& 7& 6& 5& 2\end{array}\right)}^{-1}={\left(\begin{array}{ccccccc}2& 7& 1& 3& 6& 5& 4\\ 1& 2& 3& 4& 5& 6& 7\end{array}\right)}^{-1}=\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 2& 7& 1& 3& 6& 5& 4\end{array}\right)$

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

$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 4& 1& 5& 2& 3\end{array}\right)=\left(\begin{array}{ccccc}1& 4& 2& 3& 5\\ 4& 2& 1& 5& 3\end{array}\right)=\left(\begin{array}{ccc}1& 4& 2\end{array}\right)\left(\begin{array}{cc}3& 5\end{array}\right)$

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

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

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

$\left(\begin{array}{ccc}1& 2& 3\end{array}\right)\sim \left(\begin{array}{ccc}1& 3& 2\end{array}\right)$

$\left(\begin{array}{cc}1& 2\end{array}\right)\left(\begin{array}{c}3\end{array}\right)\sim \left(\begin{array}{cc}1& 3\end{array}\right)\left(\begin{array}{c}2\end{array}\right)\sim \left(\begin{array}{cc}2& 3\end{array}\right)\left(\begin{array}{c}1\end{array}\right)$

$\left(\begin{array}{c}1\end{array}\right)\left(\begin{array}{c}2\end{array}\right)\left(\begin{array}{c}3\end{array}\right)$

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

$3=3$

$3=2+1$

$3=1+1+1$

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

$\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}({\mathrm{id}}_n)=0$

$\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\left(\begin{array}{cc}x& y\end{array}\right))=|\{(y,x+1),(y,x+2),\dots ,(y,y-1),(x+1,x),(x+2,x),\dots ,(y-1,x),(y,x)\}|=2|y-x|-1$

$\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{n}\mathrm{u}\mathrm{m}(\left(\begin{array}{cccc}1& 2& \cdots & n\\ n& n-1& \cdots & 1\end{array}\right))=(\genfrac{}{}{0ex}{}{n}{2})=\{\begin{array}{cc}0& n=0,1\\ n(n-1)/2& n\ge 2\end{array}$

관련 개념

순열 행렬

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

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

같이 보기

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

외부 링크

• 틀:Eom
  • 틀:Eom
  • 틀:Eom
• 틀:매스월드
  • 틀:매스월드
  • 틀:매스월드
  • 틀:매스월드
  • 틀:매스월드
  • 틀:매스월드
  • 틀:매스월드
  • 틀:매스월드
  • 틀:매스월드
  • 틀:매스월드
• 틀:Nlab
  • 틀:Nlab
• 틀:Groupprops
  • 틀:Groupprops
  • 틀:Groupprops
  • 틀:Groupprops
  • 틀:Groupprops
• 틀:플래닛매스
  • 틀:플래닛매스
• 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki
  • 틀:Proofwiki