错排问题(derangement)
问题来自于 云风的 BLOG: 会抽到自己的那张吗？，我这里写写自己的做法。评论里面说这是 错排问题，也叫做伯努利-欧拉装错信封问题。
我觉得云风的公式推导有点复杂，我想简化一下。推导过程，需要非常小心，确保概念完全正确。 我之前做过一个错误的推导，把概率计算成为((n-1) / n) ^ n.回来起来应该是把一些概念混淆了，所以导致错误的结果。
定义两个函数：
- f(n+1) = 1..(n+1)个人抽取1..(n+1)个数字，并且完全错配的数量
- g(n+1) = 1..n个人中抽取1..(n+1)个数字，并且完全错配的数量
我们先从g(n+1)推导，两种情况：
- 1..n个人抽取了(n+1)th这个数字，那么结果就是剩余的n-1个人只需要抽取1..n个数字.
- 所有人都没有抽取n+1th这个数字，那么就是n个人抽取1..n个数字.
情况1的数值是 n * g(n), 情况2的数值是f(n). 所以g(n+1) = n * g(n) + f(n) [A].
然后从f(n+1)推导，两种情况：
- 1..n个人抽取了1..(n+1)个数字，并且完全错配。
- 但是需要排除1..n个人抽取了1..n个数字，那么(n+1)th这个人只能抽取(n+1)th数字，这就没有错配，需要排除。
情况1的数值是 g(n+1), 情况2的数值是f(n). 所以f(n+1) = g(n+1) - f(n) [B].
化简上我们尽量保留f(n+1)，去掉g(n+1). 我们把[B]中的定义带入[A]中
- g(n+1) = f(n+1) + f(n)
- g(n) = f(n) + f(n-1)
- f(n+1) + f(n) = n * (f(n) + f(n-1)) + f(n)
- f(n+1) = n * (f(n) + f(n-1))
f(n)只是具体的数量，映射到概率上则是p(n) = f(n) / n!, 化简一下可以得到 `p(n) - p(n-1) = (p(n-2) - p(n-1)) / n`.
云风这里确实厉害，把p(n)映射到了麦克劳林公式上. n接近无穷大是, p(n) 收敛到 1/e.