ダメなボーイから学ぶ--完全順列、モンモール数(Montmort number)

ホテルのボーイが $n$ 人の客からそれぞれ帽子をあずかったが，誰の帽子であるかの記録をなくしてしまったため，でたらめに帽子を返すこととした．この状況で自分の帽子を正しく返してもらえる客の数を $X_n$ とし， $X_n=k$ となる確率を $p_n(k)$ と表す．

考えやすくするために、客と帽子にそれぞれ番号を $1,2,\ldots,n$ と付ける。

まず、 $X_n=0$ となる場合の数 $d_n$ を考える。（ちなみに、この $d_n$ をモンモール数と呼ぶ。）
1番目の人に注目するこの人の受け取る帽子は自分の帽子である1以外の帽子で、
$n-1$ 通り、この人の受け取った帽子の番号を $i$ とする。このとき、
$i$ 番目の人が受け取った帽子の番号で場合分けを行う。
$i$ 番目の人が受け取った帽子の番号が1のときは、 $n-2$ のときの場合の数 $d_{n-2}$ 、
$i$ 番目の人が受け取った帽子の番号が1でないときは、 $i$ 番目の人は1の帽子を受け取れないので、 $n-1$ のときの場合の数 $d_{n-1}$ を考えればよい。

よって、以下が成立する。

$d_n = (n-1)\left\{d_{n-1}+d_{n-2}\right\}$

これを変形して

$d_n -n d_{n-1} = -\left\{d_{n-1} - (n-1)d_{n-2}\right\}$

ここで、 $d_1 = 0,d_2 =1$ であるから、

$d_n - n d_{n-1} = (-1)^n$

両辺を $n!$ で割って

$\frac{d_n}{n!} - \frac{d_{n-1}}{(n-1)!} = \frac{(-1)^n}{n!}$

和を考えて

$\sum_{k=2}^n \left\{ \frac{d_k}{k!} - \frac{d_{k-1}}{(k-1)!} \right\} = \sum_{k=2}^n \frac{(-1)^k}{k!}$

$\frac{d_n}{n!} - \frac{d_1}{1!} = \sum_{k=2}^n \frac{(-1)^k}{k!}$

$d_n = n!\left$ \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \cdots +\frac{(-1)^n}{n!}\right$$

よって、確率 $p_n(k)$ は以下のように表現できる。

$p_n(k) = \frac{ {n \choose k} d_{n-k}} {n!}$

次に、期待値、分散を考えたい。ここで、

$kp_n(k) = k \frac{ { n \choose k} d_{n-k}}{ {n!}} = n \frac{{n-1 \choose k-1}d_{n-k}}{n!}$
$kp_n(k) = \frac{{n-1\choose k-1}d_{n-k}}{(n-1)!} = p_{n-1}(k)$

であるから、

$E[X_n] = \sum_{k=0}^nkp_n(k) = \sum_{k=0}^np_{n-1}(k) = 1$
$E[X_n(X_n-1)] = \sum_{k=0}^nk(k-1)p_n(k) = \sum_{k=0}^n(k-1)p_{n-1}(k) = \sum_{k=0}^np_{n-2}(k) = 1$

$E[(X_n-\bar X_n)^2] = E[X_n^2] - E[X_n]^2 = E[X_n(X_n-1)] + E[X_n] - E[X_n]^2 = 1$

また、 $p_n(k)$ の形から分かることであるが、

$p_n(k) = \frac {1}{k!}p_{n-k}(0) \left$=\frac{d_{n-k}}{(n-k)!k!}\right$$
$\lim_{n \to \infty} p_n(0) = e^{-1}$
が成立することが分かる。
[追記]
期待値、分散は期待値の線形性を利用すればもっと簡単に求められることに気がついた、いまさら。