巡回置換

$\sigma=(a_1\,\cdots\,a_k)$ なら、$a_1$ の軌道は $\{a_1,\dots,a_k\}$（$k\ge2$ 個）であり、他の元はすべて不動点なので軌道は 1 元である。逆に元が $2$ 個以上の軌道がちょうど 1 つなら、置換 の記事の定理「互いに素な巡回置換の積への分解」の証明で作る分解は、その軌道の巡回置換 $(x\ \ \sigma(x)\ \ \cdots\ \ \sigma^{\ell-1}(x))$ ただ 1 つからなり、これが $\sigma$ に等しい。$\square$

帰納法により $c^t(a_j)=a_{j+t}$ なので、$c^m(a_j)=a_{j+m}$ であり、台の外の元は $c^m$ でも動かない。$a_i$ の $c^m$ による軌道は $\{a_{i+tm}\mid t\in\mathbb{Z}\}$ である。$a_{i+tm}=a_i$ となるのは $k\mid tm$ のときであり、$k=dk'$、$m=dm'$（$k',m'$ は互いに素）と書くと、$k\mid tm$ は $k'\mid tm'$、すなわち $k'\mid t$ と同値である。よって $a_i$ が初めて戻るのは $t=k'=k/d$ 回目であり、軌道の元の個数は $k/d$ で、軌道の元は $a_i,a_{i+m},\dots,a_{i+(k/d-1)m}$ である。
$tm$ はすべて $d$ の倍数なので、$a_i$ の軌道の元の添字は $k$ を法として $i$ と合同な $d$ の倍数ずれにある。$0\le j< k$ のうち $j\equiv i\pmod d$ となるものはちょうど $k/d$ 個なので、$a_i$ の軌道は $\{a_j\mid j\equiv i\pmod d\}$ に一致する。したがって台 $\{a_0,\dots,a_{k-1}\}$ は $i=0,\dots,d-1$ に対応する $d$ 個の軌道に分かれ、各軌道の上で $c^m$ は上の巡回置換として働く（置換 の記事の定理「互いに素な巡回置換の積への分解」）。
$c^m=e$ は軌道がすべて 1 元、すなわち $k/d=1$、$k\mid m$ と同値である。$c^m$ が長さ $k$ の巡回置換であることは、元が $2$ 個以上の軌道が台全体の 1 つだけ（prop-cyc-characterization）、すなわち $d=1$ と同値である。$\square$

$\tau$ は単射なので $\tau(a_1),\dots,\tau(a_k)$ は相異なり、右辺は長さ $k$ の巡回置換である。$c=(a_1\,\cdots\,a_k)$ とおく。$y=\tau(a_i)$ なら、左辺は $\tau(c(\tau^{-1}(y)))=\tau(c(a_i))=\tau(a_{i+1})$ であり、右辺も $\tau(a_{i+1})$ である（添字は $k$ を法とする）。$y$ がどの $\tau(a_i)$ とも異なれば $\tau^{-1}(y)\notin\{a_1,\dots,a_k\}$ なので $c$ は $\tau^{-1}(y)$ を動かさず、左辺は $\tau(\tau^{-1}(y))=y$ であり、右辺も $y$ である。
後半について、$\tau\sigma\tau^{-1}=\tau c_1\tau^{-1}\tau c_2\tau^{-1}\cdots\tau c_r\tau^{-1}$ であり、前半により $\tau c_i\tau^{-1}$ は $c_i$ と同じ長さで台が $\tau$（$c_i$ の台）の巡回置換である。$\tau$ は単射なので、これらの台は互いに交わらない。とくに $X=\{1,\dots,n\}$ のとき、分解の一意性により、$\tau\sigma\tau^{-1}$ の長さ $2$ 以上の輪の長さは $\sigma$ と同じであり、不動点の個数（$n$ から台の元の個数の和を引いたもの）も同じなので、巡回型が一致する。$\square$

共役なら巡回型が一致することは prop-cyc-conjugation である。逆に巡回型が一致するとする。不動点も長さ $1$ の輪として、$\sigma$ の輪を長さの順に並べて
$$ \sigma:\ (a_{1,1}\,\cdots\,a_{1,\ell_1})(a_{2,1}\,\cdots\,a_{2,\ell_2})\cdots(a_{r,1}\,\cdots\,a_{r,\ell_r}) $$
と書き、$\rho$ の輪も同じ長さの列 $\ell_1,\dots,\ell_r$ で $(b_{1,1}\,\cdots\,b_{1,\ell_1})\cdots(b_{r,1}\,\cdots\,b_{r,\ell_r})$ と書く（巡回型が同じなのでこう並べられる）。$1,\dots,n$ はどちらの並びにもちょうど 1 回ずつ現れるので、$\tau(a_{i,j}):=b_{i,j}$ は $S_n$ の元を定める。$j$ を $\ell_i$ を法として読むと $\sigma(a_{i,j})=a_{i,j+1}$、$\rho(b_{i,j})=b_{i,j+1}$ であり（長さ $1$ の輪では $a_{i,1}$ も $b_{i,1}$ も不動点である）、
$$ \tau\sigma\tau^{-1}(b_{i,j})=\tau(\sigma(a_{i,j}))=\tau(a_{i,j+1})=b_{i,j+1}=\rho(b_{i,j}) $$
がすべての $b_{i,j}$、すなわち $1,\dots,n$ のすべてで成り立つので $\tau\sigma\tau^{-1}=\rho$ である。巡回型と $n$ の分割の対応は def-cyc-type の後に述べたとおりである。$\square$

