1、組合數學組合數學主講人:高巧琴In our classes,all the mobile phones should be switched off !The class is begin!課程簡介課程簡介相關課程相關課程數學分析數學分析高等代數高等代數離散數學離散數學 本課程針對計算機科學中的一個重要學科組合數學，組合數學是數學的一個分支，它研究事物在結定模式下的配置，研究這種配置的存在性，所有可能配置的計數和分類以及配置的各種性質。組合數學在計算機科學中有著極其廣泛的應用。 組合學問題求解方法層出不窮、千變萬化，應以理解為基礎，善于總結各種技巧，掌握科學的組織和推理方法。參考教材參考教材:

2、l孫世新編,組合數學,電子科技大學出版;社,2006年l孫淑玲編,組合數學,(第三版)中國科學技術大學出版社,2012年;l盧開澄,盧華明編,組合數學,清華大學出版社,2002年;lRichard A.Brualdi著,馮速等譯,組合數學(第五版),機械工業出版社,2012年. 現代數學可以分為兩大類：一類是研究連續對象的，如分析、方程等；另一類就是研究離散對象的組合數學。 計算機出現以后，由于離散對象的處理是計算機科學的核心，研究離散對象的組合數學得到迅猛發展。 它能夠運用到很多學科，而之前這些學科與數學幾乎沒有關聯。組合數學概述組合數學概述(Combinatorial mathematic

3、s)院士指出，每個時代都有它特殊的要求，使得數學出現一個新的面貌，產生一些新的數學分支，組合數學這個新的分支也是在時代的要求下產生的。 最近,院士又指出，信息技術很可能會給數學本身帶來一場根本性的變革，而組合數學則將顯示出它的重要作用。 組合數學概述組合數學概述(Combinatorial mathematics)教授曾提出要向中國領導人呼吁，組合數學是計算機軟件產業的基礎，中國最終一定能成為一個軟件大國，但是要實現這個目標的一個突破點就是發展組合數學。同志在1998年接見“五四”青年獎章時發表的講話中指出，組合數學不同于傳統的純數學的一個分支，它還是一門應用學科，一門交叉學科。他希望中國的組

4、合數學研究能夠為國家的經濟建設服務。 組合數學概述組合數學概述(Combinatorial mathematics)組合數學概述組合數學概述(Combinatorial mathematics) 另一方面，我們在日常生活中我們常常遇到組合數學的問題。：如果你仔細留心一張世界地圖，你會發現用一種顏色對一個國家著色，那么一共只需要四種顏色就能保證每兩個相鄰的國家的顏色不同。這樣的著色效果能使每一個國家都能清楚地顯示出來。但要證明這個結論確是一個著名的世界難題，最終借助計算機才得以解決，最近人們才發現了一個更簡單的證明。 ：組合數學中有許多象幻方這樣精巧的結構。 1977年美國旅行者1號、2號宇宙飛

5、船就帶上了幻方以作為人類智慧的信號。神 農 幻 方4923578162200BC 1 15 14 412 6 7 9 8 10 11 513 3 2 16 15世紀 階 幻 方組合數學概述組合數學概述(Combinatorial mathematics)：給定來自6種軍銜和6個軍團的36名軍官，能不能把他們排成一個66編隊，使得每一行上和每一列上都滿足每個軍銜有一名軍官且每個軍團有一名軍官呢？ 這個問題是18世紀由瑞典數學家L.Euler提出的一個數學娛樂問題，它對統計學特別是試驗設計等產生重要的影響。組合數學概述組合數學概述(Combinatorial mathematics) 對于城市的交

