错排问题

错排问题是组合数学中的问题之一。考虑一个有${\displaystyle n}$），并独立解决了这个问题。

对于情况较少的排列，可以使用枚举法。

对于排列数较多的情况，难以采用枚举法。这时可以用递归思想推导错排数的递回关系式。

显然D₁=0，D₂=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑k的情况。

所以当n排在第k位时共有D_n-2+D_n-1种错排方法，又k有从1到n-1共n-1种取法，我们可以得到：

在上面我们得到

D_n=(n-1)(D_n-1+D_n-2)

从这个公式中我们可以推出D_n的通项公式，方法如下：

为书写方便，记D_n = n!M_n，则M₁ = 0, M₂ = ${\displaystyle \frac{1}{2}}$ 的最大整数）。

这个简化公式可以由之前的错排公式推导出来。事实上，考虑指数函数在 0 处的泰勒展开：

所以，${\displaystyle \frac{n!}{e}-<!--\; -\; -->D_n=n!R_n}$ 是泰勒展开的余项， 是介于 0 和 1 之间的某个实数。 的绝对值上限为

当 n≥2 时，${\displaystyle \frac{1}{(n+1)}}$ 严格小于 0.5，所以 ${\displaystyle D_n=n!\left(\frac{1}{2!}-<!--\; -\; -->\frac{1}{3!}+...+(-<!--\; -\; -->1{)}^n\frac{1}{n!}\right)}$ 是最接近 ${\displaystyle \frac{n!}{e}}$ 的整数，可以写成