計(jì)算機(jī)組合數(shù)學(xué)-CHO1省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)

組合數(shù)學(xué)吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院年9月第1頁(yè)關(guān)于我姓名：盧奕南luyn@單位：圖像處理與虛擬現(xiàn)實(shí)研究團(tuán)體

主要研究方向：圖像處理、模式識(shí)別第2頁(yè)關(guān)于教材內(nèi)部試用版本時(shí)間：下周一下午地點(diǎn)：計(jì)算機(jī)大樓A413價(jià)格：每本20元組織：請(qǐng)各班班長(zhǎng)帶著本班教材費(fèi)前來(lái)領(lǐng)取電話3頁(yè)參考書(shū)：機(jī)械工業(yè)出版社：組合數(shù)學(xué)，布魯?shù)?BrualdiR.A.)(作者),馮舜璽

(譯者)清華大學(xué)出版社：組合數(shù)學(xué)，盧開(kāi)澄等上網(wǎng)習(xí)題

組合數(shù)學(xué)（姜建國(guó)等），西安電子科技大學(xué)

第4頁(yè)本學(xué)期包括到內(nèi)容：鴿巢原理和Ramsey定理（存在性問(wèn)題）基本計(jì)數(shù)方法容斥原理生成函數(shù)遞推關(guān)系Pólya定理第5頁(yè)怎樣學(xué)好組合數(shù)學(xué)組合數(shù)學(xué)經(jīng)常使用方法并不高深復(fù)雜。最主要方法是計(jì)數(shù)時(shí)合理分類組合模型轉(zhuǎn)換（一一對(duì)應(yīng)）。組合分析數(shù)學(xué)歸納法反證法要學(xué)好組合數(shù)學(xué)并非易事，既需要一定數(shù)學(xué)涵養(yǎng)，也要進(jìn)行相當(dāng)訓(xùn)練。可從規(guī)模小模型著手，從中找到規(guī)律性東西，再推及普通。你處理問(wèn)題越多，那么你能夠處理下一個(gè)問(wèn)題可能性也越大。

第6頁(yè)7第一章引言組合數(shù)學(xué)(簡(jiǎn)稱組合學(xué)）是數(shù)學(xué)一個(gè)分支,它起源于古代娛樂(lè)和休閑游戲。以后這些問(wèn)題逐步與數(shù)論、概率統(tǒng)計(jì)、拓?fù)鋵W(xué)、線性規(guī)劃等學(xué)科問(wèn)題交織在一起，逐步形成一個(gè)理論。廣義組合數(shù)學(xué)就是離散數(shù)學(xué)，離散數(shù)學(xué)是狹義組合數(shù)學(xué)和圖論、代數(shù)結(jié)構(gòu)、數(shù)理邏輯等總稱。

工程認(rèn)證第7頁(yè)組合數(shù)學(xué)中著名問(wèn)題計(jì)算一些物品在特定條件下分組方法數(shù)目。這些是關(guān)于排列、組合和整數(shù)分拆。地圖著色問(wèn)題：對(duì)世界地圖著色，每一個(gè)國(guó)家使用一個(gè)顏色。假如要求相鄰國(guó)家顏色相異，是否總共只需四種顏色？這是圖論問(wèn)題。船夫過(guò)河問(wèn)題：船夫要把一匹狼、一只羊和一棵白菜運(yùn)過(guò)河。只要船夫不在場(chǎng)，羊就會(huì)吃白菜、狼就會(huì)吃羊。船夫船每次只能運(yùn)輸一個(gè)東西。怎樣把全部東西都運(yùn)過(guò)河？這是線性規(guī)劃問(wèn)題。中國(guó)郵差問(wèn)題：由中國(guó)組合數(shù)學(xué)家管梅谷教授提出。郵遞員要穿過(guò)城市每一條路最少一次，怎樣行走走過(guò)旅程最短？1856年，哈密爾頓（Kirkman）,旅行商問(wèn)題。任務(wù)分配問(wèn)題：有一些員工要完成一些任務(wù)。各個(gè)員工完成不一樣任務(wù)所花費(fèi)時(shí)間都不一樣。每個(gè)員工只分配一項(xiàng)任務(wù)。每項(xiàng)任務(wù)只被分配給一個(gè)員工。怎樣分配員工與任務(wù)以使所花費(fèi)時(shí)間最少？這是線性規(guī)劃問(wèn)題。怎樣結(jié)構(gòu)幻方。第8頁(yè)組合數(shù)學(xué)起源幻方最早記載于我國(guó)公元前500年春秋時(shí)期《大戴禮》中，這說(shuō)明我國(guó)人民早在2500年前就已經(jīng)知道了幻方排列規(guī)律。而在國(guó)外，公元130年，希臘人塞翁才第一次提起幻方

