错位排列：满足 \(p_{i}\ne i\) 的排列
错排数：\(D_{n}\) 表示 \(n\) 的错位排列数
容斥
考虑算补集：\(n\) 个元素不都错排的方案数为
\[\sum_{i=1}^{n}(-1)^{i-1}{n\choose i}(n-i)!=n!\sum_{i=1}^{n}\frac{(-1)^{i-1}}{i!} \]\[D_{n}=n!\sum_{i=0}^{n}\frac{(-1)^{i}}{i!} \]递推
考虑 \(n\) 所在的位置 \(i\)：
- \(p_{n}=i\)：交换 \(p_{i},p_{n}\) 后剩下 \(n-2\) 个元素构成错排
- \(p_{n}\ne i\)：交换 \(p_{i},p_{n}\) 后 \(1\sim n-1\) 个元素构成错排
递推式：\(D_{n}=(n-1)(D_{n-2}+D_{n-1})\)
标签：排列,frac,sum,ne,错位,错排 From： https://www.cnblogs.com/ft61/p/17777910.html