6、通管理，交通規劃，哪些地方可能是阻塞要地，哪些地方 應該設單行道，立交橋建在哪里最合適，紅綠燈怎樣設定最合理， 如此等等，全是組合數學的問題。 組合數學概述組合數學概述(Combinatorial mathematics)：一個通訊網絡怎樣布局最節省？美國的貝爾實驗室和IBM公司都有世界一流的組合數學家在研究這個問題，這個問題直接關系到巨大的經濟利益。 是一種兩人玩的游戲，玩家雙方對一堆硬幣。假設k堆硬幣，每堆分別為n1,n2,nk枚硬幣。這一游戲的目標目標就是取得最后一枚硬幣。游戲規則如下： 1）玩家輪番出場； 2）當輪到一個玩家取子時，他們都要從選擇的硬幣堆中至少取走一枚硬幣；（這位玩家可

7、以把所選硬幣堆都取走，于是剩下一個空堆，這時它“退出”）當所有的硬幣堆都空了的時候，游戲結束。走最后一步的玩家，即取走最后一枚硬幣的玩家獲勝獲勝。 組合數學概述組合數學概述(Combinatorial mathematics)組合數學概述組合數學概述(Combinatorial mathematics) 總之，組合數學無處不在，它的主要應用就是在各種復雜關系中找出最優的方案。所以組合數學完全可以看成是一門量化的關系學關系學，一門量化了的運籌學運籌學，一門量化了的管理學管理學。 組合數學概述組合數學概述(Combinatorial mathematics) T存在性問題:符合要求的安排是否存在？

8、符合要求的安排是否存在？T計數問題:如有，這種安排有多少種？如有，這種安排有多少種？T構造問題:怎樣作出這些安排？怎樣作出這些安排？T優化問題:當有衡量這種安排的優劣的標準當有衡量這種安排的優劣的標準時，怎樣求出最優安排？時，怎樣求出最優安排？一、組合數學研究什么組合數學概述組合數學概述(Combinatorial mathematics)二、組合數學的主要內容引言引言第第1章章 排列與組合排列與組合 1.1 加法法則和乘法法則 1.2 排列 1.3 組合 1.4 二項式定理 1.5 組合恒等式及其含義 本章小結第第2章章 鴿籠原理與鴿籠原理與容斥原容斥原理理 2.1 鴿籠原理 2.2 容斥原

9、理及其應用本章小結 第第3章章 母函數母函數 3.1 母函數的基本概念 3.2 母函數的基本運算 3.3 在排列組合中的應用 3.4 整數的拆分 本章小結 習題第第4章章 遞推關系遞推關系 4.1 遞推關系的建立 4.2 常系數線性齊次遞推關系 4.3 常系數線性非齊次遞推關系 4.4 迭代法與歸納法 4.5 母函數在遞推關系中的應用本章小結 目目 錄錄 本課程主要內容為組合數學，是一門理論性較強，應用性較廣的課程。因此，通過本課程的學習，使學生熟悉組合計算方法的基本原理和基本方法，掌握常見組合計算的方法，能把一種較難的組合計數問題轉化為一個較易的組合問題，進一步提高組合計算能力。運用組合數學

10、的思想和方法，培養分析問題和解決問題的能力。組合數學概述組合數學概述(Combinatorial mathematics)三、開課目的和要求三、開課目的和要求四、計劃及注意點四、計劃及注意點 把好入門關，牢固掌握基本原理與方法，反復思考，認真體會。解題需要智慧和靈感。組合數學源于實踐用于實踐。 共32課時，第一四章組合數學概述組合數學概述(Combinatorial mathematics) 本章重點介紹以下的基本計數方法：本章重點介紹以下的基本計數方法： 加法法則和乘法法則加法法則和乘法法則 排列排列 組合組合 二項式定理的應用二項式定理的應用 組合恒等式組合恒等式 相互獨立相互獨立的事件的

