组合数学是啥

1、組合數學是啥？交大應數系 陳秋媛交通大學 資訊科學學士交通大學 應用數學組合數學組碩士交通大學 資訊工程博士交通大學 應用數學系教授學術專長暨研究領域 - 離散數學 (Discrete Mathematics) - 圖型理論 (Graph Theory) - 演算法 (The Design and Analysis of Algorithms) Combinatorics is concerned with arrangements of objects of a set into patterns satisfying specified rules.Combinatorics is con

2、cerned with the existence, enumeration, and analysis of discrete structures.有兩類問題常被考慮到:1. Existence（存在性） of the arrangement.某種 arrangement 是否存在? 若不一定存在, 則在什麼情況下會存在 ( necessary and sufficient conditions是什麼) ?2. Enumeration（列舉） or classification（分類） of the arrangement.若arrangements存在, 有幾種方法? 可以分類嘛?我們不

3、敢說 there are general principles or methods 來解 combinatorial problems. 但 mathematical induction (數學歸納法), inclusion-exclusion principle (容斥原理), pigeonhole principle (鴿籠原理), recurrence relations (遞迴關係), generating functions (生成函數), Burnsides theorem, Polya counting 等都會有用的.經驗當然也是很重要的. The more problems

4、one solves, the more likely one is able to solve the next problems.以下介紹一些例子, 讓大家感受一下什麼是 combinatorial problems.主題1：Perfect Cover of Chessboards（棋盤的完美覆蓋）今有一個8×8的棋盤, 和32個完全相同的 dominoes（棋子）, 每個 domino 佔棋盤上的兩格（可以平放、或直放）.The chessboard A domino問題1. 可否將32個dominoes 排在棋盤上, 滿足：1. no two dominoes overlap

5、（任兩棋子不重疊）,2. every domino covers 2 squares（每一棋子佔兩格）, and 3. all the squares of the chessboard are covered（全部格子都有被蓋到）?符合這3個條件的覆蓋方法, 叫做a perfect cover（完美覆蓋）.你應該看得出：對8×8的棋盤而言, perfect cover不但存在, 而且還很多呢!問題2. 有多少種不同的perfect covers?這就有點難了!但Fischer在1961年, 証出有12,988,816 = 24×(901)2種.動動手：2×2的棋

6、盤, 4×4的棋盤, 6×6的棋盤, 有多少種不同的perfect covers?問題3. 將8×8的棋盤改成是m×n的棋盤.問：那些m和n會有a perfect cover?動動手：2×3的棋盤有沒有a perfect cover?3×3的棋盤有沒有a perfect cover?3×4的棋盤有沒有a perfect cover?有人証明出：一個m×n的棋盤有a perfect cover 的充分必要條件是at least one of m and n is even.【換句話說, 棋盤中的格子數是偶數個時就有a

7、 perfect cover.】動動手：請試寫出証明, 要注意這是充分必要條件.一個m×n的棋盤有a perfect cover at least one of m and n is even.At least one of m and n is even 一個m×n的棋盤有a perfect cover.問題4. 回到8×8的棋盤, 將 “左上角” 和 “右下角” 這兩個格子拿掉.問：是否仍有a perfect cover?XX答案是沒有!但, 如何證明 不論怎麼排dominoes, 都不會有a perfect cover 呢?畢竟排法有很多種啊！有人提出了a

8、simple and clever的證法喔!WBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBWWBWBWBWBBWBWBWBW首先將棋盤塗成黑白交錯出現的形式,以B表黑, 以W表白, 故有32B和32W.這個塗法使得：無論你將一個domino放在棋盤中的那個位置上, B和W都恰用了一次.厲害呀！厲害呀！史上無敵！此時左上角和右下角被塗了同色,不失其一般性, 設它們都被塗了W.拿掉左上角和右下角後, 棋盤中剩下32B和30W.然而一個domino必定是cover 1B and 1W.由於31B + 31W 32B + 30W, 因此不存在a perf

9、ect cover.問題5. 將8×8棋盤推廣成m×n棋盤.也將棋盤塗成黑白交錯出現的形式, 拿掉一些格子.問：什麼情形下會存在a perfect cover?我們由問題4的討論過程中, 知道拿掉的B和W要等多.然而下圖也告訴我們：This is not sufficient！(i.e., 拿掉的B和W等多, 並不足以保證會存在a perfect cover).WBWBWBWBWBWBWBWBWBWB充分必要條件是什麼?將domino推廣成b-omino.5-omino的例子： 推廣perfect cover的定義到m×n的棋盤和b-ominoes.問題6. Wh

