4.2 置換

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

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

のとき $ \sigma$

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

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

4.2 (置換の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix}\,,$ (592)
  $\displaystyle 1\to3\,,\quad 2\to1\,,\quad 4\to4\,,\quad 4\to2\,,$ (593)
  $\displaystyle \sigma(1)=3\,,\quad \sigma(2)=1\,,\quad \sigma(4)=4\,,\quad \sigma(4)=2\,.$ (594)

4.3 (置換の表記)  

$\displaystyle \begin{pmatrix}1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{pmatrix}= \beg...
...4 & 1 & 3 \end{pmatrix}= \begin{pmatrix}3 & 1 & 4 \\ 4 & 3 & 1 \end{pmatrix}\,.$ (595)

同じ数字に置換する場合は省略可能. 並べる順はどうでも良い.

定義 4.4 (置換の積)   二つの置換

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k_{n} \end{pmatrix}\,,$ (596)
$\displaystyle \tau$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ l_{1} & l_{2} & \cdots & l_{n} \end{pmatrix}$ (597)

の積 $ \sigma\tau$

$\displaystyle \sigma\tau$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k...
...rix}1 & 2 & \cdots & n \\ k_{l_1} & k_{l_2} & \cdots & k_{l_n} \end{pmatrix}\,,$ (598)

または

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

と定義する.

4.5 (置換の積の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}\,,\quad \tau= \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}\,,$ (600)
$\displaystyle \sigma\tau$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix} \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}$ (601)
  $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ \sigma(\tau(1)) & \sigma(\tau(2...
...ix}1 & 2 & 3 & 4 \\ \sigma(2) & \sigma(3) & \sigma(4) & \sigma(1) \end{pmatrix}$ (602)
  $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}\,,$ (603)
$\displaystyle \tau\sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix} \begin{pmatrix}1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}$ (604)
  $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ \tau(\sigma(1)) & \tau(\sigma(2...
...in{pmatrix}1 & 2 & 3 & 4 \\ \tau(4) & \tau(3) & \tau(1) & \tau(2) \end{pmatrix}$ (605)
  $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 1 & 4 & 2 & 3 \end{pmatrix}\,.$ (606)

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

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

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

単位置換と呼ぶ.

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

$\displaystyle \sigma\tau=\tau\sigma=\epsilon$ (608)

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

定理 4.9 (逆置換)   置換

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

の逆置換は

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

で与えられる.

4.10 (逆置換の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 1 & 3 & 2 \end{pmatrix}\,,$ (611)
$\displaystyle \sigma^{-1}$ $\displaystyle = \begin{pmatrix}4 & 5 & 1 & 3 & 2 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}= \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix}\,.$ (612)

定義 4.11 (巡回置換)   $ 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}$ と動かさない 写像の置換を巡回置換という. 巡回置換は

$\displaystyle \sigma$ $\displaystyle = \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}$ (613)
  $\displaystyle = \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{r-1} & k_{r} \\ k_{2} & k_{3} & \cdots & k_{r} & k_{1} \end{pmatrix}$ (614)

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

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{r} \end{pmatrix}$ (615)

と書く.

