対称群の定義

• $[n] = \{0,1,\ldots, n-1\}$ としたとき、$[n]$ から $[n]$ への全単射全体とその合成で成す群を$n$次対称群 (symmetric group) といい、$S_n$ などで表す

対称群の諸概念

• 置換: 対称群の元のこと
• 巡回置換
• 互換
• 隣接互換
• 置換群: 対称群の部分群
• 転倒数
• 符号
  • (-1) の転倒数乗
• 偶置換・奇置換
  • 符号が+1 （転倒数が偶数）のとき偶置換
  • そうでないとき奇置換
• 交代群
  • 偶置換全体の群。Ker sgn とも言える。

対称群の性質

• 任意の置換は巡回置換の積で表せる
  • 置換を functional graph として見て連結成分を考えれば良い。
• 任意の巡回置換は互換の積で表せる

  • 例えば、$(1,3,4)$ は $(3,4)(1,3)$ で表せる

    初期値	$1, 2 ,3, 4$
    $(1, 3)$	$3, 2, 1, 4$
    $(3, 4)$	$3, 2, 4, 1$

• 任意の互換は隣接互換の積で表せる
  • パズドラをする
• 任意の置換に対して、その置換が $k$ 個の巡回置換の積で表せるとき、$n-k$ 個の互換の積で表せる

転倒数

• 転倒数の定義
  • 置換 $\sigma$ の転倒数は $i < j$ かつ $\sigma(i)> \sigma(j)$ となる組 $(i, j)$ の数