11、事件 A、B 分別有分別有 k 和和 l 種方法產生，則產生種方法產生，則產生 A 或或 B 的方的方法數為法數為 k+l 種。種。1.1 加法法則1.1 加法法則和乘法法則加法法則和乘法法則1.1.1 加法法則加法法則加法法則加法法則集合論定義集合論定義 若若|A|=k，|B|=l ，且，且AB= ，則則|AB| = k+l 。 設設S是有限集合，若是有限集合，若 ，且，且時，時， ，則有，則有 。ij ijSS 1,miiiSSSS 11mmiiiiSSS 換言之：若集合S可以分解成互不相交的子集1,S之和，則確定S中的事物個數，可以先求出各子集個數，然后相加。2,mSSiS中的事物1.1

12、 加法法則例11.1 加法法則和乘法法則加法法則和乘法法則1.1.1 加法法則加法法則例例 題題例例1、有一所學校給一名數學競賽優勝有一所學校給一名數學競賽優勝者發獎，獎品有三類，第一類是三種者發獎，獎品有三類，第一類是三種不同版本的法漢詞典；第二類是四種不同版本的法漢詞典；第二類是四種不同類型的數學參考書；第三類是二不同類型的數學參考書；第三類是二種不同的獎杯。這位優勝者只能挑選種不同的獎杯。這位優勝者只能挑選一樣獎品。那么，這位優勝者挑選獎一樣獎品。那么，這位優勝者挑選獎品的方法有多少種？品的方法有多少種？解：解：設設S是所有這些獎品的集合，是所有這些獎品的集合，Si是第是第i類獎品的集合

13、類獎品的集合(i=1,2,3)，顯然，顯然，SiSj= (ij) ，根據加法法則有，根據加法法則有iiSSSSS31231| | | |3429 注：注：運用加法法則的技巧是把集合運用加法法則的技巧是把集合S劃分成劃分成的部分。的部分。 若若|A|=k，|B|=l ，A B=(a,b)|aA，bB，則，則|A B| = k l 。1.1 乘法法則1.1 加法法則和乘法法則加法法則和乘法法則1.1.2 乘法法則乘法法則乘法法則乘法法則 相互獨立相互獨立的事件的事件 A、B 分別有分別有 k 和和 l 種方法產生，則選取種方法產生，則選取A以后再選取以后再選取B 的方的方法數為法數為 kl 種。種

14、。集合論定義集合論定義 設設 是有限集合，且是有限集合，且 ，則有，則有 。11mmiiiiSSS 1miiSS (1,2,.,)iS im 12(,.,)|,1,2,.,miia aaaS im 換言之：若集合S是集合1,S2,mSS的事物個數，可以先求出各個集合的直積，則確定S中iS中的事物個數，然后相乘。Si1.1 乘法法則例51.1 加法法則和乘法法則加法法則和乘法法則1.1.2 乘法法則乘法法則例例 題題例例2 由數字由數字1,2,3,4,5可以構成多少個所可以構成多少個所有數字互不相同的四位偶數？有數字互不相同的四位偶數？解：解：所求的是四位偶數，故個位只能選所求的是四位偶數，故個

15、位只能選2或或4，有兩種選，有兩種選擇方法；又由于要求四位數字互不相同，故個位選中后，擇方法；又由于要求四位數字互不相同，故個位選中后，十位只有四種選擇方法；同理，百位、千位分別有三種、十位只有四種選擇方法；同理，百位、千位分別有三種、兩種選擇方法，根據乘法法則，四位數互不相同的偶數兩種選擇方法，根據乘法法則，四位數互不相同的偶數個數為個數為2 4 3 2=481.1 乘法法則例61.1 加法法則和乘法法則加法法則和乘法法則1.1.2 乘法法則乘法法則例例 題題例例3 求出從求出從8個計算機系的學生、個計算機系的學生、 9個個數學系的學生和數學系的學生和10個經濟系的學生中個經濟系的學生中選出

