会抽到自己的那张吗？
周末和一个朋友聊天，说是要去阿里巴巴报道了。听说阿里巴巴的入职培训中有个有趣的游戏。所有学员都要在一张纸条上写下自己的一个短期愿望，投进纸箱中。然后大家各抽一张。抽到别人的愿望后，要想办法帮那个人实现愿望，且不能告诉对方是你抽到了他的愿望。
我突然想，如果抽到自己的愿望怎么办？:D
抽到自己的写的那张的概率是 1/n （n 为人数），这个概率和你先抽后抽无关。当人数很多时，概率自然是很小的，但是整个集体中，至少有一个人抽到自己那张的概率看起来却不小。到底是多少呢？我饶有兴趣的算了一下。
简化一下题目，其实就是把 1-n 个自然数，排成一个数列里，至少有一个数字 i 刚好排到第 i 个位置的概率。
n 个数字的全排列有 n! 种，我们只需要计算出，没有一个数字排在它所在次序位置的排列数。
先定义一个函数 f(n) ，表示把 n-1 个数字排到 n 个位置上，每个数字都不在自己位置上的排列数。
可知 f(2)=1 （把 1 排在两个位置上 ， X 1） f(3)=3 （把 1 2 排在三个位置上， X 1 2 ，2 1 X ，2 X 1） ...
再定义一个函数 g(n) ，表示把 n 个数字，排到 n 个位置上，每个数字都不在自己位置的排列数。
可知 g(n+1) = n * f(n) ，这么理解， g(3)=g(1+2) 也就是排 3 个数字时，先把 2 或 3 排到第一个位置。剩下的两个数字中，1 一定不会在自己位置了。另一个数字排到 2 个空位不在自己位置的排列数就是 f(2)
又可以推导出： f(n+1) = g (n) + n * f(n)
这样理解： f(n+1) 可以分成两种情况，一种是空出那个多余的位置，剩下 n 个数字都不在自己位置的排列数即 g(n) ；另一种情况是，从 n 个数字里挑出一个放在多余的位置上，剩下 n-1 个数字去排 n 个空位，这种情况总数为 n 倍的 f(n) 。
两式联立得到 g(n+1) = n * ( g(n-1) + g (n) )
这样，我们就得到了一个递推式。由于已知 g(3) = 2 * f(2) = 2 ；g(4) = 3 * f(3) = 9 ，所以写个程序很容易求出后续数值。
然后来算概率，n 个数时，概率 h(n) = g(n)/n! 。
我用程序计算了前 100 项，发现从第 8 项开始，概率就几乎不变了，稳定在 0.3679 左右。这引起了我的好奇心，然后重新用笔来推导上面的公式。
h(n+1) * (n+1)! = n * ( h(n-1) * (n-1)! + h(n) * n! )
可以得到
和 ( h(n+1) - h (n) ) *(n+1) = h(n-1) - h (n)
我们可以看到， h(n) 这个数列，相邻两项的差是 1/2! , -1/3! , +1/4! ....
因为我们已知，h(2) = g(2) / 2! = 1/2 ， h(3) = g(3) / 3! = 1/3
可以得到 h(n) = 1 -1 + 1/2! - 1/3! + 1/4! - 1/5! .... 1/n!
这看起来是什么？哈，正好是 1/e 的麦克劳林展开式 :D 所以 h(n) 当 n 增大时，它会收敛到 1/e = 0.367879 。且收敛速度极快 :D
结论：当 n 较大(n>5) 时，没有一个人抽到自己那张纸条的概率是 1/e = 36.8% 左右。还句话说，至少有一个人抽到自己写的那个愿望的可能性有 63.2% 左右，这种事情还是很容易发生的，无论人多还是人少。这个概率随 n 变化的量很小。
哈，怎么又绕到欧拉数 e上面去了，数学还真是神奇啊。
Comments
((n-1)/n)^n这个答案不对，这应该是每个人抽完之后再放回去再抽的答案。楼主的意思应该是抽完之后不放回的。虽然两个答案的极限是一致的，但是收敛速度不一样，从n=2开始，两个结果就不等了。
Posted by: 周星星 | (26) March 13, 2016 09:09 AM
如果小组之间互换了下纸条呢？
Posted by: Anonymous | (25) September 11, 2012 12:25 PM
还是楼下的方法简单，容易理解。
这个方法的理论基础是概率论中的一个定理：抽签抽中的概率和抽签顺序无关。
Posted by: 海洋 | (24) April 15, 2012 06:25 PM
很简单的联合概率问题，为什么搞的那么复杂呢？
假设有n个人
第1个人抽不到自己的概率是(n-1)/n
第1和第2个人都抽不到自己的概率是(n-1)/n的2次方
所有n个人都抽不到自己的概率是 (n-1)/n的n次方
验算，(9999/10000)的10000次方，结果是0.36786104，和楼主给出极限一致
Posted by: test | (23) April 23, 2010 03:52 PM
我只想知道 100! 你是怎么用程序算的,我知道是一个158位的大数,能不能给我程序.最好是C程序呀.
Email: 282015535@qq.com
Posted by: hanzi | (22) November 19, 2008 10:21 PM
楼主想必是一个技术牛人,很喜欢你的blog,虽然我只学了一点C的皮毛,但是还是很认真的看了你的文章
Posted by: 34 | (21) June 13, 2008 09:16 AM
就是这个题的后面还有一问，我也答不出，这N个人编号为1,2,...,N放至一个数组中，哪些没有拿到自己的号的人，比如说原来是123，变成231了，这个与数组的序号就构成一个环，1->2,2->3,3->1,就是这个环，问的是这样的环的平均长度是多少？
Posted by: Anonymous | (20) June 7, 2008 03:53 PM
云风师兄,好想和你交个朋友啊!我最佩服的不是你的技术水平多高,也不是你多么专业执着.而是你对于金钱的淡泊.我想我的水平也是不错,做游戏也是挺认真的,当然,比起你来,还是有差距的,哈哈.可是有一点我似乎很难做到:我没有你那么一点也不在乎钱.可能是我生来俗气吧,或许是我现在很需要钱吧.我挺希望自已能和你一样淡泊名利
Posted by: 亮 | (19) May 31, 2008 09:19 PM
如果有N个人抽中的概率是多少？怎么算？
Posted by: 笑笑和尚 | (18) May 29, 2008 05:17 PM
我觉得163是中国互联网最有技术实力的一家公司，干什么说到底还是技术是根本。
Posted by: emil | (17) May 28, 2008 11:39 PM
这个和说曹操,曹操 jiu dao,yiyang,hehe,you can bc it chance?
Posted by: Anonymous | (16) May 28, 2008 09:39 PM
哈哈，大家用递归解的比较多。
我说一个不用递归的解法吧。
设A(i）[i＝1，。。。N] 表示第i个人抽到自己的愿望。
很明显， P[A（i）] = 1/n.
由条件概率有： P[A(i)A(j)] = P[A(i)]P[A(j)|A(i)] = 1/n(n-1) （1<＝i<j）
以此类推： P[A(i)A(J).....A(n)] ＝ 1/n(n-1)(n-2).... = 1/n!
至少有一个人抽到自己的那张是：U[A(1)+ A(2).... + A(ｎ)] 由全概率公式有：P(U) = C(n,1)* 1/n - C(n,2)* 1/n(n-1) + ....... 1/n! = 1-1/2!+1/3!.....1/n!
当 n－> 无穷大时，该式收敛于1－1/e
:-)
叹造物之精妙，赞数学之神奇！
Posted by: 红色警戒 | (15) May 28, 2008 02:38 PM
作为用程序解决生活问题，这是非常好的教材~
Posted by: chinainvent | (14) May 28, 2008 01:47 PM
真是数学天才，我只能说一个字：囧
Posted by: govo | (13) May 27, 2008 01:24 AM
只能说明你很无聊
Posted by: 吴明 | (12) May 26, 2008 11:48 PM
这个是组合数学中一个比较经典的问题，叫更列或者错位排列，就是把n封信放进n个信封并且都放错的方式数，knuth在taocp里讨论过，随便拿一本组合数学的书也都有讲，用递归解比较容易懂，但是得到的递推公式求通项时需要点技巧，最经典的一个解法是用容斥原理。
好像有一年高考题出过一次计算5的derangement，结果随后几届的高中小孩都会玩这个了，呵呵，包括我~~~~
不过风哥能直接推出来也不容易~~~~~~~~
Posted by: dongxie | (11) May 26, 2008 03:03 PM
g(n+1) = n * f(n) 我没有理解这步是怎么来的，但是你让我看到了数学归纳法的威力
Posted by: ywchen2000 | (10) May 26, 2008 01:52 PM
我的愿望是把英语学好一点!
Posted by: 开心 | (9) May 26, 2008 11:34 AM
下界勘误：省略号后的n应为(n+1)...
Posted by: Kusk | (8) May 26, 2008 10:55 AM
有(n+1)个数时，假设数字“1”选择了位置x，则剩下n个数的放置方法分两种情况：
1）若数字x选择了位置1，则剩下2,3,...,x-1,x+1,...,n共(n-1)个数，且每个数均有自己对应不能摆的位置，故此情况共有g(n-1)种摆法；
2）若数字x不选择位置1，则可将数字x视为新的数字"假1"，相当于"假1",2,3,...,x-1, x+1,...n共n个数字，且每个数字均有自己对应不能摆的位置（"假1"不能摆在位置1），故此情况共有g(n)种摆法。
综1）及2），数字1选择位置x之后共有(g(n-1)+g(n))种摆法，由于位置x有2,3,...,n种选择，故有g(n)=n(g(n-1)+g(n)).
Posted by: Kusk | (7) May 26, 2008 10:12 AM
= =
我的第一反应也是：如果抽到自己的怎么办？
= =
Posted by: kevinlynx | (6) May 26, 2008 10:07 AM
= =
我的第一反应也是：如果抽到自己的怎么办？
= =
Posted by: kevinlynx | (5) May 26, 2008 10:07 AM
题目的原型是伯努利装错信封问题，还的确是欧拉解决的，欧拉威武~
Posted by: Dingding | (4) May 26, 2008 09:06 AM
真是相当有意思!
Posted by: srdrm![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (3)
May 26, 2008 08:32 AM
一个365人的集体，有与自己同天过生日的人的概率是不是1/365？（排列组合全忘光了）想想不是。但是至少有人同天过生日的概率就很高，据说20多人的团队里概率就超过一半，50多人中几乎肯定有同天过生日的。
有人觉得枯燥深奥，有人觉得生动有趣的概率问题。
Posted by: 老黄牛 | (2) May 26, 2008 08:05 AM
抢个沙发。这个是组合数学中的错排问题。上周刚好在群里让学数学的策划mm做了一下这个题目，结果一个程序dd推出了这个递推公式，呵呵
Posted by: along | (1) May 26, 2008 12:20 AM