本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-11 19:08:04

很多数数题听是听懂了，写也写完了，但是自己想是绝对想不出来的。

所以整理一下

错排

考虑 $f(i)$ 表示 $1$ 到 $n$ 的排列中错排的数量，那么对于第 $i$ 个数，我们要把它插入到前面 $1$ 到 $i - 1$ 个数中。

可以把它放到 $f(i - 1)$ 中的里，这是 $(i - 1) f(i - 1)$ 种方案；

也可以把它放到一个缺一错排里，也就是只有一个 $i$ 满足 $a_i = i$，这个的方案数是 $(i - 1)f(i - 2)$。

最终的转移就是 $f(i) = (i - 1)(f(i - 1) + f(i - 2))$。