モンモール数の母関数による導出

はじめに

この記事は以下の記事の続編である。
置換群の類等式

導出

ある順列が完全順列であるためには、その順列をサイクルで分解したときに、長さ$1$のサイクルが存在しないことと同値である。

よって、上記の記事において、$a_1=0$としたときの場合の数を考えたら良い。

つまり、長さ$n$の置換全体の場合の数は

$$n!\cdot [x^n]\exp\left(x+\dfrac{x^2}{2}+\cdots+\dfrac{x^n}{n}\right)$$

であるが、長さ1のサイクルが存在しないような置換の総数は

$$n!\cdot [x^n]\exp\left(\dfrac{x^2}{2}+\cdots+\dfrac{x^n}{n}\right)$$

である。

これを計算すると

$$\begin{aligned}n!\cdot [x^n]\exp\left(\dfrac{x^2}{2}+\cdots+\dfrac{x^n}{n}\right)&=n!\cdot [x^n]\exp\left(-x+x+\dfrac{x^2}{2}+\cdots+\dfrac{x^n}{n}\right)\\&=n!\cdot [x^n]\exp\left(-x-\log{(1-x)}\right)\\&=n!\cdot [x^n]\dfrac{1}{1-x}e^{-x}\\&=n!\cdot \left(\sum_{k=0}^{n}[x^k]e^{-x}\cdot [x^{n-k}]\dfrac{1}{1-x}\right)\\&=n!\cdot \left(\sum_{k=0}^{n}[x^k]e^{-x}\right)\\&=n!\left(\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}\right)\\&=\sum_{k=0}^{n}(-1)^k\dfrac{n!}{k!}\end{aligned}$$

となる。これはモンモール数の公式そのものである。