1、組合數(shù)學(xué)(Combinatorics),哈爾濱工業(yè)大學(xué)(威海)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 孟凡超 Email: Tele參考書(shū)目,組合數(shù)學(xué)(第四版)/(美)布魯斯(Brualdi, R.A)著；北京機(jī)械工業(yè)出版社,2005.2 盧開(kāi)澄.組合數(shù)學(xué),清華大學(xué)出版社. 孫淑玲.組合數(shù)學(xué)引論,中國(guó)科學(xué)技術(shù)大學(xué)出版社.,課程情況,課程編號(hào)S041001C 考試情況 平時(shí)成績(jī)30分 作業(yè)15分(電子/紙質(zhì)) 課堂表現(xiàn)5分 出勤10分 期末考試成績(jī)70分 上課時(shí)間表(4-9周) 周三第三大節(jié)(H樓529)(14:00-14:50;14:55-15:45) 周四第三大節(jié)(H樓529) (1

2、4:00-14:50;14:55-15:45) 周五第二大節(jié)(H樓529) (10:05-10:55;11:00-11:50),主要內(nèi)容,概述 鴿巢原理 排列與組合 生成排列和組合 二項(xiàng)式系數(shù) 容斥原理及應(yīng)用 遞推關(guān)系和生成函數(shù) 特殊計(jì)數(shù)序列 Polya計(jì)數(shù)法,概述,數(shù)學(xué)研究問(wèn)題 連續(xù)對(duì)象(微積分) 離散對(duì)象(組合數(shù)學(xué)) 組合數(shù)學(xué)研究的問(wèn)題 按照一定的的規(guī)則來(lái)安排有限多個(gè)對(duì)象,研究4類(lèi)問(wèn)題： 1.安排存在性(存在性問(wèn)題) 2.安排的枚舉和分類(lèi)(計(jì)數(shù)問(wèn)題) 3.構(gòu)造性問(wèn)題 4.優(yōu)化問(wèn)題,組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計(jì)數(shù)、分析和優(yōu)化等問(wèn)題的一門(mén)學(xué)科。,概述,1.安排的存在性問(wèn)題(存在性問(wèn)題) 如

3、果把有限多個(gè)對(duì)象按照一定的規(guī)則來(lái)進(jìn)行安排，當(dāng)符合要求的安排并非顯然存在或者顯然不存在時(shí)，首要的問(wèn)題就是要證明或者否定它的存在。,例. 計(jì)算機(jī)學(xué)院有四位老師A,B,C,D，下學(xué)期要開(kāi)設(shè)組合數(shù)學(xué)(1)、算法設(shè)計(jì)與分析(2)、人工智能(3)、并行處理與體系結(jié)構(gòu)(4)4門(mén)課程，如果A與B都能教組合數(shù)學(xué)和算法設(shè)計(jì)與分析，C能教所有4門(mén)課程，D能教人工智能，問(wèn)能否設(shè)計(jì)一種工作安排方案，使得每位老師在下學(xué)期教且僅教一門(mén)課程？,概述,A,B,C,D,1,2,3,4,二分圖,概述,如果A能教組合數(shù)學(xué)和算法設(shè)計(jì)與分析，B能教人工智能和并行處理與體系結(jié)構(gòu)，C能教組合數(shù)學(xué)，D能教人工智能，問(wèn)能否設(shè)計(jì)一種工作安排方案，

4、使得每位老師在下學(xué)期教且僅教一門(mén)課程？,從該例可以看出，滿(mǎn)足一定條件的安排不總是存在？ 那么在什么條件下這種安排是存在的?這是安排的存在性所要研究的中心問(wèn)題。,概述,例.(棋盤(pán)的完美覆蓋) 考慮一張88(8行8列)的64個(gè)正方形的國(guó)際象棋棋盤(pán)，設(shè)有形狀一樣的多米諾牌，每張牌恰好覆蓋棋盤(pán)上相鄰的兩個(gè)方格，那么，是否能夠把32張多米諾牌擺放到棋盤(pán)上，使得任何兩張多米諾牌均不重疊，每張多米諾牌覆蓋兩個(gè)方格，并且棋盤(pán)上的所有方格都被覆蓋??？我們把這樣一種排列稱(chēng)為棋盤(pán)的多米諾牌的完美覆蓋。,88棋盤(pán),完美覆蓋1,完美覆蓋2,完美覆蓋數(shù)：12988816=24(901)2),概述,問(wèn)題1. 如果將棋盤(pán)變?yōu)?/p>

5、 mn (m行n列)，則完美覆蓋是否存在？,問(wèn)題2. 對(duì)于什么樣的m和n存在完美覆蓋？,當(dāng)且僅當(dāng)m和n中至少有一個(gè)是偶數(shù)時(shí)，mn 棋盤(pán)存在完美覆蓋。,不一定存在，例如，3行3列的棋盤(pán)就不存在完美覆蓋。,概述,問(wèn)題3. 如果用一把剪刀剪掉88棋盤(pán)一副對(duì)角線上的兩個(gè)方格，總共剩下62個(gè)方格，那么能否排列31張多米諾牌來(lái)得出這幅被剪過(guò)的棋盤(pán)的完美覆蓋？,88棋盤(pán),問(wèn)題4. 將mn棋盤(pán)上的方格交替涂成黑色和白色，切除一些方格，得到一塊被切過(guò)的棋盤(pán)，這塊被切過(guò)的棋盤(pán)什么時(shí)候存在完美覆蓋？,概述,問(wèn)題5. mn棋盤(pán)在什么條件下存在b-牌完美覆蓋？,一張5牌,當(dāng)且僅當(dāng)b是m的一個(gè)因子或者b是n的一個(gè)因子。,

