數學 에서 順列 (順列, 文化語 : 次例무이, 英語 : permutation 퍼뮤테이션 ^{[ * ]} ) 또는 置換 (置換)은 順序가 附與된 任意의 集合 을 다른 順序로 뒤섞는 演算이다. 卽, 定義域 과 工役 이 같은 全單射 函數 이다. ${\displaystyle n}$個의 元素에 對한 順列의 數는 ${\displaystyle n}$의 繼承

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

과 같다.

주어진 集合의 順列은 函數의 合成 에 따라 對稱軍 이라고 불리는 軍 을 이룬다. 이와 같이 주어진 集合의 全部 또는 一部 順列들로 構成된 軍(卽, 對稱軍의 部分群 )을 順列群 (順列群, 英語 : 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》 (英語).