；公園1275年（宋代），楊輝著作中出現(xiàn)10階幻方問(wèn)題和楊輝三角記載；1666年，萊布尼茨發(fā)表《組合藝術(shù)》(DeArtCombinatoria)，這是組合數(shù)學(xué)第一部專著。書(shū)中首次使用了組合論（Combinatorics）一詞。標(biāo)志組合數(shù)學(xué)誕生。萊布尼茨：德國(guó)最主要自然科學(xué)家、數(shù)學(xué)家、物理學(xué)家、歷史學(xué)家和哲學(xué)家，一個(gè)舉世罕見(jiàn)科學(xué)天才，和牛頓（1643年1月4日—1727年3月31日）同為微積分創(chuàng)建人。

楊輝，中國(guó)南宋時(shí)期出色數(shù)學(xué)家和數(shù)學(xué)教育家。

第9頁(yè)組合分析和組合算法已經(jīng)被廣泛應(yīng)用與計(jì)算機(jī)科學(xué)、管理科學(xué)、信息科學(xué)、電子工程、人工智能、生命科學(xué)等很多領(lǐng)域中。第10頁(yè)11組合數(shù)學(xué)蓬勃發(fā)展則是在計(jì)算機(jī)問(wèn)世和普遍應(yīng)用之后。首先，當(dāng)我們研究組合問(wèn)題規(guī)模很大時(shí)候，計(jì)算量會(huì)很大，計(jì)算機(jī)為求解這些問(wèn)題提供了有力伎倆。另首先，在計(jì)算機(jī)科學(xué)算法研究中數(shù)據(jù)結(jié)構(gòu)+算法+編程語(yǔ)言時(shí)間復(fù)雜性和空間復(fù)雜性《計(jì)算復(fù)雜性理論》、《算法設(shè)計(jì)與分析》基礎(chǔ)課。第11頁(yè)什么是組合數(shù)學(xué)組合數(shù)學(xué)就是研究按照一定規(guī)則來(lái)安排一些離散個(gè)體問(wèn)題。它包括面廣，內(nèi)容龐雜（包括到組合分析、圖論、組合算法、近代密碼學(xué)、編碼理論等），而且仍在很快地發(fā)展著，因而還沒(méi)有一個(gè)統(tǒng)一而有效理論體系。

研究對(duì)象是離散結(jié)構(gòu)，普通能夠用{1，2，、、、，n}表示。本書(shū)僅限于討論n是有限自然數(shù)情況。組合數(shù)學(xué)是研究離散結(jié)構(gòu)存在、計(jì)數(shù)、分析和優(yōu)化等問(wèn)題一門(mén)學(xué)科。第12頁(yè)13

組合數(shù)學(xué)主要問(wèn)題（1）存在性問(wèn)題 滿足一定條件安排存在性.假如某種安排不一定總存在，我們就需要研究存在條件。

存在性是數(shù)學(xué)研究最主要問(wèn)題之一.許多問(wèn)題存在性至今也無(wú)法處理？

比如數(shù)論中很多難題：哥德巴赫猜測(cè)…第13頁(yè)（2）安排枚舉、分類和計(jì)數(shù)

假如所要求安排存在，則可能有各種不一樣安排。此時(shí)，需要計(jì)數(shù)不一樣方案數(shù)，并將它們進(jìn)行枚舉和分類。

當(dāng)實(shí)際問(wèn)題比較復(fù)雜時(shí)候，必須有好數(shù)學(xué)方法來(lái)處理.第14頁(yè)（3）結(jié)構(gòu)性問(wèn)題

