亂點鴛鴦譜

下麵這篇是一九九五年九月在ACT上有人提問，題目是：A、B兩個集合各有n個元素，本來有個一一對應的，但是如果隨機配對，所有的配對都配錯的概率是多少？(原題的描述要有趣一些，但是我不記得了)


 亂點鴛鴦譜 (Re: 問題求解)

 這個問題有點意思，通俗地講講吧。

 話說月老給ｎ對少男少女牽紅線。誰知這位月老是個馬大哈，
閉著眼睛亂拴一氣，到頭來不知多少癡男怨女被錯配鴛鴦，有情無
緣。隻不知道他老人家糊塗到什麽程度，哪怕隻拴對了一對兒也好
嘛。下麵就來算算連一對兒都拴不對的可能性有多大。

 因為總共有ｎ對男女，一男一女之間拴紅線，所有不同的拴法
總數是ｎ！（ｎ的階乘），所以隻要數清一對兒都拴不對有多少種
拴法，再除以ｎ！就可以得出概率。這是一個計數的問題。

 一對兒都拴不對的拴法並不好數，我們可以先數至少拴對了一
對兒的拴法，再從總數ｎ！中減掉就行了。至少拴對了一對兒，怎
麽數呢？先從ｎ對中任選一對作為拴對了的，這有C(n,1)種選
擇（C(n,1)是ｎ中選１的組合數）；其他紅線就隨便牽，共有
（ｎ－１）！種方法，由此得到一個結果：

 S(1) = C(n,1) * (n-1)!

 您如果細心，就會發現這個結果其實是不對的，因為假如某種
拴法拴對了兩對兒，那麽它在Ｓ（１）中就被數了兩次。所以需要
把這些數過兩次的算法減掉一次才對。至少拴對了兩對兒，有多少
種拴法呢？從ｎ對中選出２對，有C(n,2)種選擇；其餘的紅線
隨便牽，共（ｎ－２）！種方法，於是：

 S(2) = C(n,2) * (n-2)!

 要算的總數是： S(1) - S(2)

 細心人會發現，類似的問題又來了：假如某種拴法拴對了三對
兒，那麽它在Ｓ（１）中被數了３次，在Ｓ（２）中也被數了３次，
兩數一減就沒了，因此我們比須再把它加回來。用和前麵同樣的辦
法算出：

 S(3) = C(n,3) * (n-3)!

 要算的總數是： S(1) - S(2) + S(3)

 下麵再考慮拴對了四對兒的拴法。仔細數數（也是用組合數來
數），它在上麵的Ｓ（１）中數了４次，Ｓ（２）中數了６次，而
Ｓ（３）中又數了４次，加加減減之後還剩下２次，這多出的一次
還是要減掉，所以：

 S(4) = C(n,4) * (n-4)!

 要算的總數是： S(1) - S(2) + S(3) - S(4)

 依此類推，最後算到ｎ對兒全拴對的拴法數：

 S(n) = C(n,n) * 0!

 那麽至少拴對了一對兒的拴法數目就是：

 S(1) - S(2) + S(3) - S(4) + ... + (-1)^(n-1) * S(n)

 我們要數的是所有的紅線都拴錯了的拴法數，記為Ｄ（ｎ），
應該等於ｎ！減去上麵算出的這個數，就得出下列公式：

 D(n) = n! - S(1) + S(2) - S(3) + S(4) - ... + (-1)^n S(n)
 = n! - C(n,1)*(n-1)! + C(n,2)*(n-2)! - ...
 ... + (-1)^n * C(n,n)*0!
 = n! * (1 - 1/1! + 1/2! - ... + (-1)^n * 1/n!)

 這個數除以ｎ！，就得到連一對兒都沒有配上的概率：

 P(n) = 1 - 1/1! + 1/2! - ... + (-1)^n * 1/n!

 正象一位網友指出的，這實際上是ｅ＾（－１）的泰勒展式的
前ｎ＋１項之和。當 n 趨於無窮大，結果就是ｅ＾（－１），
即 36.79% 。

 上麵隻是一般的解釋，不能算嚴格的推導。對數學有興趣的朋
友可以試試嚴格的數學推導。一種方法是先推出下麵這個遞推公式：

 D(n) = (n-1) * [ D(n-2) + D(n-1) ]

 然後由此導出下麵的公式：

 D(n) = n * D(n-1) + (-1)^n

 最後解出Ｄ（ｎ）就不難了。細節不講了吧。