错排

把“第 $i$ 个元素仍在第 $i$ 位”记为坏事件后，错排就是避开所有坏事件的排列。坏事件高度重叠，不能简单把各自概率相减；容斥逐级补回同时固定多个位置的排列，最终产生截断的 $e^{-1}$ 级数。Poisson 近似则解释了为什么随机排列中固定点个数的极限均值恰为一。

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

四个元素的错排数为

其中 $(12)(34)$ 合法，因为错排禁止不动点而不禁止二循环。若秘书把四封信放入信封且只要求前两封不回原位，后两封可固定，计数就不再是 $D_4$，而应只对指定两个坏事件做容斥。

排列公理库排列Permutation有限集合到自身的双射，或其元素的有序排列。提供总体，容斥原理公理库容斥原理Inclusion–exclusion principle · PIE通过交集的交替和修正多个有限集合并集的重复计数。给出 $D_n=n!\sum _{k=0}^n(-1{)}^k/k!$；指数生成函数把它压缩为 $e^{-x}/(1-x)$。错排还可视为完全二分图删去对角边后的完美匹配公理库匹配Matching in a graph由彼此不共享端点的边组成、表达一对一配对约束的边集合。，从而连接受限指派与 permanent 计数。