6、概述,2.安排的枚舉和分類(lèi)(計(jì)數(shù)問(wèn)題) 如果所要求的安排存在，那么有多少種可能的安排方案？如何對(duì)安排的方案進(jìn)行分類(lèi)？,例. 對(duì)正三角形的3個(gè)頂點(diǎn)進(jìn)行紅、藍(lán)兩色著色，有多少種方案？如果我們將經(jīng)過(guò)旋轉(zhuǎn)后相互重合的兩種方案看成是同類(lèi)的，則有多少種方案？,計(jì)數(shù)問(wèn)題是組合數(shù)學(xué)課程研究的重點(diǎn)！,概述,3.構(gòu)造性問(wèn)題 如果所要求的安排存在存在解，則需要給出求出所有的解或者某一特定解的算法，這就是所謂的構(gòu)造性問(wèn)題。,例. 幻方問(wèn)題.將1,2,n2共n2個(gè)整數(shù)填入nn的棋盤(pán)中，使得每行、每列及兩條對(duì)角線上的元素之和均相等，滿(mǎn)足上述條件的一個(gè)安排稱(chēng)為一個(gè)n階幻方。,組合數(shù)學(xué)所研究的是n取何值時(shí)n階幻方存在，并且要

7、找出構(gòu)造n階幻方的一般方法。,2階幻方不存在，但是對(duì)其余所有正整數(shù)n，n階幻方都可以構(gòu)造出來(lái)。,三階幻方,概述,奇數(shù)幻方構(gòu)造方法,首先將i=1放在第一行的中間位置上； 如果i已填入，則除了以下幾種特殊情況外，將i+1填入i所在位置的右邊一列的上一行。 (1)如果i在第一行非最后一列，則將i+1填入i所在位置的右邊一列的底行； (2)如果i在非第一行的最后一列，則將i+1填入i的上一行的第一列； (3)如果i在第一行的最后一列或者i+1位置已經(jīng)被填上，則i+1直接填入i所在位置的正下方。,練習(xí). 寫(xiě)出5階幻方和7階幻方。,概述,n為4倍數(shù)(n=4k)時(shí)的偶幻方(雙偶幻方)構(gòu)造方法,互補(bǔ)：如果兩個(gè)

8、數(shù)字的和等于幻方最大數(shù)和最小數(shù)的和，即n2+1，則稱(chēng)這兩個(gè)數(shù)互補(bǔ)。例如，對(duì)于4階幻方，1與16互補(bǔ)，2與15互補(bǔ)。,4階幻方構(gòu)造方法 將數(shù)字從左到右,從上到下按順序填寫(xiě)； 將對(duì)角線上的數(shù)字，換成與它互補(bǔ)的數(shù)字。,概述,n=4k階幻方構(gòu)造方法 (1)首先將數(shù)字從左到右,從上到下按順序填寫(xiě)； (2)寫(xiě)好后，按照44把它劃分成kk個(gè)方陣,因?yàn)閚是4的倍數(shù),一定能用44的小方陣分割; (3)然后把每個(gè)小方陣的對(duì)角線，像制作4階幻方的方法一樣，將對(duì)角線上的數(shù)字換成互補(bǔ)的數(shù)字，就構(gòu)成了幻方。,概述,n為非4倍數(shù)(n=4k+1)時(shí)的偶幻方(單偶幻方)構(gòu)造方法,構(gòu)造方法(以10階幻方為例) (1)把方陣分為A

9、,B,C,D四個(gè)象限，這樣每一個(gè)象限肯定是奇數(shù)階，在A,B,C,D象限按照奇數(shù)幻方法填數(shù);,概述,(2)在A象限的中間行、中間格開(kāi)始，按照自左向右的方向，標(biāo)出k格，在A象限的其它行則標(biāo)出最左邊的k格，將這些格和C象限相對(duì)位置上的數(shù)互換位置;,概述,(3)在B象限任一行的中間格，自右向左，標(biāo)出k-1列，將B象限標(biāo)出的這些數(shù)和D象限相對(duì)位置上的樹(shù)進(jìn)行交換，就形成幻方。(注：6階幻方由于k-1=0，所以不用再作B和D象限的數(shù)據(jù)交換),練習(xí). 寫(xiě)出6階幻方。,概述,4.優(yōu)化問(wèn)題 在一定條件下找出一個(gè)(或幾個(gè))最優(yōu)或近似最優(yōu)的安排方案。,例. 最短路徑問(wèn)題.考慮一個(gè)由道路和路口組成的系統(tǒng)，一人想從一個(gè)路口A行到另一個(gè)路口B，一般來(lái)說(shuō)，從路口A到路口B存在許多通道，問(wèn)題：確定一條通道，使研此通路從A到C的距離盡可能小，即一條最短路徑。,解決方法1：列出從A到B的所有可能的路徑，計(jì)算每條路徑的距離，然后選擇一條最短的路徑。(效率低！),目標(biāo)：設(shè)計(jì)一個(gè)高效的算法!,概述,采用圖來(lái)描述最短路徑問(wèn)題.,1,2,3,4,5,6,1,12,9,3,4,5,13,4,15,概述,例. 0/1背包問(wèn)題.設(shè)U=u1,u2,un是一個(gè)準(zhǔn)備放入容量為C的背包中的n項(xiàng)物品的集合