形式陈述

$n$$n$ 个元素的错排是没有不动点的排列。错排数记为 $!n$$!n$ 或 $D_n$$D_n$。令 $A_i$$A_i$ 为“排列固定第 $i$$i$ 个元素”，容斥给出

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

它满足递推

$$ D_n=(n-1)(D_{n-1}+D_{n-2}), \qquad D_0=1,\ D_1=0, $$$$D_n=(n-1)(D_{n-1}+D_{n-2}),D_0=1,D_1=0,$$

也满足 $D_n=nD_{n-1}+(-1)^n$$D_n=n{D}_{n-1}+(-1{)}^n$。由于指数级数余项的界，

$$ D_n=\left\lfloor\frac{n!}{e}+\frac12\right\rfloor $$$$D_n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor$$

，即当 $n\ge1$$n\ge 1$ 时为 $n!/e$$n!/e$ 的最近整数。

直觉

总排列中，每个元素大约以概率 $1/n$$1/n$ 固定；固定点数在极限上近似 Poisson$(1)$$(1)$，所以完全无固定点的比例趋近 $e^{-1}$$e^{-1}$。

例子与边界

$D_3=2$$D_3=2$，对应三个元素的两个三循环；$D_4=9$$D_4=9$。约定 $D_0=1$$D_0=1$ 是因为空排列恰有一种且没有不动点，使递推和生成函数保持一致。最近整数公式不是单纯渐近式，而对全部 $n\ge1$$n\ge 1$ 精确成立。错排只禁止元素留在原位，不禁止出现二循环或其他短循环。若只要求指定子集不能固定，需对相应事件做容斥；若每个位置有一般禁配集合，则进入棋盘多项式或永久量问题。

推论与应用

错排用于帽子问题、随机排列固定点、容斥原理范例和受限匹配计数。

参考资料

• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，Problem 15.60, derangements by inclusion–exclusion。
• Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019，§8.5, applications of inclusion-exclusion。