容斥：错位排列

令 { $1,2,...,n$ } 的一个错位排列，是一个排列 ${a_1,a_2,...,a_n}$ ，使得 ${a_1}\ne{1},{a_2}\ne{2},...,{a_n}\ne{n}$ 。

令 $D_n$ 表示大小为 $n$ 的错位排列的方案数。

考虑对于首位放置共有 $n-1$ 种选择，且每一种选择的方案数均相同。

令我们对于首位的放置为 $2$ ，现在考虑第 $2$ 位处放置的数予以讨论。

则此时的排列为 $2,1,a_3,a_4,...,a_n$ ，使得 ${a_3}\ne{3},{a_4}\ne{4},...,{a_n}\ne{n}$ 。

显然，这与排列为 ${a_1,a_2,...,a_{n-2}}$ ，使得 ${a_1}\ne{1},{a_2}\ne{2},...,{a_{n-2}}\ne{n-2}$ 的方案数相等。

故此时的方案数为 $D_{n-2}$ 。

则此时的排列为 $2,a_2,a_3,...,a_n$ ，使得 ${a_2}\ne{1},{a_3}\ne{3},...,{a_n}\ne{n}$ 。

显然，这于排列为 ${a_1,a_2,...,a_{n-1}}$ ，使得 ${a_1}\ne{1},{a_2}\ne{2},...,{a_{n-1}}\ne{n-1}$ 的方案数相等。

股此时的方案数为 $D_{n-1}$ 。

通过运用数学归纳法，我们易知递推式为：

D_{n} = (n-1) (D_{n-1} + D_{n-2})\tag{n $\geq$ 3}

我们也可以通过容斥原理来对此题进行分析。

首先，我们对于存在 $a_i=i$ 的排列定义为重位排列。

用符号 $T_i$ 表示存在至少 $i$ 个重位的排列方案数。

我们考虑到对于所有的方案中不合法的方案即为重位排列。

但是对于重位排列中仍会有重复计数，于是运用容斥原理易得：

D_{n} = {n}! + \sum_{i=1}^{n} (-1)^{i} T_{i}

考虑对于 $T_i$ 的计数，首先选取出 $i$ 个 $a_i$ 使得满足 $a_i=i$ ，此项选取贡献为 $\binom{n}{i}$ ；然后对于剩下的 $n-i$ 个数进行排列，此项选取贡献为 $(n-i)!$ 。于是易知：

T_i = \binom{n}{i} (n-i) !

对于 $i=0$ 即不存在重位排列的方案数进行验证发现也遵循此理，故易知：

D_n = \sum_{i=0}^{n} (-1)^{i} \binom{n}{i} (n-i) !

我们主要对上述结论进行梳理和部分性质的引导拓展。

令 $f_i = D_i - i {D_{i-1}}$ ，易知：

D_{n} = (n-1) \cdot (D_{n-1} + D_{n-2}) \tag{n $\geq$ 3}

D_{n} -n {D_{n-1}} = - ( D_{n-1} - (n-1) {D_{n-2}} )\tag{n $\geq$ 3}

f_n = -f_{n-1}

f_{n} = (-1) ^ {n-k} f_{k}

令 $k=2$ 时，手玩得 $D_1=0$ ， $D_2=1$ ，易知：

D_n - n D_{n-1} = (-1)^{n-2} (D_2 - 2 D_1)\tag{n $\geq$ 3}

D_n = n D_{n-1} + (-1)^{n-2}\tag{n $\geq$ 3}

我们发现这样的式子类似于关于阶乘的公式：

n! = (n-1)((n-1)!+(n-2)!) \tag{n $\geq$ 3}

另，联想到自然常数 $e^{-1}$ 的无穷级数展开式与关于错位排列的另一个公式如此相似：

e ^ {-1} = 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - ...

e ^ {-1} = \frac{D_n}{n!} + \sum_{i=n+1}^{\infty} (-1)^{i} \frac{1}{i!}

令事件 $E$ 为随机选出 { $1,2,...,n$ } 的一个排列是一个错位排列，则易知其概率 $Prob(E)= \frac{D_n}{n!}$ 。

感谢您的支持，我会继续努力的!