置換関数
定義
有限集合$X$に対して、全単射$\sigma : X \to X$を$X$の置換関数permutation、または単に置換という。$|X| = n$のときは、元に番号を付けて次のように置くのが慣例である。
$$ X = \left\{ 1, 2, \dots, n \right\} $$
説明
定義上、集合$X$が有限集合である必要はないが、説明を簡単にするため有限集合に限定する。
置換を全単射関数として定義したので、置換は元を重複も欠落もなく並べ直すのと同じ働きをする。したがって$|X| = n$ならば、$\sigma(1)$になり得る値は$n$通り、それが決まれば$\sigma(2)$になり得る値は残りの$n-1$通りであるから、$X$の置換はちょうど$n!$個であり、場合の数としての順列$_{n}P_{n}$と等しい。
$$ {}_{n}P_{n} = \dfrac{n!}{(n-n)!} = n! $$
表記
$X = \left\{ 1, 2, \dots, n \right\}$の置換は、上段に$X$の元を、下段にその元の移り先を書いて表すのが最も直観的である。たとえば$n = 4$で$1 \mapsto 3$、$2 \mapsto 1$、$3 \mapsto 4$、$4 \mapsto 2$である置換は次のように書かれる。
$$ \sigma = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{bmatrix} $$
上の写像をつなげると$1 \to 3 \to 4 \to 2 \to 1$となるので、同じ置換を$\sigma = (1,3,4,2)$のように表すこともある。
一方、置換を$X$の元を移す関数と見る代わりに、変数の添字に作用させて$(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)})$のように書くこともある。上の例であれば、この表記は$(x_{3}, x_{1}, x_{4}, x_{2})$を意味する。