错排问题

问题引入

$n$ 封信从信封拆出，现将信放回，要求每封信都不能放到原来的信封里。求信放回的方案数。

Solution

设 $D_n$ 为 $n$ 封信时的方案数。小写字母代表信，大写字母代表信封。

先考虑第一封信 $a$，有 $n-1$ 个可以选择的信封。不妨设 $a$ 放入了 $B$ 信封。

再考虑信 $b$ 的放置。若 $b$ 放进 $A$ 信封，则余下 $n-2$ 封信的方案数即为 $D_{n-2}$。_

若 $B$ 放进 $A,B$ 外的信封，则可看作除 $A$ 外余下 $n-1$ 封信的错排，即 $D_{n-1}$。_

与 $A$ 的放置方案相乘，得到递推式：

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

其中手推易得 $D_1=0,D_2=1$。

生成函数求解可得通项公式：

$D_n=n!\sum^{n}_{k=0}\frac{(-1)^k}{k!}$