一個(gè)組合問(wèn)題，假如已經(jīng)判定解是存在，那么將全部可能安排結(jié)構(gòu)出來(lái)是一個(gè)關(guān)鍵問(wèn)題。

與計(jì)算機(jī)算法親密相關(guān)

經(jīng)典問(wèn)題：組合設(shè)計(jì)第15頁(yè)（4）優(yōu)化問(wèn)題

在給定優(yōu)化條件下從全部安排方案中找出最優(yōu)安排方案。旅行商問(wèn)題(TravelingSalesmanProblem，簡(jiǎn)稱TSP)與算法分析親密相關(guān)傳統(tǒng)方法當(dāng)代智能方法第16頁(yè)17幻方問(wèn)題——有趣數(shù)學(xué)游戲幻方在娛樂(lè)數(shù)學(xué)中地位以及它意義非同普通，它是中國(guó)人首創(chuàng)。

公元前2200年《易經(jīng)》提到洛書(shū)與河圖

§1.1幻方問(wèn)題第17頁(yè)816357412一個(gè)n階幻方是由整數(shù)1，2，3…，n2按下述方式組成n×n方陣：該方陣每行上整數(shù)和、每列上整數(shù)和以及兩條對(duì)角線中每條對(duì)角線上整數(shù)和都等于同一個(gè)數(shù)s

第18頁(yè)19

3階幻方全部整數(shù)和為15；每一行（或列或?qū)蔷€）數(shù)字和稱為幻方和（幻和）：

S=

n

(n2+1)/2

。第19頁(yè)關(guān)于幻方問(wèn)題歸結(jié)為（一）存在性問(wèn)題對(duì)任意正整數(shù)n，n階幻方存在嗎？（二）組累計(jì)數(shù)問(wèn)題假如存在，那么應(yīng)該有多少個(gè)不一樣

n階幻方。（三）結(jié)構(gòu)問(wèn)題奇數(shù)階幻方：連續(xù)擺數(shù)法(deLaLoubère法)

雙偶數(shù)（4k）階幻方：對(duì)稱法單偶數(shù)(4k+2)階幻方：斯特雷奇法（1918）

第20頁(yè)2024年5月5日21（一）幻方存在性問(wèn)題

例1.1證實(shí)了不存在2階幻方。對(duì)其余正整數(shù)n，因?yàn)閚階幻方都能結(jié)構(gòu)出來(lái)，當(dāng)然就證實(shí)了（正整數(shù)）階幻方存在性。第21頁(yè)22例1.1

證實(shí)不存在2階幻方證實(shí)：反證法。假定存在2階幻方，如圖所表示：a1a2a3a4依據(jù)幻方定義，它幻和是5，于是a1+a2=a1+a3=5，可得a2=a3，因?yàn)閍1，a2，a3，a4必定彼此不一樣，所以不可能，矛盾。所以不存在2階幻方。第22頁(yè)2024年5月5日23（二）幻方結(jié)構(gòu)性問(wèn)題（1）奇數(shù)階幻方結(jié)構(gòu)連續(xù)擺放法（delaLoubère法）。規(guī)則為：假定結(jié)構(gòu)n階（n為奇數(shù)）幻方。首先將1放在(n+1)/2列第1行方格中，

然后按照副對(duì)角線方向（即行號(hào)減1，列號(hào)加1）依次把從小到大各個(gè)數(shù)字放入對(duì)應(yīng)方格中。第23頁(yè)2024年5月5日24假如行號(hào)變成0（第1行上面一行），則改成第n行對(duì)應(yīng)列對(duì)應(yīng)方格。假如列號(hào)變成n+1（第n列右面一列），則改成第1列對(duì)應(yīng)行對(duì)應(yīng)方格。假如輪到方格已經(jīng)填有數(shù)字或者到了第0行第n+1列對(duì)應(yīng)方格，則退到前一個(gè)方格正下方方格。

第24頁(yè)25例1.2

利用連續(xù)擺放法結(jié)構(gòu)5階幻方17241815235714164613202210121921311182529即行號(hào)減1，列號(hào)加1第25頁(yè)26（2）偶數(shù)階幻方結(jié)構(gòu)

