細說傾聽。技安聚星堂: envelope matching problem的延伸問題，解構亂序(derangement)的用法

http://johnmayhk.wordpress.com/2008/02/04/alam-derangement-%E4%BA%82%E5%BA%8F/

以下問題，我於課堂上已說過，這裡純粹為同學留一個詳細記錄而已。

Applied mathematics (II) textbook Ex. 2(g) #2

A certain number, $n$ , of persons sit down in a random arrangement on chairs labelled with their names. If $u_n$ denotes the probability that all $n$ chairs are filled wrongly, write down the values of $u_2$ , $u_3$ , $u_4$ and $u_5$ . Show that for $n = 5$ , the chance that more than one person is in his right chair slightly exceeds 0.25.

上述是一個經典問題：亂序（Derangement）的特例，一般問法是：
“n 個人入座，設每人有大會指定的坐位，但他們不清楚，亂坐，問他們完全『坐錯』的機會。”

順著題意，列舉數例如下：

考慮 $n = 2$ 的情況，
設正確排序為
1, 2
則亂序（即所謂『坐錯』）的情況是
2, 1
即是說亂序的情況有 1 個，或曰：亂序數 = 1；記之曰 $D_2 = 1$
故 $u_2 = \frac{D_2}{2!} = \frac{1}{2}$

當 $n = 3$ 時，
正確序：1, 2, 3
亂序：
2, 3, 1
3, 1, 2
即亂序數 $D_3 = 2$
故 $u_3 = \frac{D_3}{3!} = \frac{1}{3}$

當 $n = 4$ 時，
正確序：1, 2, 3, 4
亂序：
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
即亂序數 $D_4 = 9$
故 $u_4 = \frac{D_4}{4!} = \frac{3}{8}$

當 $n$ 愈來愈大，要算數 $D_n$ 便愈來愈困難。但，若果我們知道以下關係：對 $n \ge 3$ ，恆有

$D_n = (n - 1)(D_{n - 1} + D_{n - 2})$ – - – (*)

我們便容易得出 $D_5 = 4(D_4 + D_3) = 4(9 + 2) = 44$ 了。
則 $u_5 = \frac{44}{5!} = \frac{11}{30}$ 。

問題是如何得到 (*) 這個遞迴關係？讓我以 $n = 5$ 的情況說明。
我們希望數算一下 5 個人『坐錯位』的情況有多少。

1 號位，要『坐錯』，我們可以『安排』阿 2,3,4,5 這 4 個人坐之。即 4 個可能性。

好了，假設阿 4 坐了 1 號位。讓我們看看 4 號位。這裡有以下 2 種『互斥』(exclusive) 的情況：

(情況 1) 阿 1 坐 4 號位。即是阿 1 和阿 4 交換了坐位。
(情況 2) 阿 1 不是坐 4 號位。

好了，現在數算一下 (情況 1) 有多少可能性。

因為要 5 個人坐亂，已知阿 1 和阿 4 已交換坐，剩下的 3 個坐位 2,3,5 也要『坐亂』，即阿 2,3,5 要亂坐，由定義，3 人坐亂的亂序數為 $D_3$ ，即有 (情況 1) 共有 $D_3$ （= 2）種情況。

那麼 (情況 2) 有多少可能性呢？

答曰： $D_4$ 種。

這裡，同學在堂上有疑問。因為 (情況 2) 要求阿 1 不坐 4 號位；但， $D_4$ ，是 4 人坐亂的可能情況的數目，但 4 人坐亂，會否包括：『阿 1 坐了 4 號位』呢？如果包括，這個數算方法不是和 (情況 1) 有些『重疊』嗎？那麼它們便不是『互斥』事件了！

嗯，這個可能是解說這問題的『難點』。

我們要數算 (情況 2) ，必要確保『阿 1 不坐 4 號位』；
那麼，讓我們把 4 號位『重新命名』為『1』號位，
即是，現在剩下了坐位 2,3,『1』,5，提供給阿 2,阿 3,阿 1,阿 5 坐下。
於是， $D_4$ 種情況，便已暗指『阿 1 不坐『1』號位』這個情況了。

