全错位排列

这里介绍全错位排列的两种解法，分别是利用递推公式和容斥原理

建议移步全错位排列 | 一剑九州寒的个人小站

递推公式

假设排列是1,2,3···n个数，$D_n$表示n个数的全错位排列的方法数。$D_1$ = 0、$D_2$ = 1

那么对于第1个位置，假设由k去占。现在就有两种情况：

1. 1和k互换了位置，k占1的位置，1占k的位置：那么此时相当于1和k位置确定，只需要讨论$D_{n-2}$的排列数。
2. 1没有占k的位置，而是占了其它的位置：那么此时相当于只确定了k的位置，需要讨论$D_{n-1}$的排列数。

但是有（n-1）个数需要讨论，所以可以得到下面的递推式：

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

然后展开递推式就可以得到错位排序的通项公式了。

容斥原理

记$N(a_1,a_2,···,a_n)$为n个数都没排错的方法数，那么对于以下情况，可以得到一些结论：
$a_1$排对，记$N(a_1) = (n-1)!$。因为a1已经排对了，那么还剩下(n-1)个位置让其它数排，所以有(n-1)!的排法。
$a_1$、$a_2$排对，记$N(a_1,a_2) = (n-2)!$
$a_1$、$a_2$、$a_3$排对，记$N(a_1,a_2,a_3) = (n-3)!$
·
·
·
$a_1$、$a_2$、$a_3$,$\dots$,$a_n$排对，记$N(a_1,a_2,a_3) = (n-n)! = 0! = 1$

推广一下，对于任意t个数，可得下面的等式：

$$
\sum N(t) = \sum N(a_{i_1},a_{i_2},\dots,a_{i_t})! = \binom{n}{t}(n-t)
$$

所以：

$$
D_n = n! - \sum N(1) + \sum N(2) + \dots + (-1)^n\sum N(n)
$$

$$
D_n = n!(1 - \frac{1}{1!} + \frac{1}{2!} + \dots + (-1)^n\frac{1}{n!})
$$