円順列における「固定」と完全代表系

251

はじめに

この記事で伝えたい事：円順列の問題を解く時よくある「1人を固定する」というのは要するに「完全代表系を張っている」
想定読者：大学数学から高校数学を眺めてみたい人
この記事を読む為にあった方がいい予備知識：群作用の基本、軌道空間
記号の約束1：集合 ${1, 2, \dots, n}$ を $[n]$ と書く。
記号の約束2：集合 ${f | f : [n] \to [m], f は単射}$ を $F_{[n] \overset{i n j}{\to} [m]}$ と書き、これを順列全体という。(injはinjective:単射の頭文字より)
記号の約束3： $↪$ は包含写像
記号の約束4： $↠$ は集合 $X$ から商集合 $X / \sim$ への標準射影

円順列

$n$ 人の円順列とは順列全体 $F_{[n] \overset{i n j}{\to} [n]}$ に巡回群 $C_{n}$ を右から群作用させた時の軌道空間 $F_{[n] \overset{i n j}{\to} [n]} / C_{n}$ である。

完全代表系と円順列における「固定」

任意に $k, l \in [n]$ を取ってくる。(つまり番号 $k$ を $l$ 番目に配置する。)
　この時、 $F_{[n] \overset{i n j}{\to} [n]}$ の部分集合 ${f \in F_{[n] \overset{i n j}{\to} [n]} | f (k) = l}$ は軌道空間 $F_{[n] \overset{i n j}{\to} [n]} / C_{n}$ の完全代表系である。

$R := {f \in F_{[n] \overset{i n j}{\to} [n]} | f (k) = l}$ として、包含写像と標準射影の合成 $π : R ↪ F_{[n] \overset{i n j}{\to} [n]} ↠ F_{[n] \overset{i n j}{\to} [n]} / C_{n}$ が全単射である事を示す。この命題を示す為に以下の補題を用意する。

任意の $k, l \in [n]$ を取ってくる。この時、 $F_{[n] \overset{i n j}{\to} [n]}$ の部分集合 $R := {f \in F_{[n] \overset{i n j}{\to} [n]} | f (k) = l}$ のどの元に対しても、単位元以外の $C_{n}$ の元を右から作用させると、この集合から飛び出す。

補題2

単位元以外の元 $σ \in C_{n}$ を取ってくる。この時、 $σ$ は $C_{n}$ の元だから、 $σ (k) \neq k$ 。よって $\forall f \in R$ に対して、 $f$ は定義より単射だから $f \circ σ (k) \neq f (k) = l$ 。よって $R$ の定義より、 $f \circ σ \notin R$

命題1

π : R ↪ F_{[n] \overset{i n j}{\to} [n]} ↠ F_{[n] \overset{i n j}{\to} [n]} / C_{n}

が単射

$f, g \in R$ に対して、 $π (f) = π (g)$ とする。この時、 $f \sim g$ より、 $\exists c \in C_{n}, f \circ c = g$ 補題2よりこれを満たすのは $c$ が単位元の時に限る。よって $f = g$ $◻$

命題1

π : R ↪ F_{[n] \overset{i n j}{\to} [n]} ↠ F_{[n] \overset{i n j}{\to} [n]} / C_{n}

が全射

「軌道空間の任意の元に対して、あるRの元が取って来れて $π$ で対応させる事が出来る」事を示せばよい。言い換えると、軌道空間の任意の元に対して、どういう風に代表元 $f$ を取ってきても、 $f$ と同じ軌道にある $R$ の元 $g$ が存在する事を示せばよい。

任意の $\overset{―}{f} \in F_{[n] \overset{i n j}{\to} [n]} / C_{n}$ に対して、 $f \in F_{[n] \overset{i n j}{\to} [n]}$ より、 $f (a) = l$ なる $a \in [n]$ が存在する。 $σ \in C_{n}$ を $σ (k) = a$ となるように取ってきて、 $g = f \circ σ$ とすると、 $g \sim f$ であってかつ、 $g (k) = f \circ σ (k) = f (a) = l$ より $g \in R$ よって $π (g) = \overset{―}{f}$ $◻$