10、en does an m×n board have a perfect cover by b-ominoes?可以觀察到：b|mn是一個必要條件.b|m或者b|n是一個充分條件.可以導出充分必要條件 (necessary and sufficient conditions) 嗎?有人証明出：一個m×n 的棋盤有a perfect cover by b-ominoes的充分必要條件是b|m or b|n.【換句話說, 棋盤中的格子數是b的倍數時就有a perfect cover.】要注意這是充分必要條件.動動手：請試寫出証明b|m or b|n 一個m×n的棋盤有a

11、 perfect cover by b-ominoes.以下証明 一個m×n的棋盤有a perfect cover by b-ominoes b|m or b|n.Proof.m可寫成 m = pb + r, 其中 0 r b 1,n 可寫成 n = qb + s, 其中 0 s b 1. (1)我們可藉由旋轉棋盤而使得r s.(不這麼做也可以, 只是討論時, 連r > s的情形也要討論到.)依下圖的塗法, 將整個m×n棋盤用顏色1, 2, ., b塗好.下圖的塗法使得無論你將b-omino放在棋盤中的那個位置上,color 1, color 2, , color b

12、 都恰用了一次.厲害呀！厲害呀！史上無敵！123b-1bb12b-2b-1b-1b1b-3b-2 234b1例如: m = 15, n = 16, b = 6時,p = 2, r = 3, q = 2, s = 4.srpb12345612345612346123456123456123561234561234561245612345612345613456123456123456234561234561234512345612345612346123456123456123561234561234561245612345612345613456123456123456234561234561

13、2345123456123456123461234561234561235612345612345612qb若存在a perfect cover, 則1, 2, , b每個顏色會被塗相同多次.將棋盤分成3部分來檢查:1. 對上方的pb×n個格子而言, 每個顏色被塗相同多次, 都是pn次.2. 對下左方r×qb個格子而言, 每個顏色被塗相同多次, 都是rq次.3. 對下右方r×s個格子而言, 若存在a perfect cover, 則1, 2, , b每個顏色在下右方r×s個格子中會被塗相同多次.由於r s, 我們的塗色方式會使color 1 occurs

14、 once in each row of the r×s part, 因此color 1出現了r次.所以若存在a perfect cover, 則each of colors 2, 3, , b也都要出現r次.所以rs = rb必須成立！若r 0, 則s = b; 此與 (1) 中的s b 1矛盾.因此r = 0. 但這表示b|m. 你可能不會想到有人會證出:一個m×n 的棋盤有a perfect cover by b-ominoes的充分必要條件是這棋盤有一個trivial perfect cover. 所謂的trivial是指：全部的b-omioes都排成直的or都排成

15、橫的.問：b不能整除m, b不能整除n, b|mn做得到嗎？答：做得到！主題2：Cutting a Cube（切立方體木塊）欲將一每邊長為3公尺的立方體木塊, 切成27個邊長為1公尺的立方體木塊.問：最少必須切幾刀?27 ×我們可以看出6刀是足夠的. 但能更少嗎?最中央的那個立方體的6個面都必須經由某刀而來,因此6刀是必須的. 由以上, 切6刀是最好的結果了.主題3：The Problem of the 36 Officers（36個軍官的問題）先看9個軍官, 來自3種軍階（上校、中校、少校）, 3種兵種（陸、海、空）,要將他們排成 3×3 的矩陣,使得在每個 row和每個

16、 column中, 每種軍階和每種兵種都恰出現一次,相同的軍階和兵種配對不能重覆出現.(上校, 陸)(中校, 海)(少校, 空)(少校, 海)(上校, 空)(中校, 陸)(中校, 空)(少校, 陸)(上校, 海)上校中校少校少校上校中校中校少校上校陸海空海空陸空陸海(1,1)(2,2)(3,3)(3,2)(1,3)(2,1)(2,3)(3,1)(1,2)1233122311232313123階拉丁方陣3階拉丁方陣兩個正交的拉丁方陣當合併在一起之後, 全部 3×3 = 9 possible ordered pairs (1,1), (1,2), (1,3), (2,1), (2,2),

17、 (2,3), (3,1), (3,2), (3,3)都有出現.1233122311322133213階拉丁方陣3階拉丁方陣(1,1)(2,3)(3,2)(3,2)(1,1)(2,3)(2,3)(3,2)(1,1)這兩個拉丁方陣沒有正交, 當合併在一起之後, 並沒有全部 3×3 = 9 possible ordered pairs (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) 都有出現.上校中校少校少校上校中校中校少校上校陸空海海陸空空海陸(上校, 陸)(中校, 空)(少校, 海)(少校, 海)(上校, 陸)(中校, 空)(中校, 空)(少校, 海)(上校, 陸)有36個軍官, 來自6種軍階, 6種兵種, 要將他們排成6×6之矩陣,使得在each row and column中, 每種軍階和每種兵種都恰出現一次,相同的軍階和兵種配對不能重覆出現.36軍官的問題相當於是問：是否存在兩