错排问题
问题⌗
错排问题是组合数学中的问题之一。
考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为 $ D_n $ 或 $!n$。
递归解法⌗
显然$ D_1=0，D_2=1 $。
当$ n \ge 3 $ 时，不妨设n排在了第k位，其中$ k \ne n $，也就是 $ 1 \le k \le n-1 $。那么我们现在考虑k的情况。
- 当k排在第n位时，除了n和k以外还有n-2个数，其错排数为$D_{n-2}$。
- 当k不排在第n位时，那么将第n位重新考虑成一个新的“第k位”（这步很重要！！！），这时的包括k在内的剩下n-1个数的每一种错排，都等价于只有n-1个数时的错排（只是其中的第k位会换成第n位）。其错排数为$D_{n-1}$。
所以当n排在第k位时共有$ D_{n-2}+D_{n-1} $种错排方法，又k有从1到n-1共n-1种取法，我们可以得到以下递推公式：
$$ D_{n}=(n-1)(D_{n-1}+D_{n-2}) $$
这里给出$ D_n $的前几项：0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, …