當(dāng)n=4k時(shí)候，即雙偶數(shù)情況，對(duì)稱法。先把n×n方陣分成上、下、左、右四個(gè)2k×2k方陣。然后對(duì)于左上2k×2k方陣進(jìn)行處理，每行每列任意取二分之一（k個(gè)）方格做標(biāo)識(shí)，如我們把這些方格涂成陰影。第26頁(yè)27然后按照對(duì)稱軸將這種標(biāo)識(shí)方式向下和向右作對(duì)稱圖形。經(jīng)過(guò)處理后使得n×n方陣每一行和每一列都有二分之一（n/2）方格被涂成陰影。接下來(lái)，把從1開(kāi)始數(shù)字依次往方格里面填。第一遍：從第1行第1列方格開(kāi)始往右，不是陰影，則填數(shù)字，假如是陰影方格，不填數(shù)字，但對(duì)應(yīng)數(shù)字加1。第1行填完后，是第2行第1列方格，依次，最終是第n行第n列方格。第27頁(yè)28這么填完之后，有二分之一方格被填上了數(shù)字。第二遍，從第n行第n列方格開(kāi)始依次往左，規(guī)則同前，從1開(kāi)始數(shù)字依次往方格里面填。第n行結(jié)束之后，是第n-1行第n列方格。依次，最終是第1行第1列方格。最終就得到了幻方。第28頁(yè)2024年5月5日29例1.3

利用對(duì)稱法結(jié)構(gòu)4階幻方

2143158125921171431061513812116594第29頁(yè)30

當(dāng)n=4k+2,所謂單偶數(shù)情況。首先把n×n方陣分成上、下、左、右四個(gè)(2k+1)×(2k+1)方陣,為了表示方便，依次把左上、右下、右上、左下方陣編號(hào)為A,B,C,D。采取連續(xù)擺數(shù)法，把1～(2k+1)2放在A中做成第一個(gè)幻方；把(2k+1)2

＋1～2(2k+1)2放在B中成第二個(gè)幻方。第30頁(yè)31

把2(2k+1)2＋1～3(2k+1)2放在C中成第三個(gè)幻方。把3(2k+1)2＋1～4(2k+1)2放在D中成第四個(gè)幻方。然后，在A各行從第1列開(kāi)始向右取m個(gè)(m=(n-2)/4)方格，但中間一行（k+1行）從第2列開(kāi)始。第31頁(yè)

把這些方格中數(shù)字與D中對(duì)應(yīng)位置數(shù)字對(duì)換。在C中各行最終一列右起向左各取m－1個(gè)方格，把這些方格中數(shù)字與B中對(duì)應(yīng)位置數(shù)字對(duì)換。最終，就得到了幻方。32第32頁(yè)33例1.4結(jié)構(gòu)6階幻方

159283267233342621221712192327101483435303629131831242520151611ACDBm=1第33頁(yè)34132928567233342621221712192327101435331830362913184242520151611第34頁(yè)35（三）幻方計(jì)數(shù)問(wèn)題

3階幻方基本形式只有一個(gè)經(jīng)過(guò)旋轉(zhuǎn)和翻轉(zhuǎn)可取得8種變形

166185775392294第35頁(yè)

4階幻方分類枚舉基本形式有880個(gè)變形有7040個(gè)第36頁(yè)

5階幻方基本形式有275305224個(gè)

6階及以上幻方即使經(jīng)過(guò)大型計(jì)算機(jī)計(jì)算依然難以取得準(zhǔn)確數(shù)字，當(dāng)前只能預(yù)計(jì)出它取值范圍372024年5月5日第37頁(yè)§1.2拉丁方問(wèn)題2024年5月5日38拉丁方是另一類經(jīng)典組合數(shù)學(xué)問(wèn)題n階拉丁方定義為由數(shù)字1,2,…,n組成n×n方陣，使得在每1行、每1列中每個(gè)數(shù)字都恰好出現(xiàn)1次。第38頁(yè)拉丁方存在性問(wèn)題

2024年5月5日39

2階拉丁方是存在1221第39頁(yè)2024年5月5日40n階拉丁方是存在

結(jié)構(gòu)方法以下：第1行為（1,2,3…,n）第2行是(2,3,…,n,1)，…第k行為(k,k+1,…,n,1,…,k-1)，…，第n行為（n,…,3,2,1）。

