错排问题

给定 \(n\) 个信封 \(n\) 封信，信封和信的配对形成双射

求有多少种将信乱放到信封中的方案使得所有双射无一被满足

Solution

尝试使用容斥原理刻画这个问题的计算模型：枚举有几个元素是放到合法位置上的，表达式如下：

\[\sum_{i=0}^n(-1)^k\binom ni (n-i)! \]

验证其正确性大可考察每个不合法方案的计算次数，本文不再赘述

设 \(D_n\) 表示上述问题在信封个数为 \(n\) 时的答案，尝试对 \(D\) 数列进行进一步探究

将上面的式子展开不难得到

\[D_n=n!\sum_{i=0}^{n}(-1)^i\frac1{i!}\\\lim\limits_{n\to \infty}D_n=\frac{n!}{e} \]

但是这个式子看起来并不能给予我们正整数形式的答案，尝试省略一些信息：在 \(n\) 有限时按照上面的容斥原式只保留 \(e^{x}(x=-1)\) 展开式中 \(i\le n\) 的部分

保留泰勒展开式中的 \(\rm Lagrange\) 余项可以得到形如下式的结果

\[D_n=n!\left(\frac{1}e-(-1)^{n+1}\frac{e^{\varepsilon}}{(n+1)!}\right) \]

根据余项的定义此时有 \(\varepsilon\ \in (-1,0)\) 所以后面的部分满足

\[|(-1)^{n+1}\frac{n!e^{\varepsilon}}{(n+1)!}|=\frac{e^{\varepsilon}}{n+1}\le \frac 1{n+1}\le \frac 12 \]

这就证明了 \(|\frac{n!}e-D_n|\le \frac 12\) ，而绝对值符号内的减数和被减数的大小是不易界定的（取决于 \(n\) 的奇偶性）

那么使用四舍五入来计算即可