4.12 (巡回置換の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 2 & 4 & 3 \end{pmat...
...\\ 5 & 2 & 3 \end{pmatrix}= \begin{pmatrix}2 & 5 & 3 \\ 5 & 3 & 2 \end{pmatrix}$ (616)
  $\displaystyle = \begin{pmatrix}2 & 5 & 3 \end{pmatrix}= \begin{pmatrix}5 & 3 & 2 \end{pmatrix}= \begin{pmatrix}3 & 2 & 5 \end{pmatrix}\,,$ (617)
$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 4 & 5 \end{pmat...
...\\ 3 & 1 & 2 \end{pmatrix}= \begin{pmatrix}1 & 3 & 2 \\ 3 & 2 & 1 \end{pmatrix}$ (618)
  $\displaystyle = \begin{pmatrix}1 & 3 & 2 \end{pmatrix}= \begin{pmatrix}3 & 2 & 1 \end{pmatrix}= \begin{pmatrix}2 & 1 & 3 \end{pmatrix}\,.$ (619)

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

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

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 1 & 6 & 2 & 7 &...
...in{pmatrix}1 & 4 & 2 & 3 & 6 & 5 & 7 \\ 4 & 2 & 1 & 6 & 5 & 7 & 3 \end{pmatrix}$ (620)
  $\displaystyle = \begin{pmatrix}1 & 4 & 2 & 3 & 6 & 5 & 7 \\ 4 & 2 & 1 & 3 & 6 &...
...2 & 1 \end{pmatrix} \begin{pmatrix}3 & 6 & 5 & 7 \\ 6 & 5 & 7 & 3 \end{pmatrix}$ (621)
  $\displaystyle = \begin{pmatrix}1 & 4 & 2 \end{pmatrix} \begin{pmatrix}3 & 6 & 5 & 7 \end{pmatrix}\,.$ (622)

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 5 & 3 & 7 & 1 & 4 &...
...in{pmatrix}1 & 5 & 4 & 2 & 3 & 7 & 6 \\ 5 & 4 & 1 & 3 & 7 & 6 & 2 \end{pmatrix}$ (623)
  $\displaystyle = \begin{pmatrix}1 & 5 & 4 & 2 & 3 & 7 & 6 \\ 5 & 4 & 1 & 2 & 3 &...
...4 & 1 \end{pmatrix} \begin{pmatrix}2 & 3 & 7 & 6 \\ 3 & 7 & 6 & 2 \end{pmatrix}$ (624)
  $\displaystyle = \begin{pmatrix}1 & 5 & 4 \end{pmatrix} \begin{pmatrix}2 & 3 & 7 & 6 \end{pmatrix}\,.$ (625)

定義 4.15 (互換)   $ 2$ 文字の巡回置換 $ (i\quad j)$互換という.

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

$\displaystyle \begin{pmatrix}k_1 & k_2 & \cdots & k_r \end{pmatrix}= \begin{pma...
...s \begin{pmatrix}k_1 & k_3 \end{pmatrix} \begin{pmatrix}k_1 & k_2 \end{pmatrix}$ (626)

と表わされる.

4.17 (置換を互換の積で表わす)   たとえば

$\displaystyle \begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1 \end{pmatrix} \be...
...1 & 4 \end{pmatrix} \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{pmatrix}$ (627)
  $\displaystyle = \begin{pmatrix}1 & 4 \end{pmatrix} \begin{pmatrix}1 & 3 \end{pmatrix} \begin{pmatrix}1 & 2 \end{pmatrix}\,.$ (628)

たとえば

$\displaystyle \begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}$ $\displaystyle = \begin{pmatrix}1 & 3 \end{pmatrix} \begin{pmatrix}1 & 4 \end{pm...
...atrix} \begin{pmatrix}2 & 3 \end{pmatrix} \begin{pmatrix}1 & 3 \end{pmatrix}\,.$ (629)

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

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

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

と定義する.

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

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}= \begin{pmatrix}1 & ...
...{pmatrix} \begin{pmatrix}1 & 3 \end{pmatrix} \begin{pmatrix}1 & 2 \end{pmatrix}$ (631)

より

$\displaystyle \mathrm{sgn}\,(\sigma)$ $\displaystyle = (-1)^{3}=-1$ (632)

となる.また

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}= \begin{pmatrix}1 & ...
...{pmatrix} \begin{pmatrix}2 & 3 \end{pmatrix} \begin{pmatrix}1 & 3 \end{pmatrix}$ (633)

より

$\displaystyle \mathrm{sgn}\,(\sigma)$ $\displaystyle = (-1)^{5}=-1$ (634)

である.

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

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

  $\displaystyle \mathrm{sgn}\,(\epsilon)=1$ (635)
  $\displaystyle \mathrm{sgn}\,(\sigma\tau)=\mathrm{sgn}\,(\sigma)\mathrm{sgn}\,(\tau)$ (636)
  $\displaystyle \mathrm{sgn}\,(\sigma^{-1})=\mathrm{sgn}\,(\sigma)$ (637)

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

4.24 (偶置換,奇置換の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 6 & 8 &...
... & 9 & 5 & 2 & 6 & 4 & 3 & 3 \\ 7 & 9 & 5 & 1 & 6 & 4 & 2 & 8 & 2 \end{pmatrix}$ (638)
  $\displaystyle = \begin{pmatrix}1 & 7 & 9 & 5 \\ 7 & 9 & 5 & 1 \end{pmatrix} \be...
...trix} \begin{pmatrix}2 & 6 & 4 \end{pmatrix} \begin{pmatrix}3 & 8 \end{pmatrix}$ (639)
  $\displaystyle = \begin{pmatrix}1 & 5 \end{pmatrix} \begin{pmatrix}1 & 9 \end{pm...
...{pmatrix} \begin{pmatrix}2 & 6 \end{pmatrix} \begin{pmatrix}3 & 8 \end{pmatrix}$ (640)

より

$\displaystyle \mathrm{sgn}\,(\sigma)$ $\displaystyle =(-1)^6=1$ (641)

となる. $ \sigma$ は偶置換である.

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

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

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

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

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

$\displaystyle S_{1}$ $\displaystyle =\left\{ \begin{pmatrix}1 \\ 1 \end{pmatrix} \right\}= \{\underset{\text{偶}}{\epsilon}\}$ (643)
$\displaystyle S_{2}$ $\displaystyle = \left\{ \begin{pmatrix}1 & 2 \\ 1 & 2 \end{pmatrix}, \begin{pma...
...}}{\epsilon},\quad \underset{\text{奇}}{\begin{pmatrix}1 & 2 \end{pmatrix}} \}$ (644)
$\displaystyle S_{3}$ $\displaystyle = \left\{ \begin{pmatrix}1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \b...
...& 2 \end{pmatrix}, \begin{pmatrix}1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \right\}$ (645)
  $\displaystyle = \{ \underset{\text{偶}}{\epsilon},\quad \underset{\text{奇}}{\b...
...end{pmatrix}},\quad \underset{\text{奇}}{\begin{pmatrix}1 & 2 \end{pmatrix}} \}$ (646)

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

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


平成20年2月2日