組合數學(Combinatorics)武仲科北京師范大學信息科學與技術學院-第一學期第1頁WelcometoCISTofBNU!第2頁教學方式講課+課后作業+自學第3頁GradingPolicyAssignments50%Finalexam50%第4頁此課程公共郵箱，請不要刪除信件Account:cistmath@Password:math第5頁武仲科/Office:電子樓503Telmail：zhongkewu@第6頁武仲科研究方向計算機圖形學計算機輔助幾何設計計算機動畫虛擬現實醫學圖象處理教育經歷09/1984~09/1988，理學學士，北京大學數學系基礎數學專業09/1988~01/1991，碩士，北京航空航天大學CAD/CAM方向09/1991~09/1995，博士，北京航空航天大學CAD/CAM方向工作經歷.4~現在，北京師范大學信息科學與技術學院1995.9~.4,新加坡南洋理工大學(NTU)計算機工程系,法國國家信息與自動化研究所(INRIA),新加坡國家高性能計算研究所(IHPC),中科院軟件所從事研究工作獎勵年8月，新加坡南洋理工大學TanChinTuan交流學者年8月，年8月，年8月，新加坡南洋理工大學訪問教授(VisitingProfessor)

年國家科技進步二等獎，

年教育部科技進步二等獎，排名第六第7頁第一講介紹什么是組合數學？為何學？學到什么？怎樣學？第8頁組合數學(Combinatorics)組合數學是研究“安排”學科——把已給有限或可數個物體按一定規則來安排。又名組合學,組合分析，組合論，組合原理,又稱為離散數學。Combinatoricsisconcernedwiththestudyofarrangements,patterns,designs,assignments,schedules,connections,andconfigurations.第9頁組合數學研究問題⒈存在性問題:

符合要求安排是否存在？⒉計數問題:如有，這種安排有多少種？⒊結構問題:怎樣作出這些安排？⒋優化問題:當有衡量這種安排優劣標按時，怎樣求出最優安排？第10頁

組合數學不但是近年來最活躍、最迷人數學分支，也是計算機科學技術主要理論基礎之一。組合數學算法與計算機技術結合在當代科學技術中發揮出極為主要作用。組合數學在電子工程、數字通信、物理學、力學、管理科學等很多領域，含有廣泛應用。第11頁組合數學內容豐富，包括廣泛。主要包含：組累計數、組合算法、組合設計、密碼學、編碼理論、圖論、線性規劃、復雜度分析等。已經發展成熟，如圖論、線性規劃等，則逐步從組合數學中分離出去。

第12頁例子-1一個船夫要把一只狼，一只羊和一棵白菜運過河。問題是當人不在場時，狼要吃羊，羊要吃白菜，而他船每趟只能運其中一個。他怎樣才能把三者都運過河呢？這就是一個很經典、很簡單組合數學問題。第13頁例子-2N各隊之間循環賽總共有多少場比賽？第14頁例子-3在一塊并排10壟田地中,選擇2壟分別種植A、B兩種作物,每種作物種植一壟,為有利于作物生長,要求A、B兩種作物間隔不少于6壟,則不一樣選壟方法共有___種。

第15頁例子-4某電腦用戶計劃使用不超出500元資金購置單價分別為60,70元單片軟件和盒裝磁盤,依據需要,軟件最少買3片,磁盤最少買2盒,則不一樣選購方式共有__(A)5(B)6(C)7(D)8第16頁例子-5幻方三維四維n維第17頁例子-6七橋問題

第18頁例子-7中國郵遞員問題一名郵遞員帶著要分發郵件從郵局出發，經過要分發每個街道，送完郵件后又返回郵局．假如他必須最少一次走過他管轄范圍內每一條街道，怎樣選擇投遞路線，使郵遞員走盡可能少旅程．這個問題是由我國數學家管梅谷先生（山東師范大學數學系教授）在1962年首次提出，所以在國際上稱之為中國郵遞員問題．用圖論述語，在一個連通賦權圖G（V，E）中，要尋找一條回路，使該回路包含G中每條邊最少一次，且該回路權數最小．也就是說要從包含G每條邊回路中找一條權數最小回路．第19頁例子-8歐拉猜測-36個軍官問題從不一樣6個軍團各選6種不一樣軍階6名軍官共36人，排成一個6行6列方隊，使得各行各列6名軍官恰好來自不一樣軍團而且軍階各不相同，應怎樣排這個方隊？假如用(1，1)表示來自第一個軍團含有第一個軍階軍官，用(1，2)表示來自第一個軍團含有第二種軍階軍官，用(6，6)表示來自第六個軍團含有第六種軍階軍官，則歐拉問題就是怎樣將這36個數對排成方陣，使得每行每列數不論從第一個數看還是從第二個數看，都恰好是由1、2、3、4、5、6組成。歷史上稱這個問題為三十六軍官問題。第20頁例子-9四色問題任何一張地圖只用四種顏色就能使有共同邊界國家著上不一樣顏色第21頁組合數學歷史組合數學是一個古老而又年輕數學分支，4000多年前，中國人就知道3階幻方楊輝三角比帕斯卡三角形早61666年萊布尼茲所著《組合學論文》首次使用了組合論（Combinatorics）一詞。組合數學是發展最快數學分支，但內容龐雜，沒有形成理論體系第22頁為何學？組合數學與信息科學相關組合數學與我們生活相關組合數學與經濟、金融相關組合數學與娛樂相關組合數學與其它數學相關第23頁特點離散有限第24頁學到什么→知識→思維方法→邏輯訓練（大腦）logical→閱讀英文資料能力→在你論文工作中找到應用第25頁怎樣學？仔細，多做練習，訓練參考書1.孫世新，張先迪。組合原理及其應用。國防工業出版社。2.Roberts,F.S.andBarryTesman.AppliedCombinatorics.SecondEdition.機械工業出版社。3.FredS.Roberts,BarryTesman著;

