O(1) 的小樂

這個(gè)是算法導(dǎo)論習(xí)題5.2-4

  n個(gè)顧客在進(jìn)酒店之前，都會把自己的帽子給前臺服務(wù)員保管。每個(gè)顧客在離開時(shí)，前臺服務(wù)員又會隨機(jī)地挑選一個(gè)帽子給他。問：最終，能拿到自己帽子的顧客們期望數(shù)是多少

首先從簡單情況入手，對于n=2 n=3 很容易求出 結(jié)果res=1；
對于n>=4,我們嚴(yán)格的用概率方法來推導(dǎo)一下！
首先定義P(n)為伯努利放錯(cuò)信的問題的答案。
P_n=n!\sum_{i=2}^{n}\frac{(-1)^i}{i!}

然后對于n個(gè)人中i個(gè)人匹配正確這個(gè)事件的數(shù)目是C(n,i)P(i)  
總共有n！中事件，2^n種情況，（可以把人看成是10串，拿到自己帽子的為1）
所以 答案就是
（n-i）*C(n,i)P(i) /n!求和
整理一下是 
\sum_{i=2}^{n-1}\frac{n-i}{(n-i)!}\sum_{j=2}^{i}\frac{(-1)^j}{j!}+\frac{1}{(n-1)!}

可以證明這個(gè)等式等于1
所以答案是1