错排问题

【问题】 一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，都装错信封的装法有多少种（历史有名的“装错信封问题”）

【切入点】类似于超几何分布+动态规划的思想：

第n个位置上新来一封信：

这封信不匹配第n个位置，这封信有n-1个选择，剩下的n-1个位置有F[n-1]个选择。共(n-1)*F[n-1]种方法

这封信匹配第n个位置，想让他错误，要和之前n-1个位置里面的一封信换换位置。换位置的选择n-1个，换完位置后，剩下的错排F[n-2]个。共(n-1)*F[n-2]中方法。

F[n] = (n-1)*F[n-1] + (n-1)*F[n-2]。