円順列における「固定」と完全代表系
はじめに
- この記事で伝えたい事：円順列の問題を解く時よくある「1人を固定する」というのは要するに「完全代表系を張っている」
- 想定読者：大学数学から高校数学を眺めてみたい人
- この記事を読む為にあった方がいい予備知識：群作用の基本、軌道空間
$\ $ - 記号の約束1：集合$\{1,2,\cdots ,n\}$を$[n]$と書く。
- 記号の約束2：集合$\{f\ |\ f:[n]\rightarrow[m]\ ,\ fは単射 \}$を$F_{[n]\overset{inj}{\rightarrow}[m]}$と書き、これを 順列全体 という。(injはinjective:単射の頭文字より)
- 記号の約束3：$\hookrightarrow$は包含写像
- 記号の約束4：$\twoheadrightarrow$は集合$X$から商集合$X/{\sim}$への標準射影
$n$人の円順列とは順列全体$F_{[n]\overset{inj}{\rightarrow}[n]}$に巡回群$C_n$を右から群作用させた時の軌道空間$\displaystyle F_{[n]\overset{inj}{\rightarrow}[n]} /{C_n} $である。
任意に$k,l\in [n]$を取ってくる。(つまり番号$k$を$l$番目に配置する。)
この時、$F_{[n]\overset{inj}{\rightarrow}[n]}$の部分集合$\{f\in F_{[n]\overset{inj}{\rightarrow}[n]}\ |\ f(k)=l \}$ は軌道空間$\displaystyle F_{[n]\overset{inj}{\rightarrow}[n]} /{C_n} $の完全代表系である。
$R:=\{f\in F_{[n]\overset{inj}{\rightarrow}[n]}\ |\ f(k)=l \}$として、包含写像と標準射影の合成$\pi : R\hookrightarrow F_{[n]\overset{inj}{\rightarrow}[n]} \twoheadrightarrow \displaystyle F_{[n]\overset{inj}{\rightarrow}[n]} /{C_n}$が全単射である事を示す。この命題を示す為に以下の補題を用意する。
任意の$k,l\in [n]$を取ってくる。この時、$F_{[n]\overset{inj}{\rightarrow}[n]}$の部分集合$R:=\{f\in F_{[n]\overset{inj}{\rightarrow}[n]}\ |\ f(k)=l \}$のどの元に対しても、単位元以外の$C_n$の元を右から作用させると、この集合から飛び出す。
単位元以外の元$\sigma\in C_n$を取ってくる。この時、$\sigma$は$C_n$の元だから、$\sigma(k)\neq k$。よって$\forall f\in R$に対して、$f$は定義より単射だから$\ \ f\circ \sigma(k)\neq f(k)=l$。よって$R$の定義より、$f\circ \sigma \notin R$
$f,g\in R$に対して、$\pi (f) =\pi (g) $とする。この時、$f \sim g$より、$ \exists c \in C_n,f\circ c=g$補題2よりこれを満たすのは$c$が単位元の時に限る。よって$f=g$ $\square$
「軌道空間の任意の元に対して、あるRの元が取って来れて$\pi$で対応させる事が出来る」事を示せばよい。言い換えると、軌道空間の任意の元に対して、どういう風に代表元$f$を取ってきても、$f$と同じ軌道にある$R$の元$g$が存在する事を示せばよい。
任意の$\overline{f} \in F_{[n]\overset{inj}{\rightarrow}[n]} /{C_n}$に対して、$f\in F_{[n]\overset{inj}{\rightarrow}[n]}$より、$f(a)=l$なる$a \in [n]$が存在する。$\sigma \in C_n$を$\sigma(k)=a$となるように取ってきて、$g=f\circ \sigma$とすると、$g\sim f$であってかつ、$g(k)=f\circ \sigma (k)= f(a) =l$より$g\in R\ $ よって$\pi (g)=\overline{f}$ $\square$
具体例$(n=3)$
$F_{[3]\overset{inj}{\rightarrow}[3]}$は以下の6つ元からなる集合である。
- $f_1(1)=1,f_1(2)=2,f_1(3)=3\rightarrow順列(123)に対応$
- $f_2(1)=1,f_2(2)=3,f_2(3)=2\rightarrow順列(132)に対応$
- $f_3(1)=2,f_3(2)=1,f_3(3)=3\rightarrow順列(213)に対応$
- $f_4(1)=2,f_4(2)=3,f_4(3)=1\rightarrow順列(231)に対応$
- $f_5(1)=3,f_5(2)=1,f_5(3)=2\rightarrow順列(312)に対応$
- $f_6(1)=3,f_6(2)=2,f_6(3)=1\rightarrow順列(321)に対応$
軌道空間：$F_{[3]\overset{inj}{\rightarrow}[3]}/
{C_3}=\{\overline{f_1},\overline{f_2}\}$
分割：$\overline{f_1}=\{f_1,f_4 ,f_5 \}$,$\overline{f_2}=\{f_2,f_3 ,f_6 \}$
次に適当に$k,l$を選ぶ。$k=2\in [3],l=3\in [3]$とおくと、$\{f\in F_{[3]\overset{inj}{\rightarrow}[3]}\ |\ f(2)=3 \} =\{ f_2, f_4\}$
$f_2\in \overline{f_2},f_4 \in \overline{f_1}$であるので、確かに軌道空間$F_{[3]\overset{inj}{\rightarrow}[3]}/
{C_3}$の完全代表系を張っている。
具体例$(n=4)$
$F_{[4]\overset{inj}{\rightarrow}[4]}$は以下の24の元からなる集合である。
- $f_{1}(1)=1,f_{1}(2)=2,f_{1}(3)=3,f_{1}(4)=4\rightarrow順列(1234)に対応$
- $f_{2}(1)=1,f_{2}(2)=2,f_{2}(3)=4,f_{2}(4)=3\rightarrow順列(1243)に対応$
- $f_{3}(1)=1,f_{3}(2)=3,f_{3}(3)=2,f_{3}(4)=4\rightarrow順列(1324)に対応$
- $f_{4}(1)=1,f_{4}(2)=3,f_{4}(3)=4,f_{4}(4)=2\rightarrow順列(1342)に対応$
- $f_{5}(1)=1,f_{5}(2)=4,f_{5}(3)=2,f_{5}(4)=3\rightarrow順列(1423)に対応$
- $f_{6}(1)=1,f_{6}(2)=4,f_{6}(3)=3,f_{6}(4)=2\rightarrow順列(1432)に対応$
- $f_{7}(1)=2,f_{7}(2)=1,f_{7}(3)=3,f_{7}(4)=4\rightarrow順列(2134)に対応$
- $f_{8}(1)=2,f_{8}(2)=1,f_{8}(3)=4,f_{8}(4)=3\rightarrow順列(2143)に対応$
- $f_{9}(1)=2,f_{9}(2)=3,f_{9}(3)=1,f_{9}(4)=4\rightarrow順列(2314)に対応$
- $f_{10}(1)=2,f_{10}(2)=3,f_{10}(3)=4,f_{10}(4)=1\rightarrow順列(2341)に対応$
- $f_{11}(1)=2,f_{11}(2)=4,f_{11}(3)=1,f_{11}(4)=3\rightarrow順列(2413)に対応$
- $f_{12}(1)=2,f_{12}(2)=4,f_{12}(3)=3,f_{12}(4)=1\rightarrow順列(2431)に対応$
- $f_{13}(1)=3,f_{13}(2)=1,f_{13}(3)=2,f_{13}(4)=4\rightarrow順列(3124)に対応$
- $f_{14}(1)=3,f_{14}(2)=1,f_{14}(3)=4,f_{14}(4)=2\rightarrow順列(3142)に対応$
- $f_{15}(1)=3,f_{15}(2)=2,f_{15}(3)=1,f_{15}(4)=4\rightarrow順列(3214)に対応$
- $f_{16}(1)=3,f_{16}(2)=2,f_{16}(3)=4,f_{16}(4)=1\rightarrow順列(3241)に対応$
- $f_{17}(1)=3,f_{17}(2)=4,f_{17}(3)=1,f_{17}(4)=2\rightarrow順列(3412)に対応$
- $f_{18}(1)=3,f_{18}(2)=4,f_{18}(3)=2,f_{18}(4)=1\rightarrow順列(3421)に対応$
- $f_{19}(1)=4,f_{19}(2)=1,f_{19}(3)=2,f_{19}(4)=3\rightarrow順列(4123)に対応$
- $f_{20}(1)=4,f_{20}(2)=1,f_{20}(3)=3,f_{20}(4)=2\rightarrow順列(4132)に対応$
- $f_{21}(1)=4,f_{21}(2)=2,f_{21}(3)=1,f_{21}(4)=3\rightarrow順列(4213)に対応$
- $f_{22}(1)=4,f_{22}(2)=2,f_{22}(3)=3,f_{22}(4)=1\rightarrow順列(4231)に対応$
- $f_{23}(1)=4,f_{23}(2)=3,f_{23}(3)=1,f_{23}(4)=2\rightarrow順列(4312)に対応$
- $f_{24}(1)=4,f_{24}(2)=3,f_{24}(3)=2,f_{24}(4)=1\rightarrow順列(4321)に対応$
軌道空間：$F_{[4]\overset{inj}{\rightarrow}[4]}/
{C_4}=\{ \overline{f_1}, \overline{f_2}, \overline{f_3}, \overline{f_4}, \overline{f_5}, \overline{f_6} \}$
分割：$\overline{f_1}=\{f_1, f_{10}, f_{17},f_{19} \}$,
$\ \ \ \ \ \ \ \ \ \ \ \ \ \overline{f_2}=\{f_{2},f_{12},f_{13},f_{23} \}$,
$\ \ \ \ \ \ \ \ \ \ \ \ \ \overline{f_3}=\{f_3, f_{11},f_{16},f_{20}\}$,
$\ \ \ \ \ \ \ \ \ \ \ \ \ \overline{f_4}=\{f_4,f_{7},f_{18},f_{21 } \}$,
$\ \ \ \ \ \ \ \ \ \ \ \ \ \overline{f_5}=\{f_5,f_{9},f_{14},f_{22} \}$,
$\ \ \ \ \ \ \ \ \ \ \ \ \ \overline{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{inj}{\rightarrow}[4]}\ |\ f(4)= 2\} =\{ f_{4}, f_{6}, f_{14}, f_{17}, f_{20}, f_{23}\}$
$f_{4} \in \overline{f_{4}}\ $, $f_{6} \in \overline{f_{6}}\ $,$f_{14} \in \overline{f_{5}}\ $,$f_{17} \in \overline{f_{1}}\ $,$f_{20} \in \overline{f_{3}}\ $,$f_{23} \in \overline{f_{2}}$
であるので、確かに軌道空間$F_{[4]\overset{inj}{\rightarrow}[4]}/
{C_4}$の完全代表系を張っている。