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

組合數(shù)學(xué)課時(shí)：36課時(shí)成績(jī)分配：平時(shí)成績(jī)30分，期末考試成績(jī)70分。平時(shí)成績(jī)?nèi)〉梅绞剑喊才?次課堂測(cè)驗(yàn)，每次6分。課件郵箱:hjh0826@163.com密碼:08261第1頁(yè)組合數(shù)學(xué)應(yīng)用范圍從廣義上講組合數(shù)學(xué)就是離散數(shù)學(xué)組合數(shù)學(xué)研究滿足一定條件組合模型情況:(1)存在性：(2)計(jì)數(shù)：(3)有哪些？(4)哪些最優(yōu)？組合數(shù)學(xué)與算法、密碼學(xué)、編碼理論、數(shù)據(jù)壓縮等計(jì)算機(jī)方向密不可分。****2第2頁(yè)選取教材組合數(shù)學(xué)(第四版)盧開澄盧華明著清華大學(xué)出版社3第3頁(yè)組合數(shù)學(xué)應(yīng)用范圍第一章:排列與組合第二章:遞推關(guān)系與母函數(shù)第三章:容斥原理與鴿巢原理第四章:Burnside引理與Polya定理第五章:區(qū)組設(shè)計(jì)第六章:線性規(guī)劃第七章:編碼介紹第八章:組合算法介紹4第4頁(yè)參考教材組合數(shù)學(xué)RichardA.Brualdi著馮舜璽等譯機(jī)械工業(yè)出版社5第5頁(yè)參考教材組合數(shù)學(xué)及其算法楊振生中國(guó)科學(xué)技術(shù)大學(xué)出版社6第6頁(yè)第一章：排列與組合1.1基本計(jì)數(shù)法則1.2一一對(duì)應(yīng):1.3排列與組合1.4圓周排列1.5排列生成算法1.6允許重復(fù)組合與不相鄰組合1.7組合意義解釋1.8應(yīng)用舉例1.9*Stirling公式7第7頁(yè)1.1基本計(jì)數(shù)法則1、加法法則:假如含有性質(zhì)A事件有m個(gè)，性質(zhì)B事件有n個(gè)，則含有性質(zhì)A或B事件有m+n個(gè)。A和B是性質(zhì)無(wú)關(guān)兩個(gè)事件。8第8頁(yè)2、乘法法則:若含有性質(zhì)A事件有m個(gè)，含有性質(zhì)B事件有n個(gè)，則含有性質(zhì)A及B事件有mn個(gè)1.1基本計(jì)數(shù)法則9第9頁(yè)例1.1若從合肥到南京有2條路可走，從南京到上海有3條路可走，從上海到杭州有2條路可走，問從合肥經(jīng)南京、上海到杭州有多少路可走？1.1基本計(jì)數(shù)法則10第10頁(yè)例1.2：用乘法法則解釋8卦及64卦。解：1、太極生兩儀

3、四象生八卦

000，001，010,011100，101，110,111

2、兩儀生四象

