错排问题
https://www.luogu.com.cn/problem/P1595
https://www.luogu.com.cn/problem/P4071
错排问题，这个问题的背景可能有多种表述方式，将其形式化，可表为：将 1 至 n 这 n 个数字排列，使得每个数字不出现在其所在序号的位置上，问所有可能的排列数。
先分步，考虑序列 \(1,2,\cdots,n\)。先考虑最后一个位置 \(n\) 任选前面 \(n-1\) 个数放，此时前面有一个位置空了。然后分类：
- \(n\) 放在该空的位置，则目前已经有两个元素确定了位置，即剩下的构成了一个 \(D_{n-2}\) 的子问题。
- \(n\) 不放在该空的位置，则此时除了最后一位已经确定，其他 \(n-1\) 个数都不能放在自己的位置上（\(n\) 不能放在这个空的位置上），即构成了一个 \(D_{n-1}\) 的子问题。
综上，可以得到递推公式：
\[
D_{n}=(n−1)(D_{n−1}+D_{n−2}),n≥3
\]
初始条件为 \(D(1)=0,D(2)=1\) .