ダメなボーイから学ぶ–完全順列、モンモール数(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}

が成立することが分かる。

[追記]

期待値、分散は期待値の線形性を利用すればもっと簡単に求められることに気がついた、いまさら。

More Reading
Newer// 筋肉痛
Older// 帰還-合宿