具体例 $(n = 3)$

$F_{[3] \overset{i n j}{\to} [3]}$ は以下の6つ元からなる集合である。

$f_{1} (1) = 1, f_{1} (2) = 2, f_{1} (3) = 3 \to 順列 (123) に対応$
$f_{2} (1) = 1, f_{2} (2) = 3, f_{2} (3) = 2 \to 順列 (132) に対応$
$f_{3} (1) = 2, f_{3} (2) = 1, f_{3} (3) = 3 \to 順列 (213) に対応$
$f_{4} (1) = 2, f_{4} (2) = 3, f_{4} (3) = 1 \to 順列 (231) に対応$
$f_{5} (1) = 3, f_{5} (2) = 1, f_{5} (3) = 2 \to 順列 (312) に対応$
$f_{6} (1) = 3, f_{6} (2) = 2, f_{6} (3) = 1 \to 順列 (321) に対応$

軌道空間： $F_{[3] \overset{i n j}{\to} [3]} / C_{3} = {\overset{―}{f_{1}}, \overset{―}{f_{2}}}$
　分割： $\overset{―}{f_{1}} = {f_{1}, f_{4}, f_{5}}$ , $\overset{―}{f_{2}} = {f_{2}, f_{3}, f_{6}}$

次に適当に $k, l$ を選ぶ。 $k = 2 \in [3], l = 3 \in [3]$ とおくと、 ${f \in F_{[3] \overset{i n j}{\to} [3]} | f (2) = 3} = {f_{2}, f_{4}}$
$f_{2} \in \overset{―}{f_{2}}, f_{4} \in \overset{―}{f_{1}}$ であるので、確かに軌道空間 $F_{[3] \overset{i n j}{\to} [3]} / C_{3}$ の完全代表系を張っている。

具体例 $(n = 4)$

$F_{[4] \overset{i n j}{\to} [4]}$ は以下の24の元からなる集合である。