第40頁(yè)41例1.5

設(shè)計(jì)一個(gè)藥品臨床試驗(yàn)以測(cè)試五種藥品對(duì)人體藥效。這五種藥品編號(hào)1,2,3,4,5。然后選取5個(gè)人，并給每人不一樣藥。為了消除個(gè)體對(duì)藥品反應(yīng)偏差，要求在連續(xù)5天里進(jìn)行測(cè)試，每人天天吃一個(gè)藥品。而為了消除服藥時(shí)間造成藥效偏差，要求2個(gè)人不能在同1天吃相同藥。

第41頁(yè)42最終滿足要求試驗(yàn)是要形成由1,2,3,4,5組成5×5方陣，其中每行每列中沒(méi)有相同數(shù)字，即5階拉丁方結(jié)構(gòu)問(wèn)題。第42頁(yè)432345134512451235123412345行（人）列（天）第43頁(yè)例36軍官問(wèn)題有36名軍官來(lái)自六個(gè)不一樣團(tuán)，含有六種不一樣軍銜，而且每個(gè)團(tuán)每種軍銜軍官各有一名，能否把他們排成一個(gè)6

6方陣，使得對(duì)每一個(gè)團(tuán)與每一個(gè)軍銜，在每一行或每一列都有一位軍官來(lái)自這個(gè)團(tuán)，也都有一位軍官有此軍銜？是由Euler首先提出，實(shí)際上是組合設(shè)計(jì)中正交拉丁方問(wèn)題，屬于結(jié)構(gòu)問(wèn)題。猜測(cè)？6、10、。。。。第44頁(yè)將這36名軍官排成6×6方陣,使得

1)每行每列都有任一軍團(tuán)軍官2)每行每列都有任一軍銜軍官.i:軍銜,j:軍團(tuán),軍官對(duì)應(yīng)數(shù)偶(i,j),i,j[1,6]問(wèn)題等價(jià)于結(jié)構(gòu)數(shù)偶(i,j)排成6階方陣,使得

1)數(shù)偶第一個(gè)數(shù)字組成拉丁方;2)數(shù)偶第二個(gè)數(shù)字組成拉丁方;3)每個(gè)數(shù)偶只出現(xiàn)一次.第45頁(yè)兩個(gè)拉丁方稱為相互正交，即正交拉丁方.

定義:設(shè)A=(aij)n×n,B=(bij)n×n是兩個(gè)n×n拉丁方.

令C=((aij,bij))n×n,若Cn2對(duì)數(shù)偶互不相同,則稱A與B正交.第46頁(yè)上述是兩個(gè)3階正交拉丁方。2階哪？

36軍官問(wèn)題即不存在6階正交拉丁方。

>6猜測(cè)不對(duì)。對(duì)于只有9個(gè)軍官類似問(wèn)題有解：第47頁(yè)48§1.3涂色問(wèn)題

在實(shí)際應(yīng)用中，很多計(jì)數(shù)問(wèn)題都可抽象成涂色問(wèn)題。作為經(jīng)典組累計(jì)數(shù)問(wèn)題，依據(jù)涂色問(wèn)題難度不一樣，將反應(yīng)出各種不一樣計(jì)數(shù)技術(shù)。第48頁(yè)49例1.6

對(duì)正三角形三個(gè)頂點(diǎn)涂以紅、藍(lán)（r和b）兩種顏色，求有多少種不一樣涂色方案？

解因?yàn)橹挥袃煞N顏色，我們能夠采取枚舉方法分類討論。第49頁(yè)50涂色方案可分成四類：（1）三點(diǎn)全涂紅色，只有一個(gè)方案rrr（2）三點(diǎn)全涂藍(lán)色，只有一個(gè)方案bbb（3）兩點(diǎn)涂紅色，一點(diǎn)涂藍(lán)色，因藍(lán)色可分別涂于三個(gè)頂點(diǎn)之一，故有3種方案brr，rbr，rrb（4）由對(duì)稱性可知，兩點(diǎn)涂藍(lán)色，一點(diǎn)染紅方案也有3種：第50頁(yè)51紅色,藍(lán)色第51頁(yè)