置換群の類等式

置換群$S_n$というのは、$\{1,\ldots,n\}$の自己同型写像全体の集合である。
これの共役類は、置換が持つサイクルの構造によって決まるのだが、式が複雑なので総和をとったらきちんと$n!$に戻ってくれるのか不安になってしまう。
この記事ではちゃんと$n!$になっていることを証明する。

注意点

このの方法ではうまくいかない。

・$a_1+\cdots+a_m=n$として、$m$をサイクルの個数,$a_k$を$k$番目の巡回置換の長さとする。

何故かというと、$a_i=a_j(i\neq j)$となるようなものがあった場合、同じ長さの巡回置換があることによる対称性を考慮しなくてはいけない。よって共役類の数を単純な$a_1,\ldots,a_m$による関数で書き下すことが出来ないからである。
じゃあどうすればいいのか、以下の証明が答えである。

証明

$a_k\quad(1\leq k\leq n)$を、「長さ$k$の巡回置換をいくつ持っているか」という数とする。ここで、
$$n=\sum_{k=1}^{n}ka_k$$
が成立していて、$a_k\geq 0$である。

このような構造を持った共役類にいくつの元が入っているかを考える。
まず、$n$個の元をそれぞれのサイクルに割り当てる組み合わせを考えると
$$\frac{n!}{1!^{a_1}\cdots n!^{a_n}}$$
となっている。さらに、同じ長さのサイクルは区別しないため
$$\frac{1}{a_1!\cdots a_n!}$$
で割る。
さらに、サイクルの中で円順列を考えているため
$$0!^{a_1}\cdots (n-1)!^{a_n}$$
を掛ける。
すると結局、長さ$k$のサイクルを$a_k$個もっているような置換の個数は
$$\frac{n!}{1^{a_1}\cdots n^{a_n}a_1!\cdots a_n!}$$
となる。よって示すべきは以下の等式である。
$$\sum_{a_1+\cdots+na_n=n}\frac{n!}{1^{a_1}\cdots n^{a_n}a_1!\cdots a_n!}=n!$$
両辺を$n!$で割ることで、これは以下の式と同値である。
$$\sum_{a_1+\cdots+na_n=n}\frac{1}{1^{a_1}\cdots n^{a_n}a_1!\cdots a_n!}=1$$
ここで、この数列の母関数を考えてみる。つまり、
$$\sum_{m=0}^{\infty}\quad \sum_{a_1+\cdots+na_n=m}\frac{1}{1^{a_1}\cdots n^{a_n}a_1!\cdots a_n!}x^m$$
という形で書ける級数である。これはいかのように書ける
$$=\sum_{m=0}^{\infty}\quad \sum_{a_1+\cdots+na_n=m}\frac{1}{1^{a_1}\cdots n^{a_n}a_1!\cdots a_n!}x^{a_1+\cdots+na_n}$$
$$=\sum_{a_1=0}^{\infty}\cdots \sum_{a_n=0}^{\infty}\frac{1}{1^{a_1}\cdots n^{a_n}a_1!\cdots a_n!}x^{a_1+\cdots+na_n}$$
これをテイラー展開したときの$x^m$の項の係数を求めれば良い。
ここで、この関数は積の形になっているので以下のように因数分解することが出来る。
$$=\left(\sum_{a_1=0}^{\infty}\frac{1}{1^{a_1}a_1!}x^{a_1}\right)\cdots\left(\sum_{a_n=0}^{\infty}\frac{1}{n^{a_1}a_n!}x^{na_n}\right)$$
これはよく吟味してみるとexpのテイラー展開の形で書けることがわかるため、以下のようになる。
$$=\exp\left(\frac{x}{1}\right)\cdots\exp\left(\frac{x^n}{n}\right)$$
$$=\exp\left(1+\frac{x^2}{2}+\cdots+\frac{x^n}{n}\right)$$
これをテイラー展開したときの$x^n$の項の係数を考えれば良い。
そしてこれは、以下の関数で考えても問題ないことがわかる。
$$\exp\left(1+\frac{x^2}{2}+\cdots+\frac{x^n}{n}+\frac{x^{n+1}}{n+1}+\cdots\right)$$
何故かというと、$\exp\left(\frac{x^m}{m}\right)(m\geq n+1)$を掛けたところで、関数のテイラー展開の$n$項目までは同じだからである。つまり、$\exp\left(\frac{x^m}{m}\right)$を掛けても関数の$x^n$の項の係数は変わらないのである。

ここで、
$$x+\frac{x^2}{2}+\frac{x^3}{3}+\cdots=-\log{(1-x)}$$
となっている。よって、
$$\exp\left(x+\frac{x^2}{2}+\cdots+\frac{x^n}{n}+\frac{x^{n+1}}{n+1}+\cdots\right)$$
$$=\exp{(-\log{(1-x)})}$$
$$=\frac{1}{1-x}=1+x+x^2+\cdots$$
となっている。
よって各項のテイラー展開の係数は1となるため、示すべき等式が示された。