某班有n个士兵,每人各有一支枪,这些枪外形完全一样,在一次夜间紧急集合中,若每人随机的取走一支枪,问至少有一个人拿到自己的枪的概率是多少?1/1!-1/2!+1/3!-1/4!+1/5!-1/6!+……+1/n!,

Question

某班有n个士兵,每人各有一支枪,这些枪外形完全一样,在一次夜间紧急集合中,若每人随机的取走一支枪,问至少有一个人拿到自己的枪的概率是多少?
1/1!-1/2!+1/3!-1/4!+1/5!-1/6!+……+1/n!,

Answer 1

这是一个经典问题, 常被称为装错信封问题.
比较稳妥的方法是用递推.
设n个人全部拿错的情况数为a(n).
易见a(1) = 0, a(2) = 1.
n个人全部拿错的情况可分为两类:
① 第n个人所拿的枪的主人刚好拿到第n把枪.
所拿到的枪的主人有n-1种可能.
余下的n-2个人则有a(n-2)种全拿错的可能.
此类情况的总数为(n-1)·a(n-2).
② 第n个人所拿的枪的主人没有拿到第n把枪.
第n个人拿到的是第k把枪, 第n把枪则由第j个人拿到, 而j ≠ k.
k有n-1种可能, 以下分析当k确定后的情况数.
考虑一个操作: 将第k把枪交给第j个人, 同时去掉第n个人和第n把枪.
这个操作建立了k确定后的情况与n-1个人全拿错的情况的一一对应.
(存在逆操作: 加入第n个人和第n把枪, 用第n把枪与第k把枪交换, 将第k把枪交给第n个人).
于是此类情况的总数为(n-1)·a(n-1).
因此a(n) = (n-1)·a(n-1)+(n-1)·a(n-2).
本题要求至少有1人拿对的概率: p(n) = 1-a(n)/n!.
即有a(n) = n!-n!·p(n).
代入递推式得n!-n!·p(n) = (n-1)·(n-1)!-(n-1)·(n-1)!·p(n-1)+(n-1)!-(n-1)!·p(n-2).
整理得n·p(n) = (n-1)·p(n-1)+p(n-2), 即有p(n)-p(n-1) = -(p(n-1)-p(n-2))/n.
又由p(1) = 1-a(1)/1! = 1, p(2) = 1-a(2)/2! = 1/2, 有p(2)-p(1) = -1/2.
可得p(n)-p(n-1) = (-1)^(n+1)/n!.
于是p(n) = 1/1!-1/2!+1/3!-...+(-1)^(n+1)/n!.