O(1) 的小樂

這個是算法導論習題5.2-4

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

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

然后對于n個人中i個人匹配正確這個事件的數目是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)!}

可以證明這個等式等于1
所以答案是1