00，01，10，11；1.1基本計(jì)數(shù)法則11第11頁(yè)例1.3：長(zhǎng)度為n0,1符號(hào)串?dāng)?shù)目?例1.4人類DNA鏈長(zhǎng)度為2.1×1010,鏈上每一位由T,C,A,G四種化合物組成,求人類DNA鏈可組成數(shù)目。1.1基本計(jì)數(shù)法則12第12頁(yè)例1.5：求布爾函數(shù)f(x1,x2,…,xn)數(shù)目以n=2為例：f(x1,x2)有四種方式：f(0,0),f(0,1),f(1,0),f(1,1)。1、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=0。2、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1?！瓕?duì)應(yīng)著長(zhǎng)度為22字符串，每一位都能夠取0或1;乘法：2^22自變量數(shù)為n個(gè)時(shí)：2^2n1.1基本計(jì)數(shù)法則*13第13頁(yè)1、從n個(gè)數(shù)中找出最大值問題2、n個(gè)人參加單淘汰賽，最終產(chǎn)生冠軍過(guò)程。1.2一一對(duì)應(yīng)14第14頁(yè)例1.6：求n2個(gè)人站成一排和站成n排（方陣）方案數(shù)，并比較兩種方案數(shù)大??？解：9個(gè)人站成一排方案數(shù)是9!，設(shè)a1a2a3a4a5a6a7a8a9是9個(gè)人一排，可組成一個(gè)方陣a1a2a3a4a5a6a7a8a9給定一個(gè)方陣b1b2b3b4b5b6b7b8b9也唯一確定一排b1b2b3b4b5b6b7b8b9所以這兩種站位方式方案數(shù)一樣多，都是9!1.2一一對(duì)應(yīng)15第15頁(yè)例1.6：求n2個(gè)人站成一排和站成n排（方陣）方案數(shù)，并比較兩種方案數(shù)大小？9個(gè)人站成方陣方案數(shù)為：C(9,3)3!C(6,3)3!C(3,3)3!1.2一一對(duì)應(yīng)16第16頁(yè)定理1.1n個(gè)有標(biāo)號(hào)1,2,…,n頂點(diǎn)樹數(shù)目等于nn-2。（n>=2）12534設(shè)一棵樹頂點(diǎn)集為A1、從中找到編號(hào)最小葉子結(jié)點(diǎn)，去掉該葉子結(jié)點(diǎn)a1及其鄰接邊(a1,b1)。2、重復(fù)以上過(guò)程。只到剩一條邊為止。(1,2),(4,3),(3,2)這棵樹對(duì)應(yīng)序列（2，3，2）一個(gè)棵對(duì)應(yīng)序列B=b1b2b3…bn-2而且是唯一1.2一一對(duì)應(yīng)17第17頁(yè)12534樹頂點(diǎn)集合為12345這棵樹對(duì)應(yīng)序列（2，3，2）任給一個(gè)序列B{b1,b2,b3,…,bn-2}1、從A找到最小不屬于B元素,設(shè)為a1,與b1連接，從A中去掉a1，從B中去掉b1.2、重復(fù)以上過(guò)程只到B為空，A中剩下兩個(gè)3、連接剩下兩個(gè)頂點(diǎn)。1.2一一對(duì)應(yīng)*18第18頁(yè)1.3：排列與組合1、排列定義：設(shè)A={a1,a2,…,an}是n個(gè)不一樣元素集合，任取A中r個(gè)元素按次序排成一列，稱為從A中取r個(gè)一個(gè)排列，r滿足0≤r≤n。從n個(gè)不一樣球中取一個(gè)球放在第一個(gè)盒子中，從余下n-1個(gè)球中取一個(gè)球放在第二個(gè)盒子中，…………………從余下n-(r-1)個(gè)球中取一個(gè)放在第r個(gè)盒子中。(1)(2)(3)(…)(r)依據(jù)乘法法則：P(n,r)=n(n-1)…(n-r+1)=n!／(n-r)!19第19頁(yè)全排列:P(n,n)=n(n-1)…2×1=n!1.3：排列與組合2、組合定義：當(dāng)從n個(gè)不一樣元素中取出r個(gè)而不考慮它次序時(shí),稱為從n中取r個(gè)組合,其數(shù)目記為C(n,r)。公式：從n中取r組合數(shù)記作C(n,r)從n中取r排列數(shù)是P(n,r)。C(n,r)=P(n,r)/r!=n!/[r!(n-r)!]二者之間關(guān)系:20第20頁(yè)第一章：排列與組合排列能夠看作n個(gè)不一樣元素取r個(gè)放進(jìn)r個(gè)不一樣盒子放法.組合能夠看作n個(gè)不一樣元素取r個(gè)放進(jìn)r個(gè)相同盒子放法.公式1：C(n,r)=C(n,n-r)21第21頁(yè)從5個(gè)元素中取3個(gè)進(jìn)行排列算法：inta[5]={1,2,3,4,5},b[3]；

for(i=0;i<5;i++){b[0]=a[i];for(j=0;j<5;j++){if(j==i)continue;elseb[1]=a[j];for(k=0;k<5;k++){if(k==i||k==j)continue;elseb[2]=a[k];打印b[]}}}1.3：排列與組合22第22頁(yè)例1.7:由5種顏色星狀物,20種不一樣花共25個(gè)元素中任取5個(gè)排成以下列圖案：兩邊是星狀物,中間是3朵花，問共有多少種這么圖案？解1：5×20×19×18×4=13680020種不一樣花取3種排列排列數(shù)為：P(20,3)=20!/17!=20*19*18=6840依據(jù)乘法法則，共有圖案數(shù)為：6840*20=136800解2：5種顏色星狀物取兩個(gè)排列排列數(shù)為P(5,2)=5!/3!=5*4=20★

