OI-wiki 错位排列Derangement完全指南容斥推导、递推关系与生成函数视角【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读错位排列derangement是组合数学中一类经典计数对象在 $1\sim n$ 的所有排列中不允许任何元素停留在其原位。本文以 OI-wiki 数学板块的 错位排列文档 为主体完整还原其定义、容斥原理推导、递推关系的直觉建模过程并引入 指数生成函数应用 中的置换环视角作为进阶补充。读完本文你将掌握错位排列数 $D_n$ 的三种主流求法容斥公式、两条递推式、取整表达式、它们的适用场景以及错排概念在计数类算法竞赛题目中的常见变形。定义没有不动点的排列错位排列derangement指没有任何元素出现在其有序位置的排列。即对于 $1\sim n$ 的排列 $P$若满足$$ P_i\neq i \quad (1\le i\le n) $$则称 $P$ 是 $n$ 的错位排列。从置换的角度看一个排列可以唯一分解为若干循环置换环其中长度为 $1$ 的循环称为不动点fixed point。错位排列正是不含任何长度为 $1$ 的循环的排列这一视角在后续的生成函数推导中会发挥关键作用。小规模枚举三元错位排列共有 2 个即 ${2,3,1}$ 和 ${3,1,2}$四元错位排列共有 9 个$$ {2,1,4,3},\ {2,3,4,1},\ {2,4,1,3},\ {3,1,4,2},\ {3,4,1,2},\ {3,4,2,1},\ {4,1,2,3},\ {4,3,1,2},\ {4,3,2,1} $$错位排列数列的前几项为 $0,1,2,9,44,265,\dots$对应 OEIS A000166。注意 $D_10$$1$ 的排列只有 ${1}$必然原位不动$D_21$即 ${2,1}$。方法一用容斥原理计算 $D_n$容斥原理是计数至少违反若干约束对象的经典工具。本小节完整还原 OI-wiki 文档中的推导链其前置知识见仓库中的 容斥原理文档该文档同样包含补集公式 $\left|\bigcap_{i1}^{n}S_i\right||U|-\left|\bigcup_{i1}^n\overline{S_i}\right|$ 及其证明。建立集合模型设全集 $U$ 为 $1\sim n$ 的全部排列显然 $|U|n!$。令 $S_i$ 表示满足 $P_i\neq i$ 的排列集合则错位排列数即为$$ \left|\bigcap_{i1}^n S_i\right| $$直接求交困难转而利用补集$\overline{S_i}$ 表示 $P_ii$第 $i$ 个元素不动的排列集合。由补集形式的容斥公式$$ \begin{aligned} \left|\bigcap_{i1}^n S_i\right| |U|-\left|\bigcup_{i1}^n\overline{S_i}\right|\ n!-\sum_{k1}^n(-1)^{k-1}\sum_{a_ia_{i1}}\left|\bigcap_{i1}^{k}\overline{S_{a_i}}\right| \end{aligned} $$其中内层求和的含义是从 $1,2,\cdots,n$ 中取出 $a_1,a_2,\cdots,a_k$ 且满足 $a_ia_{i1}$即枚举所有大小为 $k$ 的下标子集。计算交集大小并化简$\left|\bigcap_{i1}^{k}\overline{S_{a_i}}\right|$ 表示恰好指定的 $k$ 个数 $a_1,\dots,a_k$ 满足 $P_{a_i}a_i$原地不动而剩下 $n-k$ 个位置可任意排列因此$$ \left|\bigcap_{i1}^{k}\overline{S_{a_i}}\right|(n-k)! $$这 $k$ 个下标的选择方式共 $\dbinom{n}{k}$ 种代入求和$$ \begin{aligned} \sum_{k1}^n(-1)^{k-1}\sum_{a_ia_{i1}}\left|\bigcap_{i1}^{k}\overline{S_{a_i}}\right|\ \sum_{k1}^n(-1)^{k-1}\dbinom{n}{k}(n-k)!\ \sum_{k1}^n(-1)^{k-1}\frac{n!}{k!}\ n!\sum_{k1}^n\frac{(-1)^{k-1} }{k!} \end{aligned} $$于是 $n$ 个元素的错位排列数最终化简为$$ D_nn!-n!\sum_{k1}^n\frac{(-1)^{k-1} }{k!}n!\sum_{k0}^n\frac{(-1)^k}{k!} $$要点小结该公式把所有排列数 $n!$减去至少有一个元素不动的排列数且通过 $(-1)^{k-1}$ 的交替符号消除了多算/漏算。对于需要取模如模 $998244353$ 或 $10^97$的题目可先预处理阶乘与阶乘逆元再对 $k0..n$ 累加 $(-1)^k\cdot \mathrm{invfact}[k]$总复杂度 $O(n)$。方法二递推计算——错信封问题的直觉建模OI-wiki 文档用一个经典问题具象化递推的由来$n$ 封不同的信编号分别是 $1,2,3,4,5$现在要把这五封信放在编号 $1,2,3,4,5$ 的信封中要求信封的编号与信的编号不一样问有多少种不同的放置方法假设已经处理好前 $n-1$ 个信封初始时暂时把第 $n$ 封信放在第 $n$ 个信封中随后考虑两种情况前面 $n-1$ 个信封全部装错因为前 $n-1$ 个已经全部错排只需让第 $n$ 封信与前面 $n-1$ 个位置中的任意一个交换即可得到长度为 $n$ 的完整错排。每个交换对应一种错排共 $D_{n-1}\times (n-1)$ 种。前面 $n-1$ 个信封恰好有一个没有装错其余全部装错此时把那个装对了的信封与第 $n$ 个信封交换使原本装对的信封变成错的同时第 $n$ 封信也离开了原位得到一个全错位排列。除上述两种情况外前 $n-1$ 个位置若存在两个及以上装对的位置仅靠一次与第 $n$ 封信的交换无法同时消除这些不动点因此不可能通过一次操作构造出长度为 $n$ 的错排。综合两种情况错位排列数满足递推关系$$ D_n(n-1)(D_{n-1}D_{n-2}) $$该递推式配合初值 $D_10,\ D_21$或 $D_01,\ D_10$即可 $O(n)$ 递推求出所有 $D_i$是竞赛实现中最常用的形式。OI-wiki 文档还给出另一条递推关系$$ D_nnD_{n-1}{(-1)}^n $$这条递推可以直接从容斥公式 $D_nn!\sum_{k0}^n\frac{(-1)^k}{k!}$ 导出将 $D_{n-1}(n-1)!\sum_{k0}^{n-1}\frac{(-1)^k}{k!}$ 代入并比较两式即可验证它在只需要单项取值且不方便开逆元数组时也很实用。方法三其他关系——阶乘、自然常数与概率极限取整表达式错位排列数有一个简洁的取整表达式其增长速度与阶乘仅相差一个常数因子$$ D_n\left\lfloor\frac{n!}{\mathrm{e}} \frac{1}{2}\right\rfloor $$即 $D_n$ 是 $\dfrac{n!}{\mathrm{e}}$ 四舍五入后的整数$\lfloor x\tfrac12\rfloor$ 即对 $x$ 作最近取整。概率极限考虑随机取一个 $1\sim n$ 的排列它恰好是错位排列的概率为 $\dfrac{D_n}{n!}$。随着 $n$ 增大该概率趋近于$$ P\lim_{n\to\infty}\frac{D_n}{n!}\frac{1}{\mathrm{e}} $$直观含义是当 $n$ 足够大时约 $36.8%$$1/\mathrm{e}\approx 0.3679$的随机排列是错排。这一结论也常作为概率题中期望不动点个数等问题的背景。进阶视角生成函数与置换环仓库中 指数生成函数EGF文档 的错排数应用小节给出了错排的生成函数视角可与本文的置换环定义互相印证从置换环的角度考虑错排就是指置换环中不存在自环的排列也就是说不存在长度为 $1$ 的置换环。后者的指数生成函数是 $$ \sum_{n\ge 2}\frac{x^n}{n}-\ln\left(1-x\right)-x $$ 因此错排数的指数生成函数就是 $\exp(-\ln(1-x)-x)$这里的自环即长度为 $1$ 的循环不动点与本文定义错位排列是没有不动点的排列完全等价。利用指数生成函数可以进一步推导 $D_n$ 的解析式、处理带限制的错排变体如恰好 $k$ 个不动点的计数是多项式与组合数学结合的进阶方向适合学完基础求法后的读者继续深入 该文档。在算法竞赛中的典型用法与注意事项综合 OI-wiki 中 错位排列文档 及相关章节实战中请记住以下几点三种求法各有定位取整表达式 $D_n\left\lfloor n!/\mathrm{e}1/2\right\rfloor$ 适合手算或浮点估算递推式 $D_n(n-1)(D_{n-1}D_{n-2})$ 适合 $O(n)$ 预处理后 $O(1)$ 查询容斥公式适合结合取模、需要阶乘逆元的场景也是唯一能自然推广到恰好 $k$ 个不动点计数的形式把求和下界改为 $k$ 即可。初值别写错递推实现时建议取 $D_01,\ D_10$再套用 $D_n(n-1)(D_{n-1}D_{n-2})$。变形识别题目中出现每个人不能坐回原位每封信不能放入对应信封映射无不动点等描述时应联想到错排而恰好有 $k$ 个位置不变一类问题可结合容斥或组合数 $\dbinom{n}{k}D_{n-k}$ 处理。与其他计数工具联动错排常与容斥原理见 容斥原理文档、排列组合、概率期望、指数生成函数见 EGF 应用组合出现掌握其推导过程而非死记公式才能在综合题中灵活迁移。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考