馮速譯.應用組合數學。

北京:

機械工業出版社,

.5第26頁內容組累計數(combinatorialcounting)組合設計(combinatorialdesign)組合優化(combinatorialoptimization)第27頁詳細內容排列組合二項式和多項式容斥原理鴿籠原理與Ramsey定理,重合原理線性遞推關系母函數整系數一次不定方程整數解個數反演公式Polya計數理論第28頁詳細內容組合設計*組合優化*圖論*第29頁基本概念集合(set)

A=A為有限集合，表示元素個數重集B=

B=第30頁映射集合X和Y，單射(injection)滿射(surjection)一一對應(bijection)第31頁1.1加法原理S是有限集合，，且當時則第32頁例子100參議員，435眾議員，從中選擇一個人去見總統，有多少種方式？第33頁例子求長為5二進制數個數，其中要求每個1都同另一個1相鄰第34頁1.2乘法原理若為有限集，且則第35頁例子100參議員，435眾議員，從中選擇一個參議員和一個眾議員去見總統，有多少種方式？第36頁例子BitstringsIfbitstringsareusedtoencodeall26lettersofthealphabet,howmanybitswillsuffice?第37頁例子由數字1、2、3、4、5能夠組成多少個全部數字互不相同四位偶數。第38頁例子求出從7個數學系學生，8個化學系學生，105個經濟系學生和21個物理系學生中選出兩個不一樣專業學生方法數。第39頁1.3排列(permutation)1.3.1元素不重復排列(線排列）1.3.2圓周排列1.3.3元素允許重復排列第40頁1.3.1元素不重復排列P(n,r)=n(n-1)…(n-r+1)=P(n,n)=n!P(n,r)=nP(n-1,r-1)P(n,r)=rP(n-1,r-1)+P(n-1,r)第41頁例子由數字1、2、3、4、5、6能夠組成多少個數字各不相同四位數？將含有9個字母單詞FRAGMENTS進行排列，要求字母A總是跟在字母R右邊，問有多少種這么排法？第42頁例子面試：Jordan，Harper，Gabler第43頁例子CDplayer,5slots.Wehave24CDs,Howmanychoices?第44頁例子求有多少個5位數，每位數字都不相同，不能取0，且數字7和9不相鄰？12個人從左到右排成一排，其中張三不能排在隊首，也不能排在隊尾，問有多少種排法？第45頁1.3.2圓周排列(circularr-permutation)第46頁例子有8人圍圓桌就餐，有多少種就座方式？假如有兩人不愿坐在一起，又有多少種就座方式？4男4女圍圓桌交替就座，有多少種方式？第47頁1.3.3元素允許重復排列重集B=r-排列個數為重集B=全排列個數為這里第48頁例子由1、2、3、4、5、6這幾個數能組成多少個五位數？又能夠組成多少個大于34,500五位數？第49頁例子Pizza9toppings:Pepperoni,Mushroom,Peppers,Olives,sausage,anchovies,salami,onions,baconNHL,82-game,win,lose,tie第50頁例子由4面紅旗，3面藍旗，2面黃旗和5面綠旗能夠組成多少種由14面旗組成一組彩旗？用字母A、B和C組成五個字母符號，要求在每個符號里，A最多出現2次，B最多出現1次，C最多出現3次，求這類符號個數。第51頁1.3.3元素允許重復排列重集B=r-排列個數為多少？第52頁允許重復圓周排列？第53頁1.4組合(Combinations)1.4.1元素不重復組合1.4.2元素允許重復組合第54頁1.4.1元素不重復組合第55頁例子在一個平面上有42個點，且沒有任何三個點在一條直線上。經過這些點能夠結構多少條不相同直線？能夠結構多少個位置不相同三角形？數510,510能被多少個不相同奇數整除？(510510=2x3X5X7X11X13x17)第56頁例子從1，2，…,1000中選出三個整數，有多少種選法使得所選三個整數和能被3整除？某班要從7個女生和4個男生中產生一個班委會，問有多少方式？若：（1）這個班委會有5個人，其中3個女生和2個男生（2）這個班委會有4個人，其中最少有2個女生（3）這個班委會有4個人，但其中之一是李放同學第57頁有7面紅旗、6面藍旗和9面黃旗，求：（1）從這些彩旗中取2面不一樣顏色旗幟，共有多少種取法？（2）從這些彩旗中取2面相同顏色旗幟，又有多少種取法？（3）任取2面旗幟，不論顏色是否相同，又有多少種取法？第58頁例子Pizza3kindoftoppingsHowmanykindofpizzas?第59頁1.4.2元素允許重復組合重集B=r-