長さ $1$ の括弧を $m_1$ 個、長さ $2$ の括弧を $m_2$ 個、…と長さの順に並べ、各括弧に長さと同じ数の空欄を置いた「型紙」を作る。空欄は全部で $n$ 個ある。$1,\dots,n$ を 1 回ずつ並べた列（$n!$ 通り）を左から順に空欄へ書き込むと、各括弧は輪 $(x_1\,\cdots\,x_k)$ になり、それらの積（長さ $1$ の輪は不動点と読む）は巡回型 $1^{m_1}\cdots n^{m_n}$ の置換である。逆にこの巡回型の置換 $\sigma$ は、分解（置換 の記事の定理「互いに素な巡回置換の積への分解」）に現れる輪を型紙に書き込むことで得られる。
同じ $\sigma$ を与える書き込み方の個数を数える。分解の一意性により、$\sigma$ の長さ $k$ の輪の集合は決まっているので、書き込み方は (i) 長さ $k$ の $m_k$ 個の輪を長さ $k$ の $m_k$ 個の括弧にどの順で割り当てるか（$m_k!$ 通り）と、(ii) 各輪をどの元から書き始めるか（長さ $k$ の輪ごとに $k$ 通り）で決まり、これらの選び方が異なれば書き込まれる列も異なる。よって同じ $\sigma$ を与える列はちょうど $\prod_km_k!\,k^{m_k}$ 個あり、求める個数は $n!/\prod_km_k!\,k^{m_k}$ である。$\square$

長さ $k$ の巡回置換の巡回型は $1^{n-k}k^1$ なので、thm-cyc-count により個数は $\dfrac{n!}{(n-k)!\cdot k}=\dbinom nk\dfrac{k!}{k}=\dbinom nk(k-1)!$ である。$\square$

$S_n$ は自分自身に共役 $\tau\cdot\sigma=\tau\sigma\tau^{-1}$ で作用し、$\sigma$ の軌道は $\sigma$ の共役類、安定化群は $C(\sigma)$ である（群の作用 の記事の例「共役による作用」）。thm-cyc-conjugacy-classes により共役類は巡回型が $\sigma$ と同じ置換の全体であり、その個数は thm-cyc-count により $n!/\prod_km_k!\,k^{m_k}$ である。軌道・安定化群定理（群の作用 の記事の定理「軌道・安定化群定理」）により、軌道の元の個数は $|S_n|/|C(\sigma)|$ に等しいので、$|C(\sigma)|=\prod_km_k!\,k^{m_k}$ である。$\square$

長さ $k$ の「輪」$\gamma$ を、$k$ 個の相異なる元を円く並べたもの $(a_1\,\cdots\,a_k)$（書き始めの違いは同一視する。$k=1$ なら 1 点 $(a_1)$）とする。輪 $\gamma$ の個数は、元の選び方 $\binom nk$ と円く並べる方法 $(k-1)!$ の積 $\binom nk(k-1)!$ である。置換 $\sigma$ の分解に $\gamma$ が現れる（$\sigma(a_i)=a_{i+1}$ がすべての $i$ で成り立つ）とき $1$、そうでないとき $0$ となる確率変数を $X_\gamma$ とする。$X_\gamma(\sigma)=1$ となる $\sigma$ は、$a_1,\dots,a_k$ での値が決まっていて、残りの $n-k$ 元の上では残りの $n-k$ 元の置換として任意なので、$(n-k)!$ 個ある。よって $E[X_\gamma]=(n-k)!/n!$ である。長さ $k$ の輪の個数は $X_\gamma$ を長さ $k$ のすべての輪 $\gamma$ について足したものなので、期待値 の記事の定理「期待値の線形性」により、その期待値は
$$ \binom nk(k-1)!\cdot\frac{(n-k)!}{n!}=\frac{n!}{k!\,(n-k)!}\cdot(k-1)!\cdot\frac{(n-k)!}{n!}=\frac1k $$
である。$N$ は長さ $1,\dots,n$ の輪の個数の和なので、再び線形性により $E[N]=\sum_{k=1}^n1/k$ である。$\square$