错排问题

在组合数学中，紊乱是集合元素的排列，使得没有元素出现在其原始位置。 换句话说，紊乱是一种没有固定点的排列。

一组大小为 n 的紊乱数称为 n 的子阶乘或第 n 个紊乱数或第 n 个 de Montmort 数。 常用的子阶乘符号包括 !n、Dn、dn 或 n¡。

对于 n > 0，子阶乘 !n 等于最接近 n!/e 的整数，其中 n! 表示 n 的阶乘，e 是欧拉数。

假设一位教授给 4 名学生（A、B、C 和 D）进行了测试，并想让他们互相评分。 当然，任何学生都不应该给自己的考试打分。 教授有多少种方法可以将试卷交还给学生进行评分，从而没有学生收到自己的试卷？ 在 24 种可能的排列（4！）中用于交回测试，

只有 9 种紊乱（上面以蓝色斜体显示）。 在这个 4 人组的每个其他排列中，至少有一个学生得到了他们自己的测试（以粗体红色显示）。

当我们询问有多少种方式可以将 n 个字母（每个字母寄给不同的人）放入 n 个预先写好地址的信封中，以便没有一封信出现在正确写好地址的信封中时，就会出现问题的另一个版本。

计算一组的紊乱相当于帽子检查问题，其中考虑了 n 顶帽子（称它们为 h1 到 hn）可以返回给 n 个人（P1 到 Pn）的方式的数量，使得没有帽子可以返回 给它的主人。

每个人可能会收到 n − 1 顶帽子中的任何一顶不是他们自己的。 称 P1 收到的帽子为 hi 并考虑 hi 的所有者：Pi 收到 P1 的帽子、h1 或其他人。 因此，问题分为两种可能的情况：

• Pi 收到了 h1 以外的帽子。 这种情况等同于解决 n − 1 人和 n − 1 顶帽子的问题，因为对于除了 P1 之外的 n − 1 个人中的每个人，在剩余的 n − 1 顶帽子中，他们可能没有收到一顶帽子（对于任何 Pj 除了 Pi 之外，无法接受的帽子是 hj，而对于 Pi 来说是 h1)。 另一种方式是将 h1 重命名为 hi，其中的紊乱更为明确：对于从 2 到 n 的任意 j，Pj 无法接收 hj。
• Pi 收到 h1。 在这种情况下，问题减少到 n – 2 人和 n – 2 顶帽子，因为 P1 收到了 hi 的帽子，Pi 收到了 h1 的帽子，有效地将两者都排除在进一步考虑之外。

对于 P1 可能收到的 n-1 顶帽子中的每顶帽子，P2、…、Pn 可能收到帽子的方式数是这两种情况的计数之和。

人们也可以推导出一个非递归公式来计算 n 集的紊乱次数。 对于 1 ≤ k ≤ n 我们定义 S k 为固定 k  – xxx个对象。 这些集合中的 i 个集合的任何交集固定了一个特定的 i 个对象集合。