★1.3：排列與組合23第23頁(yè)1.8隨機(jī)地選擇n個(gè)人，求n個(gè)人最少有兩人生日相同概率(不考慮潤(rùn)年)解:n個(gè)人生日不一樣方案數(shù)是:365*364*…*(365-n+1)=P(365,n)n個(gè)人生日總方案數(shù)是:365n最少有兩人生日相同概率:1-P(365,n)/365n1.3：排列與組合24第24頁(yè)1.8隨機(jī)地選擇n個(gè)人，求n個(gè)人最少有兩人生日相同概率(不考慮潤(rùn)年)解:思緒：任選兩人，使其生日相同，其它任選。最少有兩人生日相同概率:C(365,1)×C(n,2)×365n-2/365n1.3：排列與組合*對(duì)還是錯(cuò)？25第25頁(yè)1.4：圓周排列定義：在排列中，假如我們不橫排而是將各元素排列在一個(gè)圓周上，那么我們稱這種排列方式為圓周排列。在排列中1234,2341,3412,4123為四個(gè)不一樣排列，而在圓排列中這些排列是一個(gè).要求相對(duì)位置不變算一個(gè)排列。26第26頁(yè)將從n中取r個(gè)作圓排列排列數(shù)記作Q(n,r)。從n中取r個(gè)作排列，與圓排列相比，重復(fù)了r倍；公式：Q(n,r)=P(n,r)/r，Q(n,n)=P(n,n)/n=n!/n=(n-1)!1.4：圓周排列Q(n,r)=P(n,r)/r=n!/r(n-r)!27第27頁(yè)例1.19：5顆不一樣紅色珠子，3顆不一樣藍(lán)色珠子裝在圓板四面,試問有多少種方案？若藍(lán)色珠子不相鄰又有多少種排列方案？藍(lán)色珠子在一起又怎樣？解：(1)Q(8,8)=P(8,8)/8=7!。(3)藍(lán)色珠子在一起Q(6,6)3!=5!3!。(2)藍(lán)色珠子不在一起。首先5顆不一樣紅色珠子作圓排列，共有Q(5,5)=4!，3顆不一樣藍(lán)色珠子排在紅色珠子中間4!×5×4×31.4：圓周排列****28第28頁(yè)例1.20：5對(duì)夫婦出席一宴會(huì)，圍一圓桌而坐，試問有幾個(gè)不一樣方案？若要求每對(duì)夫妻相鄰又有多少種方案?解：1）座位無(wú)限制Q(10,10)=P(10,10)/10=10!/10=9!=362880共有362880種方式。2）夫婦相鄰而坐首先能夠?qū)⒁粚?duì)夫婦作為一個(gè)元素來(lái)對(duì)待，共有Q(5,5)=P(5,5)/5=24。但夫婦能夠交換坐位，5對(duì)夫婦共有25種方式。依據(jù)乘法法則：若夫妻相鄰而坐，共有24×25=24×32=768種方式。1.4：圓周排列*29第29頁(yè)第一章：排列與組合多重集排列設(shè)S是一個(gè)多重集，有K個(gè)不一樣類型元素，各元素重復(fù)分別為n1,n2,…,nk,n=n1+n2+…+nk,則S排列數(shù)為:30第30頁(yè)第一章：排列與組合證實(shí)：給定多重集S，有k種類型元素，比如說(shuō)a1,a2,a3,…,ak,且分別有重?cái)?shù)n1,n2,…nk,元素總個(gè)數(shù)n=n1+n2+…+nk,現(xiàn)在存在n個(gè)位置,我們要在n個(gè)位置放S一個(gè)元素,首先要確定哪些位置放a1元素,共有剩下n-n1個(gè)位置,a2元素,共有……….剩下n-n1-…-nk-1個(gè)位置,ak元素,共有31第31頁(yè)第一章：排列與組合依據(jù)剩法法則:S排列總數(shù)32第32頁(yè)練習(xí)題1、求1040和2030公因數(shù)數(shù)目。解：1040=240540，2030=260530C(41,1)*C(31,1)33第33頁(yè)2、試證n2整除數(shù)數(shù)目是奇數(shù)。練習(xí)題34第34頁(yè)1.13、有n個(gè)不一樣整數(shù)，從中取出兩組來(lái)，要求第1組最小數(shù)大于另一組最大數(shù)。設(shè)取第一組數(shù)有a個(gè),第二組有b個(gè),要求第一組數(shù)中最小數(shù)大于第二組中最大，即只要取出一組m個(gè)數(shù)(設(shè)m=a+b),從大到小取a個(gè)作為第一組,剩下為第二組。此時(shí)方案數(shù)為C(n,m)。從m個(gè)數(shù)中取第一組數(shù)共有m-1中取法。(m-1)C(n,m)練習(xí)題35第35頁(yè)練習(xí)題****36第36頁(yè)第1章：游戲中碰到題目：1、中國(guó)象棋將帥問題2、一摞烙餅排序3、買書問題4、快速找出故障機(jī)器5、飲料供貨6、光影切割問題7、小飛電梯調(diào)度算法8、高效率地安排見面會(huì)9、雙線程高效下載..................《編程之美--微軟技術(shù)面試心得》37第37頁(yè)《編程之美--微軟技術(shù)面試心得》第2章：數(shù)字之魅1、求二進(jìn)制數(shù)中1個(gè)數(shù)2、不要被階乘嚇倒3、尋找發(fā)帖“水王”4、1數(shù)目5、尋找最大K個(gè)數(shù)6、最大條約數(shù)問題7、找符合條件整數(shù)8、斐