错位排列

数学

问题：

一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？
就是hdu2048

Solution：

采用递推的方法
记 $n$ 个数的错排的方案为 $f(n)$。
如果我们已经求出来前 $n-1$ 个 $f(n)$ ，现在考虑将第一个元素放在第 $k$ 个元素的位置上，那么会有以下两种情况

1. 第 $k$ 个元素恰好到了第一个位置，那么对于 $[2,k-1]\cup [k+1,n]$ 内的 $n-2$ 个元素可以与 $1,k$ 不相关地进行错排，即 $f(n-2)$ 种。
2. 第 $k$ 个元素不在第一个位置，可以将第一个位置看成第 $k$ 个元素的“归宿”，那么“第 $k$ 个元素不在第一个位置”就又是一个错排，这样一来，对于 $[1,k-1]\cup [k+1,n]$ 内的元素满足错排的方案为 $f(n-1)$ 种。

由于 $k\in [2,n]$，所以最后的递推式为 $f(n)=(n-1)[f(n-1)+f(n-2)]$