組合數學經典問題：n 對情侶重新配對，求完全錯位的排列總數

這是一個經典的錯位排列問題。有 n 對已配對的對象（可視為 1↔1, 2↔2, …, n↔n），現隨機重新一對一配對，要求每個人新配對的對象都不等於原配對象，且配對內部無序、配對之間也無序。求滿足條件的配對總數。

問題數學模型

將原配對編號為 1,2,…,n。重新配對等價於對集合 {1,2,…,n} 作一個無固點排列：即排列 π 滿足 π(i) ≠ i 對所有 i 成立。這正是錯排數 D_n（或記作 !n）。

常見錯誤思路分析

提問者嘗試：第一人有 n-1 種選擇，選了 B，則 B 原配對者有 n-1 種選擇……得到 (n-1) × (n-1)!。這錯在將後續選擇視為獨立且等價，忽略了「被選中者原配對者的選擇範圍會因先前選擇而動態變化」的遞歸結構，導致過度計數。

正確解法：容斥原理推導錯排公式

設 S_i 為「至少有 i 個元素在原位置」的排列數。任選 i 個元素固定，其餘 n-i 個任意全排列，故 |S_i| = C(n,i) × (n-i)! = n! / i!。

由容斥原理，錯排數為：

D_n = n! - C(n,1)(n-1)! + C(n,2)(n-2)! - … + (-1)ⁿ C(n,n)0!

即 D_n = n! × Σ_k=0..n (-1)^k / k!。

遞歸公式與計算實現

更適合程式計算的遞歸關係：

• D₀ = 1（空排列視為 1 種）
• D₁ = 0
• D_n = (n-1) × (D_n-1 + D_n-2) for n ≥ 2

Python 實現範例：

def derangement(n):
    if n == 0: return 1
    if n == 1: return 0
    d0, d1 = 1, 0
    for i in range(2, n+1):
        d0, d1 = d1, (i-1) * (d1 + d0)
    return d1

# 測試
for n in range(1, 11):
    print(f"D_{n} = {derangement(n)}")
# 輸出: D_1=0, D_2=1, D_3=2, D_4=9, D_5=44, D_6=265, D_7=1854, D_8=14833, D_9=133496, D_10=1334961

近似值與應用

當 n 較大時，D_n ≈ n! / e（e 為自然對數底），且 D_n 是 n!/e 的最近整數。此問題廣泛應用於禮物交換、座位重排、密碼學置換網路等場景。