2008年3月16日 星期日

造馬

歐聯八強抽籤結果鬧出造馬疑雲(可參考這篇報導),有網友「未卜先知」,在抽籤前個多小時先行公佈「內定抽籤結果」(阿仙奴對利物浦、曼聯對羅馬、車路士對費倫巴治、巴塞隆拿對史浩克 04),最終竟與真正的結果不謀而合。歐洲足協否認造馬指控,指有關事件純屬巧合。以上報導中指猜中抽籤結果的機會是 28 分之 1(There is a one in 28 chance of correctly guessing the Champions League draw at this stage.),可是那是不正確的。

如何計算 8 隊分成 4 對的可能性數目呢?其中一個方法是先抽 2 隊成對,共有 C(8,2) = 28 種可能;然後從餘下 6 隊中再抽兩隊成對,有 15 種可能;再從餘下 4 隊中抽兩隊成對,有 6 種可能;最後剩下的 2 隊成對。這樣便有 28 x 15 x 6 = 2520 個可能,但由於 4 對的次序不拘,因此每種抽籤結果我們都數了 4! = 24 次,從而抽籤結果只有 2520/24 = 105 個不同的可能。換句話說,猜中抽籤結果的機會應是 105 分之 1。

另一種數算的方法是先隨便選一隊(例如是英文字母序最先的一隊),然後選那隊的對手,這樣有 7 個可能;然後從餘下 6 隊中再選英文字母序最先的一隊,那麼這隊的對手便有 5 個可能;再之後餘下 4 隊中英文字母序最先的一隊的對手有 3 個可能;最後剩下的 2 隊對賽。由此可見,抽籤結果共有 7 x 5 x 3 = 105 個不同的可能。

從第二種方法可知,把 2n 隊分成 n 對對賽的方法共有

1 x 3 x 5 x ... x (2n-1) = (2n-1)!! 種

這裡 k!! 是個「double factorial number」(見註)。而比較兩種數算方法,我們亦可得到等式

C(2,2) x C(4,2) x ... x C(2n,2) = n! (2n-1)!!

這種「算兩次(double counting)」的方法在組合數學裡是很常用的,可以證明很多奇妙的等式或不等式。



註:有關「double factorial」的資料,可參考這裡。如果只考慮奇數的 double factorial,即 1!!, 3!!, 5!!, ...,也就是把 2n 人分成 n 對的方法數目,也可參考 The Online Encyclopedia of Integer SequencesA001147。順帶一提,這個「百科全書」很有用,大家可以輸入一串整數(例如:1, 1, 2, 3, 5, 8),然後系統便會搜尋包含這些連續項的數列。

沒有留言: