数数

· · 个人记录

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

所以整理一下

错排

考虑 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))。