错位排列

定义

错位排列（derangement）是没有任何元素出现在其有序位置的排列。即，对于 $1 \sim n$ 的排列 $P$ ，如果满足 $P_{i} \neq i$ ，则称 $P$ 是 $n$ 的错位排列。

例如，三元错位排列有 ${2, 3, 1}$ 和 ${3, 1, 2}$ 。四元错位排列有 ${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}$ 。错位排列是没有不动点的排列，即没有长度为 1 的循环。

容斥原理的计算

全集 $U$ 即为 $1 \sim n$ 的排列， $| U | = n!$ ；属性就是 $P_{i} \neq i$ . 套用补集的公式，问题变成求 $| ⋃_{i = 1}^{n} \overset{―}{S_{i}} |$ .

可以知道， $\overset{―}{S_{i}}$ 的含义是满足 $P_{i} = i$ 的排列的数量。用容斥原理把问题式子展开，需要对若干个特定的集合的交集求大小，即：

| ⋂_{i = 1}^{k} S_{a_{i}} |

其中省略了 $a_i

本页面最近更新：2024/8/31 23:47:43，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, Great-designer, Enter-tainer, untitledunrevised, xzdeyg
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用