你懂得数吗

《你懂得数吗》由会员分享，可在线阅读，更多相关《你懂得数吗（9页珍藏版）》请在金锄头文库上搜索。

1、你懂得數嗎?我可不懂! 蕭文強 1. 數數難嗎? 還沒上小學的孩子也曉得扳著指頭一個 一個地數, 數數有何難? 但很多計數問題, 往 往叫我們花好幾個鐘頭也數不出來答案, 而 且很多時候並沒有一道具體公式作為答案, 讓我先來介紹一個化學上的例子。 飽和碳氫化合物由若干個碳原子和氫原 子構成, 每個化學鍵都掛上應有的原子個數 (碳的鍵是 4 價, 氫的鍵是1價), 就像第一 個是甲烷 CH4、 下一個是乙烷 C2H6、 再下 一個是丙烷 C3H8, 餘類推 (見圖1)。 化學上 這一連串的化合物稱作烷烴序列。 圖 1 首先, 讓我們探討一下, 如果烷烴有 N 個碳原子, 它應該有多少個氫原子呢?

2、 不妨 這樣形象地描述, 碳原子是一位只伸出手4次 的“權貴”, 而且“權貴”之間不願意通過握手 搞小圈子; 氫原子是只能伸出手 1次的“趨 炎附勢之徒”。“權貴”們自相結識, 組成一個 集團 (見圖2), “趨炎附勢之徒”便爭相上前 握“權貴”伸出的手。 41 42數學傳播20卷3期 民85年9月 圖 2 N 個“權貴”共伸出手 4N 次, 其中 2(N 1) 次用於互相之間握手 (為什麼? ), 餘下的 4N 2(N 1) = 2N +2 次伸出的 手, 馬上吸引了 2N +2 個“趨炎附勢之徒”。 因此, 烷烴的化學結構式是 CNH2N+2。 雖然 化學結構式是確定了, 但化合物的性質卻

3、因 碳原子的組合方式不相同而有異, 化學上這 種現象稱作同分異構, 就像丁烷有兩種 (見圖 3), 化學結構式都是 C4H10, 性質卻不相同。 圖 3 一個自然的提問是: CNH2N+2有多少 個同分異構體? 這個問題在三十年代給解決 了, 運用到的數學比較複雜, 不能在這兒敘述 (有興趣的讀者可參看: 蕭文強, 波利亞計數 定理, 湖南教育出版社, 1991), 答案在下面 的表可窺一斑 (見圖4)。 要注意的是, 沒有一 條具體公式直接給出 CNH2N+2同分異構體 的數目 A(N), 卻有方法計算 A(N), 涉及的 數學知識可不少呢! NA(N) 11 21 31 42 53 65

4、79 818 935 1075 圖 4 由此看來, 數數不容易。 唯其如此數數 極富挑戰, 而且引人入勝, 讓我們從最簡單的 情況開始談吧。 公元前8世紀希臘詩人 HOMER 留給 後世兩首史詩, 其中一首名為 ODYSSEY, 敘述希臘城邦主之一的英雄人物 ULYSSES 經歷特洛戰爭後漂流異域歷盡十年艱辛的經 過。 有一次他去到某個島被獨眼巨人擒獲, 終 於用計把巨人的唯一眼睛弄瞎了方能脫險。 據說可憐的巨人以後只好靠數小石塊牧羊, 每天早上守在山洞口, 每當一頭羊經過時便 執起一塊石, 等到黃昏羊群回來又守在山洞 口, 每當一頭羊經過便放下一塊石。 如果早上 執起的小石塊剛好放完, 他便

5、知道一頭羊也 沒有走失了。 這大抵是民間傳說中最早關於 數學上稱作一一對應這個概念的記載! 你懂得數嗎?我可不懂!43 數數的理論根據就是一一對應。 於有限 集而言, 我們可能不容易體會這個概念的重 要, 因為我們已經非常熟悉 1、2、3 這些 數字了。 (要是想深一層, 1、2、3 . 其實是相 當抽象的東西, 沒有一一對應這個概念是解 釋不來的! ) 於無限集而言, 一一對應是無 限集理論的基石, 由此而得的基數概念, 成為 十九世紀後期由德國數學家 CANTOR 發 展起來的集合論的中心概念。 在這篇文章裡 我們只討論有限集, 不過一一對應仍然大有 用武之地。 讓我舉一個例子來說明, 這

