错排问题.md

错排问题

给出$n$个元素标号为$1$到$n$，它们共有$n!$种排列方式，我们将其中每一个元素都不在其原来的位置上的排列方式叫作该排列的一个错排.

错排问题就是指，给出一个排列，它有多少个错排？

错排的递推关系这样求：

令$D_n$表示$n$个元素的错排数，接下来分两步走：

1. 考虑第$n$个元素，假设将其放到位置$k$，有$n - 1$种放法.

2. 考虑第$k$个元素，如果我们将其放到位置$n$，那么只需要令剩下的$n - 2$个元素做错排即可，有$D_{n - 2}$种；如果第$k$个元素不放到位置$n$，那么第$k$个元素有$n - 2$个位置可以选择（位置$n$和位置$k$不能选），其余的元素也有$n - 2$个位置可以选（位置$k$和其原来的位置不能选），这相当于$n - 1$个元素的错排问题，有$D_{n - 1}$种.

综上所述，错排问题的递推式是：

$$ D_n = (n - 1) * (D_{n - 2} + D_{n - 1}) $$

特别的，有：$D_1 = 0,D_2 = 1$.