這里介紹全錯(cuò)位排列的兩種解法炸卑，分別是利用遞推公式和容斥原理
建議移步全錯(cuò)位排列 | 一劍九州寒的個(gè)人小站
遞推公式
假設(shè)排列是1,2,3···n個(gè)數(shù)证芭，$D_n$表示n個(gè)數(shù)的全錯(cuò)位排列的方法數(shù)。$D_1$ = 0够坐、$D_2$ = 1
那么對于第1個(gè)位置寸宵，假設(shè)由k去占。現(xiàn)在就有兩種情況：
- 1和k互換了位置元咙，k占1的位置梯影，1占k的位置：那么此時(shí)相當(dāng)于1和k位置確定，只需要討論$D_{n-2}$的排列數(shù)庶香。
- 1沒有占k的位置甲棍，而是占了其它的位置：那么此時(shí)相當(dāng)于只確定了k的位置，需要討論$D_{n-1}$的排列數(shù)赶掖。
但是有（n-1）個(gè)數(shù)需要討論感猛，所以可以得到下面的遞推式：
$D_n = (n-1)(D_{n-1} + D_{n-2})$
然后展開遞推式就可以得到錯(cuò)位排序的通項(xiàng)公式了。
容斥原理
記$N(a_1,a_2,···,a_n)$為n個(gè)數(shù)都沒排錯(cuò)的方法數(shù)奢赂，那么對于以下情況陪白，可以得到一些結(jié)論：
$a_1$排對，記$N(a_1) = (n-1)!$膳灶。因?yàn)閍1已經(jīng)排對了咱士，那么還剩下(n-1)個(gè)位置讓其它數(shù)排，所以有(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個(gè)數(shù)粹排，可得下面的等式：
$$
\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!})
$$