16、兩個不同專業的學生的方法數。選出兩個不同專業的學生的方法數。解：解：由乘法法則有由乘法法則有選一個計算機系和一個數學系的方法數為選一個計算機系和一個數學系的方法數為89=72選一個數學系和一個經濟系的方法數為選一個數學系和一個經濟系的方法數為910=90選一個經濟系和一個計算機系的方法數為選一個經濟系和一個計算機系的方法數為108=80由加法法則，符合要求的方法數為由加法法則，符合要求的方法數為72+90+80=2421、計算事物的有序安排或有序選擇數。這又分為兩種情況：（1）不允許任何事物重復；（2）允許事物重復。2、計算事物的無序安排或無序選擇數。這又分為兩種情況：（1）不允許任何事物重復

17、；（2）允許事物重復。 這是屬于排列問題. 這是屬這是屬于組合問于組合問題題在實際中，大量的計數問題分為兩大類： 1.1 加法法則和乘法法則加法法則和乘法法則一、線排列一、線排列設集合12,nAa aa是具有n個元素的集合，r是正整數注意：!,(1)(1)()!nrnPP n rn nnrnr 則集合A的r-排列為當r n時，則稱A的n-排列為全排列，即,!.nnPP n nn,(1,1);,(1,1)(1, ).P n rnP nrP n rrP nrP nr2nr當時，二、二、圓圓排列排列三、重排列三、重排列1.2 排列排列二、二、圓圓排列排列 例1 由數字1,2,3,4,5,6可以構成多

18、少個數字互不相同的四位數. 例2 將具有9個字母的單詞FRAGMENTS進行排列,要求A總是緊跟在字母R的右邊,問有多少種這樣的排法.設集合(6,4)360; (8,8)8!40320.PP是具有n個元素的集合，r是正整數,!()!P n rnMrr nr則集合A的r-圓排列為注意：把一個圓排列旋轉可得到另一個圓排列，這兩個圓排列是相同的。 12,nAa aa答案：1.2 排列排列 例例3 排列26個字母，使得在a和b之間正好有7個字母，問有多少種方法？分析分析（1）將a和b之間的7個字母作排列有P(24,7)； （2） a和b又有兩種排法，由乘法原理得以a和b為端點的9個字母的排列有2P(2

19、4，7); （3）把一個排列看成一個整體再與剩下的17個字母進行全排列有18！； （4）由乘法原理，所求的排列數為2 (24,7) 18!36 24!.NP 例例4 假定有8位成員,兩兩配對分成4組,試問有多少種方案N?7 5 3105N 86424!1052222N 1.2 排列排列 例5 有8人圍圓桌就餐，問有多少種就坐方式？如果有兩人不愿坐在一起，又有多少種就坐方式？若8人是4男4女并交替就坐，又有多少種就坐方式？分析：這顯然都是圓排列問題。8!7!;7! 2 6!3600;(4! 4) 4 3 2 1144.8 答案：1.2 排列排列 例6 用20個不同顏色的念珠串成一條項鏈，能做成多

20、少不同的項鏈？分析：這顯然都是圓排列問題。20!19!;20答案：19!/ 2.又因為項鏈還可以翻轉過來而念珠的排列未改動，因此項鏈的總數是1.2 排列排列定義定義 1.3三、三、 重排列重排列集合論定義集合論定義定理定理 1.1從從n個不同元素中，可重復選取個不同元素中，可重復選取r個按個按一定順序排列起來，稱為重排列。一定順序排列起來，稱為重排列。從重集從重集B=k1b1, k2b2, , knbn中選中選取取r個按一定順序排列起來。個按一定順序排列起來。重集重集B=b1, b2, , bn 的的r排列排列的個數為的個數為nr。證明：證明：構造構造B的的r排列如下：選擇第一項時可從排列如下

