我很小就從某科普讀物得知，讓大猩猩在鋼琴上蹦11億年，也會演奏出一首貝多芬的第五交響樂。當然，你無法預測11億年中哪個時刻，大猩猩會有此壯舉。以後上了大學對此事有了較清楚的概念。首先，計算需要一些簡化的假定，比如猩猩蹦跳的頻率，還需假定蹦跳是勻速的，所以要對大師的第五交響樂作些假定，什麼餘音繞梁之類，想都不要想。最重要的是，這是統計意義上的，不是說一定會出現。應用通常採取的95%置信區間（Confidence Level），就是說成千上萬隻的大猩猩在鋼琴上亂蹦，經過11億年，95%的猩猩會在無法預知的時間，至少演奏過一次第五交響樂。然而，直至拿到博士學位，對這經過簡化的計算過程，還是一點概念都沒有。 有一次，一位大學同學（同系同年級，開車不到10分鐘！）問我一個問題，是她女兒的回家作業。在0-99這100個數中，多少不含數字1。她當然做出來了，但總覺得有更好的方法。而且當數字變大，她的死算方法馬上就不能用了。這是我的專業，自然是小菜一碟。一般的方法是“Inclusion-Exclusion”原理，或譯成“容斥原理”。設有N個元素，符合條件a的有N(a)個，符合條件b的有N(b)個，符合條件(a,b)的有N(a,b)個，問不符合條件a,b,c,... 的元素有多少。答案是 N(0) - {N(a) + N(b) + ...} + {N(a,b) + N(a,c) + ...} - {N(a,b,c) + ...} + N(0)是不加限制的選擇數。其意義是先減去我們不要的符合條件的選擇。因為減的太多，所以補上。第二次又補的太多，然後再減，直至正好。 現考慮我同學的問題，不妨假定是0-9,999。有4個條件abcd，各代表某一位有數字1。 N(0) = 10,000 N(a) = N(b) = N(c) = N(d) = 1,000 N(a,b) = N(a,c) = ... = 100 （共6項） N(a,b,c) = N(a,b,d) = ... = 10 （共4項） N(a,b,c,d) = 1 所以最終答案是 10,000 - 4,000 + 600 - 40 + 1 = 6,561 就是說先從一萬種減去至少含一個1的數，正好含1，2，3，4個1的數分別被扣、減了1，2，3，4次。現在把至少含兩個1的加回去，正好含2，3，4個1的被加了1，3，6次。再減去至少含三個1的，正好含3，4個1的被減了1，4次。三次操作一起考慮，正好含1，2，3個1的恰好被減了各一次。含四個1的被減了4-6+4=2次，加上N(a,b,c,d) = 1，也是只減一次。 答案用電郵送出後，我覺得這些數字之間是有聯繫的。用C (m,n)代表m中取n的組合數，最後答案可以寫成 C (4,0)104 - C (4,1)103 + C (4,2)102 - C (4,3)10 + C (4,4) = 6,561 將上式與二項式展開(a + b)4相比較，我們發現a = 10, b = -1, 答案6,561就是9的四次方，這才是真正的答案。我原來的方法比死算當然要好多了，而且有通用性。儘管對大數也很不便，但至少可寫程序用電腦輕鬆求解。很顯然，對這個問題來說，那把通用性極大的牛刀確實是重了些。但在考試中，尋找“雞刀”所用的時間很可能比用牛刀殺雞的時間還要長。大多數情況下，你開始並不知道這到底是“雞”還是“牛”。拿這把戰無不勝的牛刀，畢竟保證了任務總是能完成的。 看到這個94，我終於明白這個9和4分別是怎麼來的。每一位數不能含1，所以可以放其餘9個數字中任何一個，共9种放法。一共4位數，就是94。我用容斥原理來解，用上海說，似乎是“港督”了（即傻瓜）。然而，這雞刀儘管人人都懂，但要在很短時間內馬上找到，就要有相當的功力了。黑體輻射現象，人們研究了好幾十年，也就找到了長波極限Rayleigh-Jeans公式和短波極限Wien公式，還有博士生的博士論文是用數值方法把這兩個公式擬合起來，最後當普朗克（Planck）發現了黑體輻射公式 I = a / (eb/T - 1)，這些前輩們真是可以吐血了。然而，沒人會說前輩們的工作是“港督”。正是他們的工作給了普朗克啟發，從而一舉成功。在現在這個問題，前輩和晚輩都是我自己，港督或聰明人也就無所謂了。事實上，這個最後答案還可以用更簡單的方法加以理解。我們問0-9,999中有幾個數不含9，這和不含1當然是一樣的。這就是說9進制的四位數共有多少值。10進制的四位數有104，2進制的四位數有24，9進制的四位數當然是94了。 現在回到大猩猩演奏貝多芬的問題。我們不妨研究蹦了11億年不出現第五交響樂的幾率，就是N（N為天文數字）位數不含某特定數串的組合數有多少。運用容斥原理，先把總數減去出現至少一次第五交響樂的組合數，再加上出現至少兩次的，直至這N位數再也裝不下第五交響樂了。那個吃飽沒事幹的數學家大概證明了，大猩猩蹦了11億年後，95%的大猩猩至少“演奏”了一次第五交響樂。現在假定我們有個10位數，空缺用0填上（Leading 0），而“第五交響樂”只有三個“音符”123，大猩猩蹦了10次後，0.7985%的大猩猩會演奏出至少一次123。多大的N可保證95%的大猩猩演奏123，我想是沒有“雞刀”的，有興趣的讀者可藉助電腦進行計算。 |
