什么是错排公式？
求有多少序列 $A$ 满足下列条件：
- $1\sim N$ 这 $N$ 个数在序列中均出现一次且仅出现一次.
- 对于任意一个位置 $i$ ，满足 $A_i\ne i$.
太长不看版： 设 $d(n)$ 为长度为 $n$ 的序列错排数量，则有
\[d(n)=\left\{ \begin{aligned} &1&(n=0)\\ &0&(n=1)\\ &(n-1)\times (d(n-1)+d(n-2))&(n\ge1) \end{aligned} \right.\]证明
我们首先来考虑，首先将 $m$ 放置在 $k$ 位置上，显然 $k$ 的取值有 $(n-1)$ 个.
接下来考虑 $k$ 放置的位置：
- $k$ 放置在 $m$ 处
则接下来要对剩下的 $n-2$ 个数进行错排，即 $d(n-2)$ 种情况， 此时第一种情况的个数为 $(n-1)\times d(n-2)$. - $k$ 放置在 $i\ (i\ne m)$ 处
那么显然 $i$ 不能等于 $k$ ， 所以 $k$ 也是进行错误排序，即对剩余的 $(n-1)$ 个数进行错排，有 $d(n-1)$ 种情况，则第二种情况的个数为 $(n-1)\times d(n-1)$.
综上所述，
\[\begin{aligned} d(n)&=(n-1)\times d(n-2)+(n-1)\times d(n-1)\\ &=(n-1)\times (d(n-2)+d(n-1)) \end{aligned}\]考虑边界情况，当 $n=0$ 时，即空序列，只有一种情况，即 $d(0)=1$.
当 $n=1$ 时， 唯一的这一个元素只能放在这个位置，所以没有办法进行错排，即 $d(1)=0$.
练习： P4071
错排公式还有通项公式和简化公式，不过我太菜了就没看，如果你想看就去百度吧