21、：選擇第一項時可從n個元素個元素中任選一個，有中任選一個，有n種選法，選擇第二項時由于可以重復種選法，選擇第二項時由于可以重復選取，仍有選取，仍有n種選法，種選法，同理，選擇第，同理，選擇第r項時仍有項時仍有n種種選法，根據乘法法則，可得出選法，根據乘法法則，可得出r排列的個數為排列的個數為nr。證畢。證畢。考慮在重集中選r個元素1122,nnBk b kbkb進行的排列。1.2 重排列例61.2 排列排列例例 題題三、三、 重排列重排列例例7 由數字由數字1,2,3,4,5,6這六個數字能這六個數字能組成多少個五位數？又可組成多少組成多少個五位數？又可組成多少大于大于34500的五位數？的五

22、位數？解：解：一個五位數的各位數字可重復出現，是一個典型的一個五位數的各位數字可重復出現，是一個典型的重排列問題，相當于重集重排列問題，相當于重集B=1,2,6的的5排列，排列，所求的五位數個數為所求的五位數個數為65=7776。 大于大于34500的五位數可由下面三種情況組成：的五位數可由下面三種情況組成：萬位選萬位選4,5,6中的一個，其余中的一個，其余4位相當于重集位相當于重集B的的4排列，排列，由乘法法則知，共有由乘法法則知，共有3 64個五位數；個五位數；萬位是萬位是3，千位，千位5,6中的一個，其余中的一個，其余3位相當于重集位相當于重集B的的3排列，由乘法法則知，共有排列，由乘法

23、法則知，共有2 63個五位數；個五位數；萬位是萬位是3，千位，千位4中的一個，百位選中的一個，百位選5,6中的一個，其余中的一個，其余2位相當于重集位相當于重集B的的2排列，由乘法法則知，共有排列，由乘法法則知，共有2 62個五位數；個五位數； 由加法法則知，大于由加法法則知，大于34500的五位數個數為的五位數個數為364 + 263 + 262=43921.2 重排列計數1.2 排列排列三三 重排列重排列定理定理 1.2重集重集B=n1b1,n2b2,nkbk的全排列的全排列個數為個數為112!,! .!kiiknnnnnn其其中中證明：證明：將將B中的中的ni個個bi看作不同的看作不同的

24、ni個元素，賦予上標個元素，賦予上標1,2, ni，即，即 ，如此，重集，如此，重集B就變成具有就變成具有n1+n2+nk=n個不同的元素集合個不同的元素集合顯然，集合顯然，集合A的全排列個數為的全排列個數為n!。又由于又由于ni個個bi賦予上標的方法有賦予上標的方法有ni!種，于是對重集種，于是對重集B的任一的任一個全排列，都可以產生集合個全排列，都可以產生集合A的的n1!n2!nk!個排列（由個排列（由乘法法則），故重集乘法法則），故重集B的全排列個數為的全排列個數為證畢。證畢。注：利用組合數的計數方法同樣可以得出證明。注：利用組合數的計數方法同樣可以得出證明。12,.,(1,2,., )

25、iniiib bbik 12121212111222,.,.,.,.,knnnkkkAb bbb bbb bb 112! .!kiiknnnnnn其其中中1.2 重排列例71.2 排列排列三、三、 重排列重排列例例 題題例例8 有四面紅旗，三面藍旗，二面有四面紅旗，三面藍旗，二面黃旗，五面綠旗可以組成多少種由黃旗，五面綠旗可以組成多少種由14面旗子組成的一排彩旗？面旗子組成的一排彩旗？解：解：這是一個重排列問題，是求重集這是一個重排列問題，是求重集4*紅旗紅旗,3*藍旗藍旗,2*黃黃旗旗,5*綠旗綠旗的全排列個數，根據定理，一排彩旗的種數為的全排列個數，根據定理，一排彩旗的種數為14!25225204! 3! 2! 5! 1.2 重排列例81.2 排列排列三、三、 重排列重排列例例 題題例例9 用字母用字母A、B、C組成五個字母組成五個字母的符號，要求在每個符號里，的符號，要求在每個符號里，A至多至多出現出現2次，次，B至多出現至多出現1次，