错排问题

约 371 个字 预计阅读时间 1 分钟

我们把错位排列问题具体化，考虑这样一个问题：

$n$ 封不同的信，编号分别是 $1,2,3,4,5$，现在要把这五封信放在编号 $1,2,3,4,5$ 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？

假设我们考虑到第 $n$ 个信封，初始时我们暂时把第 $n$ 封信放在第 $n$ 个信封中，然后考虑两种情况的递推：

• 前面 $n-1$ 个信封全部错位；
• 前面 $n-1$ 个信封有一个没有错位其余全部错位。

对于第一种情况，前面 $n-1$ 个信封全部错位：因为前面 $n-1$ 个已经全部错位了，所以第 $n$ 封只需要与前面任一一个位置交换即可，总共有 $f(n-1)\times (n-1)$ 种情况。

对于第二种情况，前面 $n-1$ 个信封有一个没有错位其余全部错位：考虑这种情况的目的在于，若 $n-1$ 个信封中如果有一个没错位，那么我们把那个没错位的与 $n$ 交换，即可得到一个全错位排列情况。没错位的可以有 $n-1$ 个位置

其他情况，我们不可能通过一次操作来把它变成一个长度为 $n$ 的错排。

于是可得错位排列的递推式为 $f_n=(n-1)(f_{n-1}+f_{n-2})$。

错位排列数列的前几项为 $0,1,2,9$。