於是，當阿 4 坐了 1 號位，共有 $D_3 + D_4$ 種坐亂的情況。
同理，阿 2, 阿 3, 阿 5, 也可安排坐 1 號位，分別也對應著 $D_3 + D_4$ 種坐亂的情況。
故 5 人坐亂的情況共有 $4(D_3 + D_4)$ 種。

把問題一般化，考慮 n 人。設阿 k 坐了 1 號位（k $\neq$ 1），則 k 號位有以下兩種互斥情況：

(情況 1) 阿 1 坐 k 號位。即是阿 1 和阿 k 交換了坐位。
(情況 2) 阿 1 不是坐 k 號位。

因循上面類似的推論，
(情況 1) 共有 $D_{n - 2}$ 種（阿 k 和阿 1 交換，剩下 (n-2) 個位以提 n-2 人亂坐）；
(情況 2) 共有 $D_{n - 1}$ 種（阿 k 坐了 1 號位，剩下 (n-1) 個位以提 n-1 人亂坐，特別地，阿 1 不能坐 k 號位）。
故當阿 k 坐了 1 號位，對應亂序總數為 $D_{n - 2} + D_{n - 1}$ ，
而 k 可以是 2,3,…,n （共 n – 1 種情況），於是有

$D_n = (n - 1)(D_{n - 1} + D_{n - 2})$ – - – (*)

對於 $n \in \mathbb{N}$ ，只要稍微推論，我們可得到 $D_n$ 的一般解如下：

$D_n = n!(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} -\dots + \frac{(-1)^{n}}{n!})$ – - – (**)

要證明 (**)，起碼有兩個方法。

（方法一）利用遞迴關係 (recurrence relation)

由 (*)，得
$D_n - D_{n-1} = (n - 1)(D_{n-1} + D_{n-2}) - (n - 2)(D_{n-2} + D_{n-3})$

（為何要考慮 $D_n - D_{n-1}$ ？頗自然的，我們想看看相鄰兩項究竟相差多少而已。）化簡，得

$D_n - nD_{n-1} = D_{n-2} - (n - 2)D_{n-3}$ – - – (***)

(***) 類似『reduction formula』，只要不斷運用它，index n 便可不斷下降 (reduced)，即

$D_n - nD_{n - 1}$
= $D_{n-2} - (n - 2)D_{n-3}$
= $D_{n-4} - (n - 4)D_{n-5}$
… (inductively)
= $D_2 - 2D_{1} = 1$ (for even number $n$ and note that $D_1 = 0$ )
or $D_3 - 3D_{2} = -1$ (for odd number $n$ )
= $(-1)^n$

即

$D_n = nD_{n-1} + (-1)^n$ – - – (****)

(****) 又是一種『reduction formula』，我們又可重覆使用之。

$D_n$
= $nD_{n-1} + (-1)^n$
= $n((n - 1)D_{n-2} + (-1)^{n-1}) + (-1)^n$
= $n(n - 1)D_{n-2} + n(-1)^{n-1} + (-1)^n$
= $n(n - 1)((n - 2)D_{n-3} + (-1)^{n-2}) + n(-1)^{n-1} + (-1)^n$
= $n(n - 1)(n - 2)D_{n-3} + n(n - 1)(-1)^{n-2} + n(-1)^{n-1} + (-1)^n$
= …
(inductively)
= $n(n - 1)(n - 2)...\times 4\times 3\times 2D_1$
+ $n(n - 1)(n - 2)...\times 4\times 3(-1)^2$
+ $n(n - 1)(n - 2)...\times 4(-1)^3$
+ …
+ $(-1)^n$
= $n!(\frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!})$

即 (**)，證畢。

（方法二）利用『容斥原理』(Inclusion-exclusion principle)

不詳談了，因為已經寫了很多廢話。簡而言之曰

設 $E_i$ 為『阿 i 坐在 i 號位』這事件，則

$D_n$
= $n!(1 - P(\cup_{i=1}^{n}E_i))$
= $n!(1 - C_{1}^{n}(\frac{1}{n}) + C_{2}^{n}(\frac{1}{n(n - 1)}) - C_{3}^{n}(\frac{1}{n(n - 1)(n - 2)}) + \dots + (-1)^nC_{n}^{n}(\frac{1}{n!}))$