错位排列数

定义

对于 $1 \sim n$ 的排列 $P$ ，如果满足 $P_i \neq i$，则称 $P$ 是 $n$ 错位排列。

递推式的推理

递推式：$D_n = ( n-1) * (D_{n-1} + D_{n-2})$
$D_n$ 表示的就是 $1 \sim n$ 的错位排列的数量。

我考虑这样一个问题，我们有 $n$ 封不同的信，编号分别为 $1,2,3, \dots ,n$ ，把这些信放进 $n$ 个不同的邮箱当中，邮箱的编号为 $1,2,3, \dots ,n$，并且保证信的编号和邮箱的编号不一样。

当我们就要放第 $n$ 个信时，我们可以分为以下两种情况 。

• 前面 $n-1$ 封信全部放错，可以通过让我们要放的第 $n$ 封信与前面的 $n-1$ 封信的其中一封信进行交换一次即可，表示出来就是 $D_{n-1} * (n-1)$
• 前面 $n-1$ 封信有一个没有放错，其他全部放错，可以通过让我们要放的第 $n$ 封信与前面的 $n-1$ 封信的中的那封没有放错的信进行交换即可，表示出来就是 $D_{n-2} * (n-1)$。 ($n-1$ 是枚举那封没有放错的信 )

所以: $D_n = ( n-1) * (D_{n-1} + D_{n-2})$

参考 OIwiki