两种方式思考全错位排列问题。
前言
问题介绍：一个人写了 $n$ 封不同的信及相应的 $n $个不同的信封，他把这 $n$ 封信都装错了信封，问都装错信封的装法有多少种？
这种全排列中每一项都不对应的问题，就称为全错位问题（All dislocation arrangement）。
这里给出两种计算方式，求解排列种数的通项。
容斥原理
记 $A_i$ 表示第 $i$ 项选到了正确位置的数的集合。
则我们待求的全错位排列的种数 $D_n = n!-|A_1\cup A_2\cup\cdots\cup A_n|$
利用容斥原理，有
$$
|A_1\cup A_2\cup\cdots\cup A_n|=\sum_{i=1}^n|A_i|-\sum_{1\leq i < j\leq n}|A_i\cap A_j| + \dots+(-1)^{n-1}|A_1\cap A_2\cap\cdots\cap A_n|
$$
同时不难发现
$$
|A_i| = (n-1)!\ \ \ \ |A_i\cap A_j|=(n-2)!\ \ \ \cdots\ \ \ |A_1\cap A_2\cap\cdots\cap A_n| = 0!
$$
于是
$$
|A_1\cup A_2\cup\cdots\cup A_n|=C_n^1(n - 1)!-C_n^2(n-2)!+\cdots+(-1)^{n-1}C_n^n0!
$$
即
$$
|A_1\cup A_2\cup\cdots\cup A_n|=n!-\frac{n!}{2!}+\cdots+(-1)^{n-1}\frac{n!}{n!}
$$
这样就求得了 $D_n$：
$$
D_n = n!(\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!})
$$
构造递推式
显然 $D_0=0,\ D_1=1$
当 $n\geq3$ 时，不妨假设 $n$ 排在了第 $k(1\leq k < n)$ 位，考虑第 $n$ 位的情况：
- $k$ 排在第 $n$ 位，除了 $n$ 和 $k$ 以外还有 $n-2$ 个数，其错排数为$D_{n-2}$
- $k$ 不排在第 $n$ 位，那么 $k$ 与剩下 $n-2$ 个数仍构成全错位排列（$k$ 不排在第 $n$ 位，其余个数不排在各自位上），其情况数是 $D_{n-1}$
由此得到了递推关系：
$$
D_{n}=(n-1)(D_{n-1}+D_{n-2})
$$
再从这个式子出发推导 $D_n$ 通项公式，设 $D_n=n!M_n$，代入上式得
$$
M_n-M_{n-1}=-\frac{1}{n}(M_{n-1}-M_{n-2})
$$
递推下去
$$
M_n-M_{n-1}=(-\frac{1}{n})(-\frac{1}{n-1})(M_{n-2}-M_{n-3})=\cdots=(-1)^n\frac{1}{n!}
$$
对此式累加得
$$
M_n=\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}
$$
故求得
$$
D_n = n!(\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!})
$$
与前一种方法达成了统一。