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

はじめに

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

導出

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

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

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

$$n!\cdot [x^n]\exp (x+{\displaystyle \frac{x^2}{2}}+\cdots +{\displaystyle \frac{x^n}{n}})$$

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

$$n!\cdot [x^n]\exp ({\displaystyle \frac{x^2}{2}}+\cdots +{\displaystyle \frac{x^n}{n}})$$

である。

これを計算すると

$$\begin{array}{rl}n!\cdot [x^n]\exp ({\displaystyle \frac{x^2}{2}}+\cdots +{\displaystyle \frac{x^n}{n}})& =n!\cdot [x^n]\exp (-x+x+{\displaystyle \frac{x^2}{2}}+\cdots +{\displaystyle \frac{x^n}{n}})\\ & =n!\cdot [x^n]\exp (-x-\log (1-x))\\ & =n!\cdot [x^n]{\displaystyle \frac{1}{1-x}}{e}^{-x}\\ & =n!\cdot (\sum _{k=0}^n[x^k]e^{-x}\cdot [x^{n-k}]{\displaystyle \frac{1}{1-x}})\\ & =n!\cdot (\sum _{k=0}^n[x^k]e^{-x})\\ & =n!\left(\sum _{k=0}^n{\displaystyle \frac{(-1{)}^k}{k!}}\right)\\ & =\sum _{k=0}^n(-1{)}^k{\displaystyle \frac{n!}{k!}}\end{array}$$

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