错排公式

错排公式

错排问题，考虑$n$个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。记作$n$个元素的错排数为$D(n)$。

递推公式：

• 选择书的编号为m，剩下n - 1个位置，假设选择k

• k放入m的位置 则转化为$D(n - 2)$的错排方案数

• 第m本书在位置k不动，此时k不能放在第m个位置，其他n - 2本书也不在自己原本的位置，等价于求$n - 1$个数的错排

$$
D(n) = (n - 1) *[D(n- 1) + D(n - 2)]
$$

https://cses.fi/problemset/task/1717