6、個例子 用到的技巧, 在後面還要再用到的。 例子 (多邊形對角線的交點數目): 圖 5 在凸多邊形內, 對角線在多邊形內相交 多少次呢? (假設沒有三條對角線共點)(見圖 5) 不難知道 N 邊形有 N(N 3)/2 條對角 線 (為什麼? ), 如果任何兩條都相交便好辦。 可惜從圖中可以見到它們有時相交於多邊形 外面, 有時說不定平行不相交, 那怎辦呢? 注 意, 從 N 個端點中任取 4點, 它們是某個 凸四邊形的端點 (試證明之), 它的兩條對角 線相交於四邊形內, 也就是在 N 邊形內。 反 之, 任何兩條原來 N 邊形的對角線在 N 邊 形內的交點, 都可以這樣得來, 而且那是個一

7、一對應。 結論是: 對角線在凸多邊形內交點, 與四個端點組成的凸四邊形有一一對應。 要 計算對角線在凸 N 邊形內的交點數目, 只用 計算從 N 點中任取4點的組合數目, 記號寫 作 ?N 4 ? = N(N 1)(N 2)(N 3)/24。 2. 組合數目 上一節結束前用的例子, 涉及一項經常 碰上的組合數目, 現在就讓我們看一看從 N 個元中取出 r 個不同元的組合數目。 這個問 題的答案, 在中國在西方均有悠久歷史, 十 三世紀宋元的書本裡載有乘方圖, 說明源於 古法 (北宋賈憲的立成釋鎖算法, 時約公元 1020年), 用以解代數方程或開高次方。 十七 世紀中葉法國數學家 PASCAL

8、 創立的算術 三角形, 用以計算概率問題, 在一百多年前已 經有西歐數學家提過, 而且也就是賈憲提出 來的乘方圖, 以下我沿用 PASCAL 的記法 (見圖6)。 圖中第 N 行第 r 列出現的數字記 作 C(N,r) 或 ?N r ? , 表示從 N 元中取出 r 不同元的組合數目。 這個數字可以用 N 和 r 表出, 就是 N(N1)(Nr+1) r(r 1)(3)(2)(1) = N! r!(N r)!, 這兒的 n! 是 n 的階乘, 即是 12(n 1)n, 並約定 0! = 1。 雖然大家都一定熟悉 這道 C(N,r) 的公式, 容許我在這裡重複解 釋一遍, 也好藉此介紹兩條數數的

9、基本原理。 44數學傳播20卷3期 民85年9月 01 11 1 21 21 31 331 41 4641 51 5 10 1051r 61 6 15 20 1561 . . . 71 7 21 35 35 2171 . . . 81 8 28 56 70 56 28 8 1 . . . . . . . . . N ?N r ? 圖 6 (1) 加法原理: 實現一個事件, 如果能分 成兩類方式, 彼此互不相同, 並且按第一類方 式有 m 種實現該事件的辦法, 按第二類方式 有 n 種實現該事件的辦法, 那麼以這兩類方 式實現這個事件共有 m+n 種辦法。 例如數 學營參加者有 50 名學生來自

10、甲校, 100 名學 生來自乙校, 有幾種辦法從當中選出一名學 生擔任營長呢? 答案是 50 + 100 = 150, 因為不會有學生既來自甲校又來自乙校。 (2) 乘法原理: 實現一個事件, 如果能分 成兩個階段, 彼此互無相干, 並且知道實現第 一階段有 m 種辦法, 實現第二階段有 n 種辦 法, 那麼通過這兩個階段實現這個事件共有 mn 種辦法。 例如雪糕店售三款雪糕球。 有巧 克力 (C)、 草莓 (S) 和香草 (V), 兩球相疊 的雪糕筒共有多少種呢? 答案是 3 3 = 9。 注意, 如果你討厭上下兩球都是 V , 便只有8 種。 乘法原理不適用, 是因為兩個階段變成互 有相干

11、了。 要得出答案, 可有兩種思路。 其一 是先用乘法原理得出9種, 排除兩球俱為 V 的一種, 即是8種。 其二是混合使用加法原理 及乘法原理, 第一類方式分成以下兩個階段: 先放下面一球, 只能是 C 或 S, 再放上面 一球, 不加限制; 第二類方式分成以下兩個階 段: 先放下面一球, 限定是 V , 再放上面一 球, 只能是 C 或 S。 從乘法原理知道第一類 方式有 2 3 = 6 種辦法, 第二類方式有 12 = 2 種辦法, 再從加法原理知道合起來 有 6 + 2 = 8 種辦法。 不難明白加法原理和乘法原理可以擴展 至多於兩類方式或多於兩個階段的情況。 運 用推廣的乘法原理便計算

