错排 子阶乘计算器

欢迎使用错排（子阶乘）计算器，这是一个全面的组合数学工具，可以计算任何 n 个元素集合的错排数量。错排是指没有任何元素出现在其原始位置的排列，记作 !n 或 D(n)。无论您是在学习组合数学、解决经典的取帽问题，还是探索概率论，本计算器都能为您提供详细的分步解答和交互式视觉展示。

什么是错排？

错排（也称为子阶乘）是一个集合中元素的排列，其中没有任何元素出现在其原始位置。n 个元素的错排数量写为 !n（叹号在 n 之前）或 D(n)。

例如，考虑位置 {1, 2, 3} 上的三个项目。共有 3! = 6 种排列，但只有 2 种是错排：

• (2, 3, 1) — 项目 1 到位置 2，项目 2 到位置 3，项目 3 到位置 1
• (3, 1, 2) — 项目 1 到位置 3，项目 2 到位置 1，项目 3 到位置 2

所以 !3 = 2。

错排公式

容斥原理公式

最基本的公式源于容斥原理：

递归公式

错排也可以通过递归计算：

基本情况为：!0 = 1, !1 = 0。

最近整数公式

对于 \(n \geq 1\)，子阶乘等于最接近 \(n!/e\) 的整数：

取帽问题

错排最著名的应用是取帽问题（problème des rencontres）：如果 n 位客人寄存了他们的帽子，然后帽子被随机归还，那么没有客人拿到自己帽子的概率是多少？

答案是 \(!n / n!\)，它会非常迅速地收敛到 \(1/e \approx 0.3679\)。这意味着无论有多少个项目，大约 36.8% 的随机排列都是错排。

如何使用此计算器

1. 输入 n： 输入元素数量（0 到 170）。可以使用快速示例按钮来尝试常见数值。
2. 计算： 点击“计算 !n”来计算错排数。
3. 查看结果： 查看 !n、n!、错排概率以及与 1/e 的比值。
4. 探索动画： 对于较小的 n，通过交互式视觉动画查看错排是如何运作的。
5. 学习步骤： 查看详细的容斥原理分解和错排表。

前 15 个错排数

错排的应用

神秘圣诞老人 / 礼物交换

在组织“神秘圣诞老人”礼物交换时，每个参与者抽取一个名字。没有人抽到自己名字的成功抽取就是一个错排。对于一个 10 人的小组，在总共 3,628,800 种排列中，有 1,334,961 种有效安排。

密码学和编码理论

错排出现在代换密码和纠错码的分析中。“无不动点”的概念是理解加密强度和基于排列的加密的基础。

洗牌和游戏

在卡牌游戏中，错排可以衡量洗牌后没有任何牌回到原始位置的概率。这在分析洗牌质量和游戏公平性时非常有用。

概率论

错排提供了容斥原理的一个优美示例，并说明了概率如何收敛于简单的极限（在本例中为 1/e）。

核心性质

• 当 \(n \to \infty\) 时，比率 \(!n/n!\) 收敛于 \(1/e \approx 0.367879\)
• 收敛速度极快 —— 在 n = 10 时已精确到小数点后 6 位
• \(!n\) 满足递推关系：\(!n = n \cdot !(n-1) + (-1)^n\)
• 指数生成函数为 \(e^{-x}/(1-x)\)
• \(!0 = 1\)（空排列在定义上是一个错排）

常见问题解答

什么是错排？

错排是集合的一种排列，其中没有任何元素出现在其原始位置。例如，如果项目标记为 {1, 2, 3}，则排列 (2, 3, 1) 是一个错排，因为没有任何项目在原位。n 个项目的错排数量记为 !n（子阶乘 n）。

子阶乘 !n 的公式是什么？

可以使用容斥原理公式计算子阶乘 !n：\(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\)。也可以通过递归计算：\(!n = (n-1)(!(n-1) + !(n-2))\)，其中 !0 = 1 且 !1 = 0。另一个有用的公式是当 \(n \geq 1\) 时，\(!n = \text{round}(n! / e)\)。

随机排列是错排的概率是多少？

随着 n 的增加，n 个项目的随机排列是错排的概率趋于 \(1/e \approx 0.3679\)。即使对于较小的 n，这个近似值也非常准确。对于 n = 5，确切概率为 44/120 ≈ 0.3667，已经非常接近 1/e。

什么是取帽问题？

取帽问题（也称为 problème des rencontres）是一个经典的概率谜题：如果有 n 个人在餐厅寄存了他们的帽子，然后帽子被随机归还，没有人拿回自己帽子的概率是多少？答案是错排数 !n 除以总排列数 n!，结果趋于 \(1/e \approx 36.79\%\)。

错排和阶乘之间有什么关系？

错排 (!n) 和阶乘 (n!) 密切相关：\(!n = n! \times \sum(-1)^k/k!\)（k 从 0 到 n）。比率 !n/n! 给出了错排的概率，收敛于 1/e。此外，当 \(n \geq 1\) 时，!n 是最接近 n!/e 的整数，使得 n!/e 成为一个非常有用的近似值。

其他资源

• 错排 - 维基百科
• 容斥原理 - 维基百科
• OEIS A000166 - 子阶乘序列