$f_{1} (1) = 1, f_{1} (2) = 2, f_{1} (3) = 3, f_{1} (4) = 4 \to 順列 (1234) に対応$
$f_{2} (1) = 1, f_{2} (2) = 2, f_{2} (3) = 4, f_{2} (4) = 3 \to 順列 (1243) に対応$
$f_{3} (1) = 1, f_{3} (2) = 3, f_{3} (3) = 2, f_{3} (4) = 4 \to 順列 (1324) に対応$
$f_{4} (1) = 1, f_{4} (2) = 3, f_{4} (3) = 4, f_{4} (4) = 2 \to 順列 (1342) に対応$
$f_{5} (1) = 1, f_{5} (2) = 4, f_{5} (3) = 2, f_{5} (4) = 3 \to 順列 (1423) に対応$
$f_{6} (1) = 1, f_{6} (2) = 4, f_{6} (3) = 3, f_{6} (4) = 2 \to 順列 (1432) に対応$
$f_{7} (1) = 2, f_{7} (2) = 1, f_{7} (3) = 3, f_{7} (4) = 4 \to 順列 (2134) に対応$
$f_{8} (1) = 2, f_{8} (2) = 1, f_{8} (3) = 4, f_{8} (4) = 3 \to 順列 (2143) に対応$
$f_{9} (1) = 2, f_{9} (2) = 3, f_{9} (3) = 1, f_{9} (4) = 4 \to 順列 (2314) に対応$
$f_{10} (1) = 2, f_{10} (2) = 3, f_{10} (3) = 4, f_{10} (4) = 1 \to 順列 (2341) に対応$
$f_{11} (1) = 2, f_{11} (2) = 4, f_{11} (3) = 1, f_{11} (4) = 3 \to 順列 (2413) に対応$
$f_{12} (1) = 2, f_{12} (2) = 4, f_{12} (3) = 3, f_{12} (4) = 1 \to 順列 (2431) に対応$
$f_{13} (1) = 3, f_{13} (2) = 1, f_{13} (3) = 2, f_{13} (4) = 4 \to 順列 (3124) に対応$
$f_{14} (1) = 3, f_{14} (2) = 1, f_{14} (3) = 4, f_{14} (4) = 2 \to 順列 (3142) に対応$
$f_{15} (1) = 3, f_{15} (2) = 2, f_{15} (3) = 1, f_{15} (4) = 4 \to 順列 (3214) に対応$
$f_{16} (1) = 3, f_{16} (2) = 2, f_{16} (3) = 4, f_{16} (4) = 1 \to 順列 (3241) に対応$
$f_{17} (1) = 3, f_{17} (2) = 4, f_{17} (3) = 1, f_{17} (4) = 2 \to 順列 (3412) に対応$
$f_{18} (1) = 3, f_{18} (2) = 4, f_{18} (3) = 2, f_{18} (4) = 1 \to 順列 (3421) に対応$
$f_{19} (1) = 4, f_{19} (2) = 1, f_{19} (3) = 2, f_{19} (4) = 3 \to 順列 (4123) に対応$
$f_{20} (1) = 4, f_{20} (2) = 1, f_{20} (3) = 3, f_{20} (4) = 2 \to 順列 (4132) に対応$
$f_{21} (1) = 4, f_{21} (2) = 2, f_{21} (3) = 1, f_{21} (4) = 3 \to 順列 (4213) に対応$
$f_{22} (1) = 4, f_{22} (2) = 2, f_{22} (3) = 3, f_{22} (4) = 1 \to 順列 (4231) に対応$
$f_{23} (1) = 4, f_{23} (2) = 3, f_{23} (3) = 1, f_{23} (4) = 2 \to 順列 (4312) に対応$
$f_{24} (1) = 4, f_{24} (2) = 3, f_{24} (3) = 2, f_{24} (4) = 1 \to 順列 (4321) に対応$

軌道空間： $F_{[4] \overset{i n j}{\to} [4]} / C_{4} = {\overset{―}{f_{1}}, \overset{―}{f_{2}}, \overset{―}{f_{3}}, \overset{―}{f_{4}}, \overset{―}{f_{5}}, \overset{―}{f_{6}}}$
　分割： $\overset{―}{f_{1}} = {f_{1}, f_{10}, f_{17}, f_{19}}$ ,
$\overset{―}{f_{2}} = {f_{2}, f_{12}, f_{13}, f_{23}}$ ,
$\overset{―}{f_{3}} = {f_{3}, f_{11}, f_{16}, f_{20}}$ ,
$\overset{―}{f_{4}} = {f_{4}, f_{7}, f_{18}, f_{21}}$ ,
$\overset{―}{f_{5}} = {f_{5}, f_{9}, f_{14}, f_{22}}$ ,
$\overset{―}{f_{6}} = {f_{6}, f_{8}, f_{15}, f_{24}}$
次に適当に $k, l$ を選ぶ。 $k = 4 \in [4], l = 2 \in [4]$ とおくと、
$R := {f \in F_{[4] \overset{i n j}{\to} [4]} | f (4) = 2} = {f_{4}, f_{6}, f_{14}, f_{17}, f_{20}, f_{23}}$
$f_{4} \in \overset{―}{f_{4}}$ , $f_{6} \in \overset{―}{f_{6}}$ , $f_{14} \in \overset{―}{f_{5}}$ , $f_{17} \in \overset{―}{f_{1}}$ , $f_{20} \in \overset{―}{f_{3}}$ , $f_{23} \in \overset{―}{f_{2}}$
であるので、確かに軌道空間 $F_{[4] \overset{i n j}{\to} [4]} / C_{4}$ の完全代表系を張っている。