12、得到從 N 元中取 出 r 不同元的排列數目, 記作 P(N,r), 即是 N(N 1)(N r + 1) = N! (Nr)!。 運用 推廣的加法原理知道 P(r,r)+P(r,r) (共 C(N,r) 項) = P(N,r), 因此 C(N,r)= P(N,r) P(r,r) = N! r!(N r)!。 3. 球罐模型 很多數數問題都能套進一種球罐模型作 考慮, 讓我在這一節簡單地介紹一下。 把 r 個 球放進 N 個有標號的罐 (圖 7), 共有多少種 方法呢? 1234 圖 7 我們必須弄清楚幾種不同的情況。 你懂得數嗎?我可不懂!45 (甲) 球可辨認 (譬如說, 把球也標號),

13、每個罐頂多只能放一個球。 那麼, 放球方法的 數目等於從 N 元中取出 r 不同元的排列數 目, 即是 P(N,r)。 比方 N = 4, r = 2, 把 標號是1的球放在標號是2的罐、 標號是2的 球放在標號是4 的罐, 這種方法相當於排列 (2,4) (見圖 7)。 (乙) 球不可辨認 (譬如說, 全部塗以紅 漆油!), 每個罐頂多只能放一個球。 那麼, 放 球方法的數目等於從 N 元中取出 r 不同元 的組合數目, 即是 C(N,r)。 比方 N = 4, r = 2, 把兩個球分別放在標號是2和4的罐, 這種方法相當於組合 2,4。 (丙) 球可辨認, 每個罐容許放多於一個 球。 那

14、麼, 放球方法的數目等於從 N 元中取 出 r 元 (選取可重複) 的排列數目。 運用乘 法原理, 不難知道答案是 Nr。 比方 N = 4, r = 2, 把標號是1和2的球都放在標號是 3 的罐, 這種方法相當於排列 (3,3)。 (丁) 球不可辨認, 每個罐容許放多於一 個球。 那麼, 放球方法的數目等於從 N 元中 取出 r 元 (選取可重複) 的組合數目。 比方 N = 4, r = 2, 把兩個球都放在標號是3的 罐, 這種方法相當於組合 3,3。 上面 (甲)、(乙) 和 (丙) 的情況, 答案分 別是 P(N,r)、C(N,r) 和 Nr, 但 (丁) 的 情況怎樣數呢? 就拿

15、 N = 4, r = 2 為例, (甲) 有12種方法, (乙) 有6 種方法, (丙) 有 16種方法 (試臚列每種情況的全部方法), 而 (丁) 應有10 種方法, 即是: 1,1,1,2,1,3,1,4,2,2 2,3,2,4,3,3,3,4,4,4。 如何從 N = 4 和 r = 2 得到答案是10呢? 讓我們用以下的詮釋看看。 設標號是 i 的罐 有 ri個球, 則 r1+rN= r, 我們要計 算的是上式有多少個不同的解 (r1,.,rN), 其中 ri是非負整數。 比方 N = 6, r = 5, (1,2,0,2,0,0) 是一個解, 表示標號是1的罐 有1個球、 標號是2

16、和4的罐各有2個球, 其餘 罐沒有球 (見圖8)。 上述的放球方法亦可簡化 為點與豎杆的組合, 把5條豎杆插放於5點之 間 (見圖8)。 由於放球方法與插放豎杆方法有 一一對應, 我們只用計算插放豎杆方法的數 目。 r 個點和 N 1 條豎杆 (分隔成 N 個 罐) 合成 r+N1 個位置, 從中選取 r 個作 為點的位置, 方法數目即是 C(r+N 1,r), 也就是 (丁) 的情況的答案了。 1234563434 圖 8 以上的四種球罐模型運用到物理學上, 有它的物理意義。 把球看作是粒子, 把罐看作 是能量級, 則每個放球方法代表一個宏觀狀 態。 在近代量子力學猶未發展的時候, 十九世 紀末的物理學家以為粒子是可分辨的, 而且 以為多於一個粒子可以處於同一能量級, 因 此計算宏觀狀態按照 (丙) 的情況分佈, 稱 作 MAXWELL-BOLTZMANN