montmort_number

<p>
\(n\) 個の要素をもつ順列において、\(i\) 番目 \((i\le n)\) が \(i\) でない順列を撹乱順列、または、完全順列といい、その数をモンモール数 \(a_n\) と呼び、以下のように与えられる。
\[
a_n = n!\sum_{k=2}^{n}\frac{(-1)^k}{k!}
\]
</p>
<p>
同じく、\(n\) 人でプレゼント交換をするとき、全員自分のプレゼントに当たらない確率 \(p_n\) は、全事象の数が \(\permu{n}{n} = n!\) でこの事象の数が \(a_n\) であるので、以下のように表される。
\[
p_n = \frac{a_n}{n!} = \sum_{k=2}^{n}\frac{(-1)^k}{k!}
\]
</p>
<h2>モンモール数の漸化式</h2>
<p>
\[
\begin{aligned}
a_1 &= 0\\
a_2 &= 1\\
a_n &= (n-1)(a_{n-1} + a_{n-2})\\
\end{aligned}
\]
</p>
<p>
この漸化式から一般式を求める。
\[
\begin{aligned}
a_n &= (n-1)(a_{n-1} + a_{n-2})\\
a_n -  na_{n-1} &= na_{n-2} - a_{n-1} - a_{n-2}\\
a_n -  na_{n-1}
&= (-1)^1(a_{n-1} - (n-1)a_{n-2})\\
&= (-1)^2(a_{n-2} - (n-2)a_{n-3})\\
&= (-1)^3(a_{n-3} - (n-3)a_{n-4})\\
&= (-1)^k(a_{n-k} - (n-1)a_{n-k-1})\\
&= (-1)^{n-2}(a_{n-(n-2)} - (n-1)a_{n-(n-2)-1})\\
&= (-1)^{n-2}(a_{2} - (n-1)a_{1})\\
&= (-1)^{n-2}(1 - (n-1)0) = (-1)^n\\
\frac{a_n}{n!} -  \frac{na_{n-1}}{n!}
&= \frac{(-1)^n}{n!}\\
\frac{a_n}{n!} -  \frac{a_{n-1}}{(n-1)!}
&= \frac{(-1)^n}{n!}\\
\frac{a_n}{n!}
&= \frac{a_{2-1}}{(2-1)!} + \sum_{k=2}^{n}\frac{(-1)^k}{k!}
= \sum_{k=2}^{n}\frac{(-1)^k}{k!}\\
a_n
&= n!\sum_{k=2}^{n}\frac{(-1)^k}{k!}\\
&= n!\left(\frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} + \cdots + \frac{(-1)^{n-1}}{(n-1)!} + \frac{(-1)^n}{n!}\right)\\
\end{aligned}
\]
</p>
<div style="text-align: right;">\(\Box\)</div>
<p>
具体的には
\(
a_n = (0, 1, 2, 9, 44, 265, 1854\cdots)
\)
となる。
</p>
<h2 style="page-break-before: always;">モンモール数のその他の漸化式</h2>
<p>
\[
\begin{aligned}
a_1 &= 0\\
a_n &= na_{n-1} + (-1)^n\\
\end{aligned}
\]
こちらの漸化式の方が簡単である。いくつか以下に求めてみる。
\[
\begin{aligned}
a_2 &= 2\cdot 0+(-1)^2=1\\
a_3 &= 3\cdot 1+(-1)^3=2\\
a_4 &= 4\cdot 2+(-1)^4=9\\
a_5 &= 5\cdot 9+(-1)^5=44\\
a_6 &= 6\cdot 44+(-1)^6=265\\
a_7 &= 7\cdot 265+(-1)^7=1854\\
&\vdots\\
\end{aligned}
\]
さて、この漸化式は一般式から以下のように得られる。
\[
\begin{aligned}
a_n
&= n!\sum_{k=2}^{n}\frac{(-1)^k}{k!}\\
a_{n-1}
&= (n-1)!\sum_{k=2}^{n-1}\frac{(-1)^k}{k!}\\
a_n - a_{n-1}
&= n!\sum_{k=2}^{n}\frac{(-1)^k}{k!} - (n-1)!\sum_{k=2}^{n-1}\frac{(-1)^k}{k!}\\
&= n!\frac{(-1)^{n}}{n!} + n!\sum_{k=2}^{n-1}\frac{(-1)^k}{k!} - (n-1)!\sum_{k=2}^{n-1}\frac{(-1)^k}{k!}\\
&= (-1)^{n} + n(n-1)!\sum_{k=2}^{n-1}\frac{(-1)^k}{k!} - (n-1)!\sum_{k=2}^{n-1}\frac{(-1)^k}{k!}\\
&= (-1)^{n} + (n-1)(n-1)!\sum_{k=2}^{n-1}\frac{(-1)^k}{k!}\\
&= (-1)^{n} + (n-1)a_{n-1}\\
a_n
&= (n-1)a_{n-1} + a_{n-1} + (-1)^{n}\\
&= na_{n-1} + (-1)^{n}\\
\end{aligned}
\]
</p>
<div style="text-align: right;">\(\Box\)</div>
<p>
ちなみに、全員自分のプレゼントに当たらない確率 \(p_n\) は以下のようになる。
\[
\begin{aligned}
p_1 &= 0/1 = 0\\
p_2 &= 1/2 = 0.5\\
p_3 &= 2/6 = 0.\dot{3}\\
p_4 &= 9/24 = 0.375\\
p_5 &= 44/120 = 0.3\dot{6}\\
p_6 &= 265/720 = 0.3680\dot{5}\\
p_7 &= 1854/5040 = 0.367\dot{8}5714\dot{2}\\
\end{aligned}
\]
ちなみに、これは \(n\to\infty\) で \(e^{-1} = 0.367879\cdots\) に収束する。
</p>