置換

定義 3.1 (文字の置換)   $n$ 個の文字 $\{1,2,\cdots,n\}$ から 自分自身 $\{1,2,\cdots,n\}$ への $1$ 対 $1$ の写像を $n$ 文字の置換（permutation）という． $n$ 文字の置換 $\sigma$ が写像

$$1\to k_{1}\,,\quad 2\to k_{2}\,,\quad \cdots n\to k_{n}\,$$ (236)

のとき $\sigma$ を

$$\sigma = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k_{n} \end{pmatrix}$$ (237)

と表わす． 写像 $j\to k_{j}$ を $\sigma(j)=k_{j}$ と表わす．

例 3.1 (置換の具体例)  

例 3.2 (置換の表記)  

定義 3.2 (置換の積)   置換 $\sigma$, $\tau$ の積 $\sigma\tau$ を

$$\sigma\tau = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k... ...matrix}1 & 2 & \cdots & n \\ k_{l_1} & k_{l_2} & \cdots & k_{l_n} \end{pmatrix}$$ (238)

または

$$(\sigma\tau)(i)=\sigma(\tau(i))\,,\quad i=1,2,\cdots,n$$ (239)

と定義する．

例 3.3 (置換の積の具体例)  

注意 3.1 (置換の積は非可換)   一般的に $\sigma\tau=\tau\sigma$ は成立しない．

定義 3.3 (単位置換)   全ての文字を動かさない置換

$$\epsilon = \begin{pmatrix}1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \end{pmatrix}$$ (240)

を単位置換と呼ぶ．

定義 3.4 (逆置換)   置換 $\sigma$ に対して

$$\sigma\tau=\tau\sigma=\epsilon$$ (241)

を満たす置換 $\tau$ を $\sigma$ の逆置換と呼び， $\tau=\sigma^{-1}$ と表わす．

定理 3.1 (逆置換)   置換

$$\sigma = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k_{n} \end{pmatrix}$$ (242)

の逆置換は

$$\sigma^{-1} = \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{n} \\ 1 & 2 & \cdots & n \end{pmatrix}$$ (243)

で与えられる．

例 3.4 (逆置換の具体例)  

定義 3.5 (巡回置換)   $n$ 個の文字 $\{1,2,\cdots,n\}$ のうち $r$ 個の文字 $\{k_{1},k_{2},\cdots,k_{r}\}$ のみを $k_{1}\to k_{2},k_{2}\to k_{3},\cdots,k_{r}\to k_{1}$ と順にずらし， 残りの文字 $\{k_{r+1},\cdots,k_{n}\}$ を $k_{r+1}\to k_{r+1},\cdots,k_{n}\to k_{n}$ と動かさない 写像の置換を巡回置換という． 巡回置換は

$$\sigma = \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{r-1} & k_{r} & k_{r+... ...k_{2} & k_{3} & \cdots & k_{r} & k_{1} & k_{r+1} & \cdots & k_{n} \end{pmatrix}$$ (244)

$$= \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{r-1} & k_{r} \\ k_{2} & k_{3} & \cdots & k_{r} & k_{1} \end{pmatrix}$$ (245)

と表わされ，省略するときは

$$\sigma = (k_{1},k_{2},\cdots,k_{r})$$ (246)

と書く．

例 3.5 (巡回置換の具体例)  

定理 3.2 (置換を巡回置換の積で表わす)   任意の置換 $\sigma$ は巡回置換 $\sigma_{1},\sigma_{2},\cdots,\sigma_{n}$ の積 $\sigma=\sigma_{1}\sigma_{2}\cdots\sigma_{n}$ で表わされる．

例 3.6 (置換を巡回置換の積で表わす計算例)  

定義 3.6 (互換)   $2$ 文字の巡回置換 $(i,j)$ を互換という．

定理 3.3 (巡回置換を互換の積で表わす)   任意の巡回置換は互換の積で表わされる． たとえば，その一つとして

$$(k_1,k_2,\cdots,k_r)= (k_1,k_r)\cdots(k_1,k_3)(k_1,k_2)$$ (247)

と表わされる．

例 3.7 (置換を互換の積で表わす)  

注意 3.2   互換の積で表わす方法は幾通りもある．

定義 3.7 (置換の符号)   置換 $\sigma$ が $m$ 個の互換の積で表わされるとき $\sigma$ の符号（sign）を

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

と定義する．

例 3.8 (置換の符号の具体例)  

定理 3.4 (置換の符号の一意性)   置換 $\sigma$ の符号 $\mathrm{sgn}\,(\sigma)$ は 互換の積の表わし方によらず一意に定まる．

定理 3.5 (置換の符号の性質)  

$$\mathrm{sgn}\,(\epsilon)=1$$ (249)

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

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

定義 3.8 (偶置換，奇置換)   $\mathrm{sgn}\,(\sigma)=1$ となる置換を 偶置換と呼び， $\mathrm{sgn}\,(\sigma)=-1$ となる置換を 奇置換と呼ぶ．

例 3.9 (偶置換，奇置換の具体例)  

定義 3.9 (置換全体の集合)   $n$ 文字の置換 $\sigma$ の全体の集合を $S_{n}$ と書く．

注意 3.3 (置換全体の集合の要素の個数)   $n$ 文字の置換は写像

$$\{1,2,\cdots,n\}\quad\to\quad \{k_{1},k_{2},\cdots,k_{n}\}$$ (252)

であるから， その個数は $n$ 個の文字の順列組合わせに等しい． よって集合 $S_{n}$ の個数は $n!$ である．

例 3.10 (置換全体の集合の具体例)  

$$S_{1} =\left\{ \begin{pmatrix}1 \\ 1 \end{pmatrix} \right\}= \{\underset{\text{偶}}{\epsilon}\}$$ (253)

$$S_{2} = \left\{ \begin{pmatrix}1 & 2 \\ 1 & 2 \end{pmatrix}, \begin{pma... ...} \right\}= \{ \underset{\text{偶}}{\epsilon},\, \underset{\text{奇}}{(1,2)} \}$$ (254)

$$S_{3} =$$ (255)

問 3.1   $4$ 次の置換全体の集合 $S_4$ の要素全てを書き出せ． またその偶奇も述べよ．

問 3.2   $S_{n}$ $(n\geq2)$ に含まれる偶置換と奇置換の個数は等しい． これを示せ．

Kondo Koichi
Created at 2002/07/22