定义：\(\forall i\in[1,n],p_i\neq i\) 的长度为 \(n\) 的排列数。
一开始看到的时候还想用容斥推：\(\sum\limits_{i=0}^n\binom{n}{i}(-1)^i(n-i)!\)，结果发现太垃圾了。
递推法
设 \(D(n)\) 表示长度为 \(n\) 的错排数，考虑枚举数 \(n\) 放在了第 \(i\) 个位置（\(1\leq i\leq n-1\)），然后此时数 \(i\) 已经不在自己的位置了，考虑它放在哪：
- 若数 \(i\) 放在了第 \(n\) 个位置，那么相当于剩下的 \(n-2\) 个数的错排问题。
- 若数 \(i\) 不放在第 \(n\) 个位置，此时看成数 \(i\) 也有一个错排限制，于是相当于 \(n-1\) 个数的错排问题。
于是有递推式：\(D(n)=(n-1)\big(D(n-1)+D(n-2)\big)\)。
生成函数法
排列可以看成若干个置换环组成，错排可以看成若干个大小不为 \(1\) 的置换环组成。
可知大小为 \(n\) 的置换环的数量为 \((n-1)!\)，那么大小为 \(n(n\geq 2)\) 的置换环数量的 EGF 为：
\[F(x)=\sum_{n\geq 2}\dfrac{(n-1)!}{n!}x^n=\sum_{n\geq 2}\dfrac{x^n}{n}=\left(\int \sum_{n\geq 0}x^{n}\right)-x=\left(\int \dfrac{1}{1-x}\right)-x=-\ln(1-x)-x \]于是错排数的指数生成函数即为：
\[\exp F(x)=\exp(-\ln(1-x)-x) \] 标签：geq,排数,dfrac,sum,计数,错排,置换 From： https://www.cnblogs.com/ez-lcw/p/16843067.html