錯排 子階乘計算機

歡迎使用 錯排 子階乘計算機，這是一個全面的組合數學工具，可計算任何 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。

什麼是取帽子問題？

取帽子問題（也稱為 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 - 子階乘數列