モンモールの問題の応用

示すべき式の左辺は「全ての置換の不動点の数の和」を表している。

一方任意の $i\:(1\leq i\leq n)$ に対して，$i$ が不動点となる置換の数は $(n-1)!$ 個あるので，「全ての置換の不動点の数の和」は，$n\cdot (n-1)!=n!$ とも数えられる。よって問題の等式は示された。

$p_n(n)=1,p_n(n-1)=0$ であり，$k\leq n-2$ のとき，

$p_n(k)={}_n\mathrm{C}_ka_{n-k}$

ただし，$a_{n-k}$ は長さ $n-k$ の攪乱順列の数（不動点の選び方が ${}_n\mathrm{C}_k$ 通りで残りの撹乱の仕方が $a_{n-k}$ 通りとなる）。

これに，攪乱順列の公式を用いると示すべき式の左辺は，

$n+\displaystyle\sum_{k=1}^{n-2}k\dfrac{n!}{k!(n-k)!}\left\{(n-k)!\sum_{t=2}^{n-k}\dfrac{(-1)^t}{t!}\right\}\\ =n+\displaystyle\sum_{k=1}^{n-2}\sum_{t=2}^{n-k}\dfrac{n!(-1)^t}{(k-1)!t!}$

これが $n!$ に等しいことを数学的帰納法で証明する。

つまり， $$N+\displaystyle\sum_{k=1}^{N-2}\sum_{t=2}^{N-k}\dfrac{N!(-1)^t}{(k-1)!t!}=N!$$ という「仮定」のもとで $$(N+1)+\displaystyle\sum_{k=1}^{N-1}\sum_{t=2}^{N+1-k}\dfrac{(N+1)!(-1)^t}{(k-1)!t!}=(N+1)!$$ という「目標」を示せばよい。「目標」の式を変形すると， $$(N+1)+\displaystyle\sum_{k=1}^{N-2}\sum_{t=2}^{N+1-k}\dfrac{(N+1)!(-1)^t}{(k-1)!t!}+\dfrac{(N+1)!}{(N-2)!2!}=(N+1)!$$ つまり $$(N+1)+(N+1)\displaystyle\sum_{k=1}^{N-2}\sum_{t=2}^{N-k}\dfrac{N!(-1)^t}{(k-1)!t!}\\ +\dfrac{(N+1)!}{(N-2)!2!}+\displaystyle\sum_{k=1}^{N-2}\dfrac{(N+1)!(-1)^{N+1-k}}{(k-1)!(N+1-k)!}=(N+1)!$$ つまり $$1+\displaystyle\sum_{k=1}^{N-2}\sum_{t=2}^{N-k}\dfrac{N!(-1)^t}{(k-1)!t!}\\ +\dfrac{N!}{(N-2)!2!}+\displaystyle\sum_{k=1}^{N-2}\dfrac{N!(-1)^{N+1-k}}{(k-1)!(N+1-k)!}=N!$$ となる（ここまでの変形は難しそうだが，「仮定」が使えるようにシグマを分解しただけ）。左辺第二項に「仮定」を使うと $$1-N +\dfrac{N!}{(N-2)!2!}+\displaystyle\sum_{k=1}^{N-2}\dfrac{N!(-1)^{N+1-k}}{(k-1)!(N+1-k)!}=0$$ を示せば良いことがわかる。結局， $$\displaystyle\sum_{k=0}^{N-2}\dfrac{(-1)^{N-k}}{k!(N-k)!}=\dfrac{N-1}{N!}$$ を証明する問題に帰着される。

この式は二項定理の展開式っぽいことに注意すると，

$0=(1-1)^n$ を展開することにより証明できる。