組合數(shù)學(xué)11省公開課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)?wù)n件

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

年國(guó)家科技進(jìn)步二等獎(jiǎng)，

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

符合要求安排是否存在？⒉計(jì)數(shù)問題:如有，這種安排有多少種？⒊結(jié)構(gòu)問題:怎樣作出這些安排？⒋優(yōu)化問題:當(dāng)有衡量這種安排優(yōu)劣標(biāo)按時(shí)，怎樣求出最優(yōu)安排？第10頁

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

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

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

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

馮速譯.應(yīng)用組合數(shù)學(xué)。

北京:

機(jī)械工業(yè)出版社,

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

A=A為有限集合，表示元素個(gè)數(shù)重集B=

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