错排

错排要求每个元素都离开原位置。先固定任意 $k$ 个位置，有 $(n-k)!$ 种办法排列其余元素；选这 $k$ 个位置又有 $(\genfrac{}{}{0ex}{}{n}{k})$ 种办法。因此容斥理路容斥原理Inclusion–exclusion principle · PIE通过交集的交替和修正多个有限集合并集的重复计数。的第 $k$ 项为 $(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=(-1{)}^{k}n!/k!$，相加得到公式。

这里不能把“第一个不回原位的概率”连乘 $n$ 次，因为前面的放置会改变后面的可选位置，坏事件并不独立。容斥逐层处理的就是同时固定多个位置造成的重叠。

递推也有具体分解。先选 $1$ 被送到的元素 $j\ne 1$，有 $n-1$ 种。若 $j$ 被送回 $1$，删掉这个二循环，剩下 $D_{n-2}$ 种；若不是，设 $i$ 被送到 $1$，删掉 $1$ 并把 $i$ 直接送到 $j$，便得到剩余 $n-1$ 个元素的一个错排。后者能唯一插回 $1$，贡献 $D_{n-1}$，于是得到两项递推。

三个元素的错排只有两个三循环，所以 $D_3=2$。四个元素的错排可按循环型独立核对：有 $(4-1)!=6$ 个四循环，以及 $3$ 个由两个二循环组成的置换，共 $9$ 个。容斥也给出

两个算法数的是同一批对象，因此它们比再次把另一个数字代入公式更能检验推理。$(12)(34)$ 是合法错排；“没有不动点”不等于“必须只有一个大循环”。

空排列没有任何违反条件的元素，所以 $D_0=1$；一个元素无法离开自身，故 $D_1=0$。二项递推从 $n\ge 2$ 使用，最近整数公式从 $n\ge 1$ 使用，不能把所有边界默认为同一范围。

若四封信中只要求前两封不能回原信封，应只排除两个事件，答案为 $24-6-6+2=14$，而非 $D_4=9$。若每个位置禁放多个不同元素，则需要研究相应禁配图，不能继续套标准错排公式。

由交错级数余项，$|D_n-n!/e|<1/(n+1)$；当 $n\ge 2$ 时小于 $1/2$，再直接检查 $n=1$，便证明最近整数公式的精确性。与此同时，均匀随机排列无不动点的概率 $D_n/n!$ 趋于 $e^{-1}$，这是概率极限而非独立事件乘法。

排列理路排列Permutation有限集合到自身的双射，或其元素的有序排列。给出总体，容斥给出计数，递推则支持只保留前两项的整数计算。其指数生成函数为 $e^{-x}/(1-x)$；展开两个因子并比较 $x^n/n!$ 的系数，又会得到同一个交错和。

把每个元素与每个允许目标位置连边，错排就成为完全二分图删去对角边后的完美匹配理路匹配Matching in a graph由彼此不共享端点的边组成、表达一对一配对约束的边集合。。一般受限指派仍可这样建模，但存在一个匹配、求最优匹配与计算全部匹配数是不同任务，不能从能高效找到一个方案推出能高效计数全部方案。

一般禁位的具体入口是车多项式理路车多项式与禁位排列Rook polynomial · 禁位棋盘计数把兼容的禁位交集编码为非攻击车，证明删占递推、独立分块乘积和禁位排列的容斥公式。。例如在四个对角禁位外再加 $(1,2)$，合法排列从九份降为六份；其车多项式为 $1+5t+8t^2+5t^3+t^4$。若改问恰有 $j$ 个固定点，先选这 $j$ 点，再对其余点错排，得到 $(\genfrac{}{}{0ex}{}{n}{j})D_{n-j}$；这是禁位命中分布理路禁位命中数与车变换Rook hit numbers · Hit polynomial从部分禁位放置恢复恰命中j格的完整排列数，并用双计数、平移多项式和逆变换交叉核验。在对角棋盘上的特例。