6个人拿6把枪，至少1个人拿到自己的枪的概率是多少？
解题思路：
要解答上面这道题，也可以先解答这道题：
6个人拿枪，没有人拿到自己枪的概率是多少？
假设第二题的答案是X，那么原题的答案就是 1-X
ok，对于第二题。我们的解法是采用数学归纳法。
定义
n个人拿n把枪，如果没有人拿到自己的枪的概率是G（n）,那么，
- G(0) = 1。一定没有人能拿到自己的枪
- G(1) = 0。1个人无论如何都是拿到自己的枪
- G(2) = 二分之一。这个也很容易，只有2种情况，要么你拿了我的，我拿了你的，要么都拿自己的枪。
一般的，如果已经知道了G(n),如何推出G(n+1)呢？
1把枪也没有拿对的概率+只有1把枪拿对的概率+只有2把枪拿对的概率+只有3把枪的概率+只有4把枪的概率+…+全部都拿到自己枪的概率 = 1
G(n+1)+1/(1!)G(n)+1/(2!)G(n-1)+1/(3!)G(n-2)+…+1/n!G(1)+1/(n+1)!*G(0)=1
可以推导出
- G(3)= 1/3
- G(4)= 9/24
- G(5)= 44/120 = 11/30
- G(6)= 1- 455/720
所以本题答案为 455/720 = 91/144
通解
那么问题来了，如果G(n)要把所有小于n之前的结果都算出来，那么如果G（25）等于多少之类的问题就吃力了。
如何才能求出G(n)的通解呢？