acm中的概率题问题大致是这样的：共有n个人，n个位置，每个人都对应着一个自己的位置，假设大家随机选择座位坐，全部人都做错位置的概率是多少

Question

acm 中的概率题问题大致是这样的： 共有n个人，n个位置，每个人都对应着一个自己的位置， 假设大家随机选择座位坐，全部人都做错位置的概率是多少

Answer 1

n个人都坐错位置的排列方式有F(n)种 考虑n个人都坐错位置的某种排列方式， 把最后一个人（位置为n的人）跟序号为n的人调换位置，变换之后的序列最后一个位置是坐对的， 前面n-1个位置有两种情况： 1. 都是坐错的（有F(n-1)种排列方式） 2. 有一个特例， 比如你n跟最后一个序号为m的调换了位置，而恰好之前n的位置就是m， 那么调换之后就变成m也在他正确的位置上了。 (有(n-1)F(n-2)种排列方式) 结合这两种情况就可以看出递推公式来： F(n) = (n-1) * F(n-1) + (n-1) * F(n-2) 用这个递推编程试试对不对吧 初始条件： F(1) = 0, F(2) = 1