《組合數(shù)學(xué)》課件PPT

組合數(shù)學(xué)課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT 組合數(shù)學(xué)Combinatorics吉林大學(xué) 軟件學(xué)院2012年3月關(guān)于教材關(guān)于教材內(nèi)部試用自編版本內(nèi)部試用自編版本l清華（研究生清華（研究生48學(xué)時(shí)）北大學(xué)時(shí)長(zhǎng)，教材難學(xué)時(shí)）北大學(xué)時(shí)長(zhǎng)，教材難l國(guó)外教材深，講解比較詳細(xì)，適合做參考書目國(guó)外教材深，講解比較詳細(xì)，適合做參考書目新版特點(diǎn)新版特點(diǎn)l內(nèi)容組織編排比較適宜內(nèi)容組織編排比較適宜l例題新穎，題型涵蓋知識(shí)點(diǎn)例題新穎，題型涵蓋知識(shí)點(diǎn)教材購(gòu)買事宜教材購(gòu)買事宜l討論討論組合數(shù)學(xué)概述組合數(shù)學(xué)概述組合數(shù)學(xué)組合數(shù)學(xué)組合數(shù)學(xué)組合數(shù)學(xué)(簡(jiǎn)稱組合學(xué)）是數(shù)學(xué)的一個(gè)分支簡(jiǎn)稱組合學(xué)）是數(shù)學(xué)的一個(gè)分支簡(jiǎn)稱組合學(xué)）是數(shù)學(xué)的一個(gè)分支簡(jiǎn)稱組合學(xué)）是數(shù)學(xué)的一個(gè)分支,它它它它起源于古代的娛樂和休閑。起源于古代的娛樂和休閑。起源于古代的娛樂和休閑。起源于古代的娛樂和休閑?，F(xiàn)代數(shù)學(xué)可以分為兩大類：一類是研究連續(xù)對(duì)現(xiàn)代數(shù)學(xué)可以分為兩大類：一類是研究連續(xù)對(duì)象的，如分析、方程等，另一類就是研究離散象的，如分析、方程等，另一類就是研究離散對(duì)象的對(duì)象的離散離散數(shù)學(xué)。數(shù)學(xué)。組合數(shù)學(xué)可以說是離散數(shù)學(xué)的分支，而圖論又組合數(shù)學(xué)可以說是離散數(shù)學(xué)的分支，而圖論又組合數(shù)學(xué)可以說是離散數(shù)學(xué)的分支，而圖論又組合數(shù)學(xué)可以說是離散數(shù)學(xué)的分支，而圖論又是組合數(shù)學(xué)的一個(gè)分支是組合數(shù)學(xué)的一個(gè)分支是組合數(shù)學(xué)的一個(gè)分支是組合數(shù)學(xué)的一個(gè)分支1666年萊布尼茲發(fā)表年萊布尼茲發(fā)表“論組合數(shù)學(xué)論組合數(shù)學(xué)”，這是組，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合學(xué)合數(shù)學(xué)的第一部專著。書中首次使用了組合學(xué)(Combinatorics)一詞。一詞。什么是組合數(shù)學(xué)什么是組合數(shù)學(xué)組合數(shù)學(xué)是研究組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計(jì)數(shù)、構(gòu)造離散結(jié)構(gòu)的存在、計(jì)數(shù)、構(gòu)造和優(yōu)化和優(yōu)化等問題的一門學(xué)科。等問題的一門學(xué)科。組合數(shù)學(xué)就是研究按照一定的規(guī)則來安排一些組合數(shù)學(xué)就是研究按照一定的規(guī)則來安排一些離散個(gè)體的問題。它涉及面廣，內(nèi)容龐雜（涉離散個(gè)體的問題。它涉及面廣，內(nèi)容龐雜（涉及到組合分析、圖論、組合算法、近代密碼學(xué)、及到組合分析、圖論、組合算法、近代密碼學(xué)、編碼理論等），并且仍在編碼理論等），并且仍在很快地發(fā)展很快地發(fā)展著，因而著，因而還還沒有一個(gè)統(tǒng)一而有效的理論體系沒有一個(gè)統(tǒng)一而有效的理論體系。研究的對(duì)象是離散結(jié)構(gòu)，一般可以用研究的對(duì)象是離散結(jié)構(gòu)，一般可以用1，2，、，、，、，n表示。表示。本書僅限于討論本書僅限于討論n是有限的自是有限的自然數(shù)的情況。然數(shù)的情況。組合數(shù)學(xué)與計(jì)算機(jī)科學(xué)的關(guān)系組合數(shù)學(xué)與計(jì)算機(jī)科學(xué)的關(guān)系計(jì)算機(jī)科學(xué)就是算法的科學(xué)，而計(jì)算機(jī)所處理計(jì)算機(jī)科學(xué)就是算法的科學(xué)，而計(jì)算機(jī)所處理的對(duì)象是離散的數(shù)據(jù)，所以離散對(duì)象的處理就的對(duì)象是離散的數(shù)據(jù)，所以離散對(duì)象的處理就成了計(jì)算機(jī)科學(xué)的核心，而研究離散對(duì)象的科成了計(jì)算機(jī)科學(xué)的核心，而研究離散對(duì)象的科學(xué)恰恰就是組合數(shù)學(xué)。學(xué)恰恰就是組合數(shù)學(xué)。微積分和近代數(shù)學(xué)的發(fā)展為近代的工業(yè)革命奠微積分和近代數(shù)學(xué)的發(fā)展為近代的工業(yè)革命奠定了基礎(chǔ)。而組合數(shù)學(xué)的發(fā)展則是奠定了計(jì)算定了基礎(chǔ)。而組合數(shù)學(xué)的發(fā)展則是奠定了計(jì)算機(jī)革命的基礎(chǔ)。機(jī)革命的基礎(chǔ)。組合數(shù)學(xué)與計(jì)算機(jī)科學(xué)的關(guān)系組合數(shù)學(xué)與計(jì)算機(jī)科學(xué)的關(guān)系 組合數(shù)學(xué)與計(jì)算機(jī)科學(xué)相輔相成。組合數(shù)學(xué)與計(jì)算機(jī)科學(xué)相輔相成。一方面，當(dāng)我們研究的一方面，當(dāng)我們研究的組合問題規(guī)模很大組合問題規(guī)模很大的時(shí)候，計(jì)算量會(huì)很大，計(jì)算機(jī)為求解這些的時(shí)候，計(jì)算量會(huì)很大，計(jì)算機(jī)為求解這些問題提供了有力手段。問題提供了有力手段。另一方面，在另一方面，在計(jì)算機(jī)科學(xué)的算法研究中計(jì)算機(jī)科學(xué)的算法研究中,要進(jìn)行算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析，要進(jìn)行算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析，要用到組合數(shù)學(xué)的知識(shí)，因此，組合數(shù)學(xué)理要用到組合數(shù)學(xué)的知識(shí)，因此，組合數(shù)學(xué)理論也為計(jì)算機(jī)的算法設(shè)計(jì)提供理論支持。論也為計(jì)算機(jī)的算法設(shè)計(jì)提供理論支持。組合數(shù)學(xué)的其他應(yīng)用組合數(shù)學(xué)的其他應(yīng)用 組合數(shù)學(xué)不僅在軟件技術(shù)中有重要的應(yīng)用價(jià)組合數(shù)學(xué)不僅在軟件技術(shù)中有重要的應(yīng)用價(jià)值，在值，在企業(yè)管理，交通規(guī)劃，戰(zhàn)爭(zhēng)指揮，金融企業(yè)管理，交通規(guī)劃，戰(zhàn)爭(zhēng)指揮，金融分析等分析等領(lǐng)域都有重要的應(yīng)用。領(lǐng)域都有重要的應(yīng)用。在美國(guó)有一家用組合數(shù)學(xué)命名的公司，他在美國(guó)有一家用組合數(shù)學(xué)命名的公司，他們用組合數(shù)學(xué)的方法來提高企業(yè)管理的效益，們用組合數(shù)學(xué)的方法來提高企業(yè)管理的效益，這家公司辦得非常成功這家公司辦得非常成功 德國(guó)一位著名組合數(shù)學(xué)家利用組合數(shù)學(xué)方德國(guó)一位著名組合數(shù)學(xué)家利用組合數(shù)學(xué)方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費(fèi)用，引起了制藥業(yè)的關(guān)注。費(fèi)用，引起了制藥業(yè)的關(guān)注。組合數(shù)學(xué)前景組合數(shù)學(xué)前景 吳文俊院士吳文俊院士 每個(gè)時(shí)代都有它特殊的要求，使得數(shù)學(xué)出每個(gè)時(shí)代都有它特殊的要求，使得數(shù)學(xué)出現(xiàn)一個(gè)新的面貌，產(chǎn)生一些新的數(shù)學(xué)分支，現(xiàn)一個(gè)新的面貌，產(chǎn)生一些新的數(shù)學(xué)分支，組合數(shù)學(xué)這個(gè)新的分支也是在時(shí)代的要求下組合數(shù)學(xué)這個(gè)新的分支也是在時(shí)代的要求下產(chǎn)生的。產(chǎn)生的。信息技術(shù)很可能會(huì)給數(shù)學(xué)本身帶來一場(chǎng)根信息技術(shù)很可能會(huì)給數(shù)學(xué)本身帶來一場(chǎng)根本性的變革，而組合數(shù)學(xué)則將顯示出它的重本性的變革，而組合數(shù)學(xué)則將顯示出它的重要作用。要作用。組合數(shù)學(xué)中的著名問題組合數(shù)學(xué)中的著名問題地圖著色問題地圖著色問題：對(duì)世界地圖著色，每一個(gè)國(guó)家使用一種顏：對(duì)世界地圖著色，每一個(gè)國(guó)家使用一種顏色。如果要求相鄰國(guó)家的顏色相異，是否總共只需四種顏色。如果要求相鄰國(guó)家的顏色相異，是否總共只需四種顏色？這是色？這是圖論圖論問題。問題。船夫過河問題船夫過河問題：船夫要把一匹狼、一只羊和一棵白菜運(yùn)過：船夫要把一匹狼、一只羊和一棵白菜運(yùn)過河。只要船夫不在場(chǎng)，羊就會(huì)吃白菜、狼就會(huì)吃羊。船夫河。只要船夫不在場(chǎng)，羊就會(huì)吃白菜、狼就會(huì)吃羊。船夫的船每次只能運(yùn)送一種東西。怎樣把所有東西都運(yùn)過河？的船每次只能運(yùn)送一種東西。怎樣把所有東西都運(yùn)過河？這是這是線性規(guī)劃線性規(guī)劃問題。問題。中國(guó)郵差問題中國(guó)郵差問題：由中國(guó)組合數(shù)學(xué)家：由中國(guó)組合數(shù)學(xué)家管梅谷管梅谷教授提出。郵遞教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個(gè)最短？這不是一個(gè)NPNP完全完全問題，存在多項(xiàng)式復(fù)雜度算法：?jiǎn)栴}，存在多項(xiàng)式復(fù)雜度算法：先求出度為奇數(shù)的點(diǎn)，用匹配算法算出這些點(diǎn)間的連接方先求出度為奇數(shù)的點(diǎn)，用匹配算法算出這些點(diǎn)間的連接方式，然后再用式，然后再用歐拉路徑歐拉路徑算法求解。這也是算法求解。這也是圖論圖論問題。問題。任務(wù)分配問題任務(wù)分配問題（也稱（也稱婚配問題婚配問題）：有一些員工要完成一些）：有一些員工要完成一些任務(wù)。各個(gè)員工完成不同任務(wù)所花費(fèi)的時(shí)間都不同。每個(gè)任務(wù)。各個(gè)員工完成不同任務(wù)所花費(fèi)的時(shí)間都不同。每個(gè)員工只分配一項(xiàng)任務(wù)。每項(xiàng)任務(wù)只被分配給一個(gè)員工。怎員工只分配一項(xiàng)任務(wù)。每項(xiàng)任務(wù)只被分配給一個(gè)員工。怎樣分配員工與任務(wù)以使所花費(fèi)的時(shí)間最少？這是樣分配員工與任務(wù)以使所花費(fèi)的時(shí)間最少？這是線性規(guī)劃線性規(guī)劃的問題。的問題。如何構(gòu)造如何構(gòu)造幻方幻方。生活中的組合數(shù)學(xué)問題生活中的組合數(shù)學(xué)問題當(dāng)你裝一個(gè)箱子時(shí)，你會(huì)發(fā)現(xiàn)要使箱子盡可能裝滿不是一件很容易的事，你往往需要做些調(diào)整。航空調(diào)度和航班的設(shè)定。怎樣確定各個(gè)航班以滿足不同旅客轉(zhuǎn)機(jī)的需要，同時(shí)也使得每個(gè)機(jī)場(chǎng)的航班起落分布合理。此外，在一些航班有延誤等特殊情況下，怎樣作最合理的調(diào)整。對(duì)于城市的交通管理，交通規(guī)劃，哪些地方可能是阻塞要地，哪些地方應(yīng)該設(shè)單行道，立交橋建在哪里最合適，紅綠燈怎樣設(shè)定最合理。一個(gè)通訊網(wǎng)絡(luò)怎樣布局最節(jié)??？美國(guó)的貝爾實(shí)驗(yàn)室和IBM公司都有世界一流的組合數(shù)學(xué)家在研究這個(gè)問題，這個(gè)問題直接關(guān)系到巨大的經(jīng)濟(jì)利益。假日飯店的管理中，也嚴(yán)格規(guī)定了有關(guān)的工序，如清潔工的第一步是換什么，清洗什么，第二步又做什么，總之，他進(jìn)出房間的次數(shù)應(yīng)該最少。既然，這樣一個(gè)簡(jiǎn)單的工作都需要講究工序，那么一個(gè)復(fù)雜的工程就更不用說了。庫(kù)房和運(yùn)輸?shù)墓芾硪彩堑湫偷慕M合數(shù)學(xué)問題。怎樣安排運(yùn)輸使得庫(kù)房充分發(fā)揮作用，進(jìn)一步來說，貨物放在什么地方最便于存取（如存儲(chǔ)時(shí)間短的應(yīng)該放在容易存取的地方）。一定要學(xué)組合數(shù)學(xué)一定要學(xué)組合數(shù)學(xué)組合數(shù)學(xué)是組合數(shù)學(xué)是計(jì)算復(fù)雜性理論計(jì)算復(fù)雜性理論、算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析的基礎(chǔ)課。的基礎(chǔ)課。練腦課程練腦課程組合分析和組合算法已經(jīng)被廣泛應(yīng)組合分析和組合算法已經(jīng)被廣泛應(yīng)用在計(jì)算機(jī)科學(xué)、管理科學(xué)、信息用在計(jì)算機(jī)科學(xué)、管理科學(xué)、信息科學(xué)、電子工程、人工智能、生命科學(xué)、電子工程、人工智能、生命科學(xué)等諸多領(lǐng)域中?？茖W(xué)等諸多領(lǐng)域中。怎樣學(xué)好組合數(shù)學(xué)怎樣學(xué)好組合數(shù)學(xué)組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是最主要的方法是計(jì)數(shù)時(shí)的合理分類和組合計(jì)數(shù)時(shí)的合理分類和組合模型的轉(zhuǎn)換模型的轉(zhuǎn)換（一一對(duì)應(yīng)）。（一一對(duì)應(yīng)）。要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。，也要進(jìn)行相當(dāng)?shù)挠?xùn)練?？蓮囊?guī)模小的模型著手，從中找到規(guī)律性可從規(guī)模小的模型著手，從中找到規(guī)律性的東西，再推及一般。的東西，再推及一般。你解決的問題越多，那么你能夠解決下一你解決的問題越多，那么你能夠解決下一個(gè)問題的可能性也越大個(gè)問題的可能性也越大。成績(jī)考核平時(shí)考查l課堂隨堂考試4次 共20分l課后作業(yè) 共30分課程結(jié)束后考試l閉卷2小時(shí) 20分2022年10月11日1314 組合數(shù)學(xué)的主要問題組合數(shù)學(xué)的主要問題（1）存在性問題）存在性問題滿足一定條件的安排的存在性滿足一定條件的安排的存在性.如果某如果某種安排不一定總存在，我們就需要研種安排不一定總存在，我們就需要研究存在的條件。究存在的條件。存在性是數(shù)學(xué)研究最重要的問題之一存在性是數(shù)學(xué)研究最重要的問題之一.許多許多問題的存在性至今也無(wú)法解決？問題的存在性至今也無(wú)法解決？例如數(shù)論中很多難題：哥德巴赫猜想例如數(shù)論中很多難題：哥德巴赫猜想（2）安排的枚舉、分類和計(jì)數(shù)）安排的枚舉、分類和計(jì)數(shù) 如果所要求的安排存在，則可能有多如果所要求的安排存在，則可能有多種不同的安排。此時(shí)，需要計(jì)數(shù)不同種不同的安排。此時(shí)，需要計(jì)數(shù)不同的方案數(shù)，并將它們進(jìn)行枚舉和分類。的方案數(shù)，并將它們進(jìn)行枚舉和分類。當(dāng)實(shí)際問題比較復(fù)雜的時(shí)候，必須有好的當(dāng)實(shí)際問題比較復(fù)雜的時(shí)候，必須有好的數(shù)學(xué)方法來解決數(shù)學(xué)方法來解決.（3）構(gòu)造性問題）構(gòu)造性問題 一個(gè)組合問題，如果已經(jīng)判定解是一個(gè)組合問題，如果已經(jīng)判定解是存在的，那么將所有可能的安排構(gòu)存在的，那么將所有可能的安排構(gòu)造出來是一個(gè)關(guān)鍵問題。造出來是一個(gè)關(guān)鍵問題。與計(jì)算機(jī)算法密切相關(guān)與計(jì)算機(jī)算法密切相關(guān) 典型問題：組合設(shè)計(jì)典型問題：組合設(shè)計(jì)（4）優(yōu)化問題）優(yōu)化問題在給定的優(yōu)化條件下從所有的安排在給定的優(yōu)化條件下從所有的安排方案中找出最優(yōu)的安排方案。方案中找出最優(yōu)的安排方案。l最短路徑問題最短路徑問題與算法分析密切相關(guān)與算法分析密切相關(guān)本學(xué)期涉及到的內(nèi)容：本學(xué)期涉及到的內(nèi)容：鴿巢原理和鴿巢原理和Ramsey定理（存在性問題）定理（存在性問題）基本計(jì)數(shù)方法基本計(jì)數(shù)方法容斥原理容斥原理生成函數(shù)生成函數(shù)遞推關(guān)系遞推關(guān)系Plya定理19幻方問題幻方問題有趣的數(shù)學(xué)游戲有趣的數(shù)學(xué)游戲 幻方在娛樂數(shù)學(xué)中的地位以及它的意義幻方在娛樂數(shù)學(xué)中的地位以及它的意義非同一般，它是中國(guó)人的首創(chuàng)。非同一般，它是中國(guó)人的首創(chuàng)。公元前公元前22002200年年易經(jīng)易經(jīng)提到提到洛書洛書與與河圖河圖 1.1 幻方問題幻方問題一個(gè)n階幻方是由整數(shù)1，2，3，n2按下述方式組成的nn方陣：該方陣每行上的整數(shù)的和、每列上的整數(shù)的和以及兩條對(duì)角線中每條對(duì)角線上的整數(shù)的和都等于同一個(gè)數(shù)s 20 3階幻方的所有整數(shù)和為階幻方的所有整數(shù)和為15；每一行（或列或?qū)蔷€）數(shù)字的和稱為每一行（或列或?qū)蔷€）數(shù)字的和稱為幻方的和（幻和）：幻方的和（幻和）：S=n(n2+1)/2。關(guān)于幻方的問題歸結(jié)為關(guān)于幻方的問題歸結(jié)為（一）存在性問題（一）存在性問題 對(duì)任意的正整數(shù)對(duì)任意的正整數(shù)n，n階幻方存在嗎？階幻方存在嗎？（二）組合計(jì)數(shù)問題（二）組合計(jì)數(shù)問題 如果存在，那么應(yīng)該有多少個(gè)不同的如果存在，那么應(yīng)該有多少個(gè)不同的 n階幻方。階幻方。（三）構(gòu)造問題（三）構(gòu)造問題 奇數(shù)階幻方：連續(xù)擺數(shù)法奇數(shù)階幻方：連續(xù)擺數(shù)法(de La Loubre法法)雙偶數(shù)（雙偶數(shù)（4k）階幻方：對(duì)稱法）階幻方：對(duì)稱法 單偶數(shù)單偶數(shù)(4k+2)階幻方：斯特雷奇法（階幻方：斯特雷奇法（1918）（四）（四）優(yōu)化優(yōu)化問題問題 在構(gòu)造出的幻方中，哪個(gè)最優(yōu)在構(gòu)造出的幻方中，哪個(gè)最優(yōu) 2022年10月11日22（一）幻方的存在性問題（一）幻方的存在性問題 例1.1 證明了不存在2階幻方。對(duì)其余的正整數(shù)n，由于n階幻方都能構(gòu)造出來，當(dāng)然就證明了（正整數(shù)）階幻方的存在性。23例例 1.1 證明不存在證明不存在2階幻方階幻方證明：證明：反證法。假定存在2階幻方，如圖所示：a1a2a3a4根據(jù)幻方的定義，它的幻和是5，于是a1+a2=a1+a3=5，可得a2=a3，因?yàn)閍1，a2，a3，a4必定彼此不同，所以不可能，矛盾。因此不存在2階幻方。2022年10月11日24（二）（二）幻方的構(gòu)造性問題幻方的構(gòu)造性問題（1）奇數(shù)階幻方的構(gòu)造）奇數(shù)階幻方的構(gòu)造連續(xù)擺放法（連續(xù)擺放法（de la Loubre法）。法）。規(guī)則為：規(guī)則為：假定構(gòu)造假定構(gòu)造n階（階（n為奇數(shù)）幻方為奇數(shù)）幻方。首先首先將將1放在放在(n+1)/2列第列第1行的方格中，行的方格中，然后然后按照副對(duì)角線方向（即行號(hào)減按照副對(duì)角線方向（即行號(hào)減1，列號(hào)加列號(hào)加1）依次把從小到大的各個(gè)數(shù)字放）依次把從小到大的各個(gè)數(shù)字放入相應(yīng)的方格中。入相應(yīng)的方格中。2022年10月11日25 如果行號(hào)變成如果行號(hào)變成0（第（第1行上面一行），行上面一行），則改成第則改成第n行相應(yīng)列對(duì)應(yīng)的方格。行相應(yīng)列對(duì)應(yīng)的方格。如果列號(hào)變成如果列號(hào)變成n+1（第（第n列右面一列），列右面一列），則改成第則改成第1列相應(yīng)行對(duì)應(yīng)的方格。列相應(yīng)行對(duì)應(yīng)的方格。如果輪到的方格已經(jīng)填有數(shù)字或者到如果輪到的方格已經(jīng)填有數(shù)字或者到了第了第0行第行第n+1列對(duì)應(yīng)的方格，則退到前列對(duì)應(yīng)的方格，則退到前一個(gè)方格正下方的方格。一個(gè)方格正下方的方格。26例例1.2 利用連續(xù)擺放法構(gòu)造5階幻方 1724181523571416461320221012192131118252927（2）偶數(shù)階幻方的構(gòu)造）偶數(shù)階幻方的構(gòu)造 當(dāng)當(dāng)n=4k的時(shí)候，即雙偶數(shù)的情況的時(shí)候，即雙偶數(shù)的情況，對(duì)稱法。對(duì)稱法。先把先把nn的方陣分成上、下、左、右的方陣分成上、下、左、右四個(gè)四個(gè)2k2k的方陣。的方陣。然后對(duì)于左上的然后對(duì)于左上的2k2k方陣進(jìn)行處理，方陣進(jìn)行處理，每行每列任意取一半（每行每列任意取一半（k個(gè)）的方格個(gè)）的方格做標(biāo)記，如我們把這些方格涂成陰影。做標(biāo)記，如我們把這些方格涂成陰影。28 然后按照對(duì)稱軸將這種標(biāo)記方式向下和向然后按照對(duì)稱軸將這種標(biāo)記方式向下和向右作對(duì)稱圖形。經(jīng)過處理后使得右作對(duì)稱圖形。經(jīng)過處理后使得nn的方陣的方陣的每一行和每一列都有一半（的每一行和每一列都有一半（n/2）的方格被）的方格被涂成陰影。涂成陰影。接下來，把從接下來，把從1開始的數(shù)字依次往方格里開始的數(shù)字依次往方格里面填。第一遍：從第面填。第一遍：從第1行第行第1列的方格開始往列的方格開始往右，不是陰影，則填數(shù)字，如果是陰影的方右，不是陰影，則填數(shù)字，如果是陰影的方格，不填數(shù)字，但相應(yīng)的數(shù)字加格，不填數(shù)字，但相應(yīng)的數(shù)字加1。第。第1行填行填完后，是第完后，是第2行第行第1列的方格，依次，最后是列的方格，依次，最后是第第n行第行第n列的方格。列的方格。29 這樣填完之后，有一半的方格被填這樣填完之后，有一半的方格被填上了數(shù)字。上了數(shù)字。第二遍，從第第二遍，從第n行第行第n列的方格開始列的方格開始依次往左，規(guī)則同前，從依次往左，規(guī)則同前，從1開始的數(shù)字開始的數(shù)字依次往方格依次往方格里面填。第填。第n行結(jié)束之后，行結(jié)束之后，是第是第n-1行第行第n列的方格。依次，最后列的方格。依次，最后是第是第1行第行第1列的方格。列的方格。最后就得到了幻方。最后就得到了幻方。2022年10月11日30 例例1.3 利用對(duì)稱法構(gòu)造利用對(duì)稱法構(gòu)造4階幻方階幻方 214315812592117143106151381211659431 當(dāng)當(dāng)n=4k+2,所謂的單偶數(shù)的情況所謂的單偶數(shù)的情況。首先把首先把nn的方陣分成上、下、左、的方陣分成上、下、左、右四個(gè)右四個(gè)(2k+1)(2k+1)的方陣的方陣,為了表達(dá)為了表達(dá)方便，依次把左上、右下、右上、左下方便，依次把左上、右下、右上、左下的方陣編號(hào)為的方陣編號(hào)為A,B,C,D。采用連續(xù)擺數(shù)法，把采用連續(xù)擺數(shù)法，把1(2k+1)2放在放在A中做成第一個(gè)幻方；把中做成第一個(gè)幻方；把(2k+1)2 12(2k+1)2放在放在B中成第二個(gè)幻方。中成第二個(gè)幻方。32 把把2(2k+1)213(2k+1)2放在放在C中成第三個(gè)幻方。中成第三個(gè)幻方。把把3(2k+1)214(2k+1)2放在放在D中成第四個(gè)幻方。中成第四個(gè)幻方。然后，在然后，在A的各行從第的各行從第1列開始向列開始向右取右取m個(gè)個(gè)(m=(n-2)/4)方格，但中間方格，但中間一行（一行（k+1行）從第行）從第2列開始。列開始。把這些方格中的數(shù)字與把這些方格中的數(shù)字與D中相應(yīng)位中相應(yīng)位置的數(shù)字對(duì)換。置的數(shù)字對(duì)換。在在C中各行最后一列右起向左各取中各行最后一列右起向左各取m1個(gè)方格，把這些方格中的數(shù)字與個(gè)方格，把這些方格中的數(shù)字與B中相應(yīng)位置的數(shù)字對(duì)換。最后，就中相應(yīng)位置的數(shù)字對(duì)換。最后，就得到了幻方。得到了幻方。3334例例1.4 構(gòu)造構(gòu)造6階幻方階幻方 1592832672333426212217121923271014834353036 29 13 18312425201516113513292856723334262122171219232710143533183036 29 13 18424252015161136（三）幻方的計(jì)數(shù)問題（三）幻方的計(jì)數(shù)問題 3階幻方階幻方 基本形式只有一種 經(jīng)過旋轉(zhuǎn)和翻轉(zhuǎn)可獲得8種變形 4階幻方階幻方 分類枚舉 基本形式有880個(gè) 變形有7040個(gè) 5 階幻方階幻方 基本形式有275305224個(gè) 6 階及以上幻方階及以上幻方 即使通過大型計(jì)算機(jī)的計(jì)算仍然難以獲得精確的數(shù)字，目前只能估計(jì)出它的取值范圍372022年10月11日1.2 拉丁方問題拉丁方問題2022年10月11日38 拉丁方拉丁方是另一類典型的組合數(shù)學(xué)問是另一類典型的組合數(shù)學(xué)問題題 n階拉丁方階拉丁方定義為由數(shù)字1,2,n構(gòu)成的nn的方陣，使得在每1行、每1列中每個(gè)數(shù)字都恰好出現(xiàn)1次。拉丁方存在性問題拉丁方存在性問題 2022年10月11日39 2階拉丁方是存在的階拉丁方是存在的 12212022年10月11日40n階拉丁方階拉丁方是存在的是存在的 構(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）。41例例1.5 設(shè)計(jì)一個(gè)藥物臨床試驗(yàn)以測(cè)試五設(shè)計(jì)一個(gè)藥物臨床試驗(yàn)以測(cè)試五種藥物對(duì)人體的藥效。這五種藥物種藥物對(duì)人體的藥效。這五種藥物編號(hào)編號(hào)1,2,3,4,5。然后選取。然后選取5個(gè)人，并個(gè)人，并給每人不同的藥。為了消除個(gè)體對(duì)給每人不同的藥。為了消除個(gè)體對(duì)藥物的反應(yīng)偏差，要求在連續(xù)藥物的反應(yīng)偏差，要求在連續(xù)5天里天里進(jìn)行測(cè)試，每人每天吃一種藥物。進(jìn)行測(cè)試，每人每天吃一種藥物。而為了消除服藥時(shí)間造成藥效的偏而為了消除服藥時(shí)間造成藥效的偏差，要求差，要求2個(gè)人不能在同個(gè)人不能在同1 天吃相同天吃相同的藥。的藥。42最后滿足要求的實(shí)驗(yàn)是要形成由1,2,3,4,5構(gòu)成的55的方陣，其中每行每列中沒有相同的數(shù)字，即5階拉丁方的構(gòu)造問題。432345134512451235123412345441.3 涂色問題涂色問題 在實(shí)際應(yīng)用中，很多計(jì)數(shù)問題都可抽象成涂色問題。作為典型的組合計(jì)數(shù)問題，根據(jù)涂色問題難度的不同，將反映出各種不同的計(jì)數(shù)技術(shù)。45例例1.6 對(duì)正三角形的三個(gè)頂點(diǎn)涂以紅、藍(lán)（r和b）兩種顏色，求有多少種不同的涂色方案？解解 由于只有兩種顏色，我們可以采用枚舉方法分類討論。46 涂色方案可分成四類：涂色方案可分成四類：（1）三點(diǎn)全涂紅色，只有一種方案 rrr（2）三點(diǎn)全涂藍(lán)色，只有一種方案 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種：47紅色,藍(lán)色48 如果考慮正三角形可以旋轉(zhuǎn)，則(3),(4),(5)顯然是同一個(gè)涂色方案，(6),(7),(8)也是同一個(gè)涂色方案，這樣涂色方案數(shù)就變成了4種。如果變成了空間的四面體了，即加上空間的旋轉(zhuǎn)之后，涂色方法的計(jì)算將更加復(fù)雜。要涂色的點(diǎn)和可選顏色的數(shù)目如再增加的話，枚舉方法就不奏效了 需要特殊技巧解決問題需要特殊技巧解決問題例例 有有101名選手參加羽毛球比賽，如果采用名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問產(chǎn)生冠軍需要進(jìn)行多少場(chǎng)單循環(huán)淘汰制，問產(chǎn)生冠軍需要進(jìn)行多少場(chǎng)比賽？比賽？方法一：方法一：50+25+13+6+3+2+1=100場(chǎng)比賽 方法二：方法二：由于每場(chǎng)比賽都要產(chǎn)生一個(gè)失敗者，而每個(gè)失敗者只能失敗一次，因此比賽的場(chǎng)數(shù)與失敗者的人數(shù)相等，除冠軍外其他100人都失敗過，因此產(chǎn)生冠軍需要100場(chǎng)比賽。解：解：首先可以看到，通過首先可以看到，通過6 6次是可以完成整個(gè)切割的，次是可以完成整個(gè)切割的，上圖就是這樣的一種方案。其次，我們證明少于上圖就是這樣的一種方案。其次，我們證明少于6 6次次是不能完成切割的。由于處于原立方體中心的一個(gè)小是不能完成切割的。由于處于原立方體中心的一個(gè)小立方體的每個(gè)面都是由切割產(chǎn)生的，每次切割只能產(chǎn)立方體的每個(gè)面都是由切割產(chǎn)生的，每次切割只能產(chǎn)生一個(gè)面，所以切割次數(shù)不能少于它的面數(shù)，因此至生一個(gè)面，所以切割次數(shù)不能少于它的面數(shù)，因此至少少6 6次才能完成切割。次才能完成切割。例例 有一個(gè)邊長(zhǎng)為有一個(gè)邊長(zhǎng)為3的立方的立方體木塊，要把它切割成體木塊，要把它切割成27個(gè)邊長(zhǎng)為個(gè)邊長(zhǎng)為1的小立方體，如的小立方體，如果在切割的過程中可以重果在切割的過程中可以重新排列被切割的木塊，問新排列被切割的木塊，問至少需要多少次才能完成至少需要多少次才能完成任務(wù)？任務(wù)？補(bǔ)充內(nèi)容有n盞燈在一條走廊上排成一列，它們都關(guān)閉著。某人在這一走廊上往返n次。第一次通過走廊時(shí)拉動(dòng)每一盞燈的開關(guān)，然后回到走廊端點(diǎn)處。第二次通過走廊時(shí)拉動(dòng)第二、四、六、盞燈的開關(guān)，再回到走廊端點(diǎn)處。第三次通過走廊時(shí)拉動(dòng)第三、六、九、盞燈的開關(guān)，再回到走廊端點(diǎn)處。如此等等。問此人往返n次后，那些燈的開關(guān)仍然關(guān)閉，哪些燈已經(jīng)亮了。2022年10月11日51分 析考慮第i盞燈(1in)。顯然如果i有k個(gè)因子(包括1和 i)，則第 i 盞燈的開閉狀態(tài)就被改變k次當(dāng)且僅當(dāng)k是偶數(shù)時(shí)第 i 盞燈關(guān)閉，當(dāng)然為k是奇數(shù)時(shí)第 i 盞燈就亮2022年10月11日52分 析 正整數(shù)n的因子個(gè)數(shù)(包括1和n)是奇數(shù)的充分必要條件是n為一個(gè)完全平方數(shù)2022年10月11日53