組合數(shù)學(xué)課件--第一章排列與組合

1、1,組合數(shù)學(xué),課時：36學(xué)時,成績分配：平時成績30分，期末考試成績70分。 平時成績?nèi)〉梅绞剑喊才?次課堂測驗，每次6分。,課件郵箱:hjh20070826@163.com 密碼:20070826,2,組合數(shù)學(xué)的應(yīng)用范疇,從廣義上講組合數(shù)學(xué)就是離散數(shù)學(xué),組合數(shù)學(xué)研究滿足一定條件的組合模型的情況:,(1)存在性：,(2)計數(shù)：,(3)有哪些？,(4)哪些最優(yōu)？,組合數(shù)學(xué)與算法、密碼學(xué)、編碼理論、數(shù)據(jù)壓縮等計算機方向密不

2、可分。,****,3,選用教材,組合數(shù)學(xué)(第四版)盧開澄 盧華明 著清華大學(xué)出版社,4,組合數(shù)學(xué)的應(yīng)用范疇,第一章:排列與組合 第二章:遞推關(guān)系與母函數(shù) 第三章:容斥原理與鴿巢原理 第四章:Burnside引理與Polya定理 第五章:區(qū)組設(shè)計 第六章:線性規(guī)劃 第七章:編碼簡介 第八章:組合算法簡介,

3、5,參考教材,組合數(shù)學(xué)Richard A. Brualdi 著馮舜璽等譯機械工業(yè)出版社,6,參考教材,組合數(shù)學(xué)及其算法楊振生中國科學(xué)技術(shù)大學(xué)出版社,7,第一章：排列與組合,1.1 基本計數(shù)法則1.2 一一對應(yīng):1.3 排列與組合1.4 圓周排列1.5 排列的生成算法1.6 允許重復(fù)的組合與不相鄰的組合1.7 組合意義的解釋1.8 應(yīng)用舉例1.9 *Stirling公式,8,1.1基本計數(shù)法則,1、加法法則:

4、如果具有性質(zhì)A的事件有m個，性質(zhì)B的事件有n個，則具有性質(zhì)A或B的事件有m+n個。,A和B是性質(zhì)無關(guān)的兩個事件。,9,2、乘法法則:若具有性質(zhì)A的事件有m個，具有性質(zhì)B的事件有n個，則具有性質(zhì)A及B的事件有mn個,1.1基本計數(shù)法則,10,例1.1 若從合肥到南京有2條路可走，從南京到上海有3條路可走，從上海到杭州有2條路可走，問從合肥經(jīng)南京、上海到杭州有多少路可走？,1.1基本計數(shù)法則,11,例1.2：用乘法法則解釋8卦及64卦。

5、,解：1、太極生兩儀?,3、四象生八卦? 000，001，010, 011 100，101，110, 111,2、兩儀生四象? 00，01，10，11；,1.1基本計數(shù)法則,12,例1.3：長度為n的0,1符號串的數(shù)目?,例1.4 人類DNA鏈的長度為2.1×1010,鏈上每一位由T,C,A,G四種化合物組成,求人類DNA鏈的可組成數(shù)目。,1.1基本計數(shù)法則,13,例1.5：求布爾函數(shù)f

6、(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。,…………,對應(yīng)著長度為22的字符串，每一位都可以取0或1;,乘法：2^22,自變量數(shù)為n個時：2^2n,1.1基本計數(shù)法則,*,14,1、從n個數(shù)中找

7、出最大值問題 2、n個人參加單淘汰賽，最后產(chǎn)生冠軍的過程。,1.2 一一對應(yīng),15,例1.6：求n2個人站成一排和站成n排（方陣）的方案數(shù)，并比較兩種方案數(shù)的大小？,解：9個人站成一排的方案數(shù)是9!，,設(shè)a1a2a3a4a5a6a7a8a9是9個人的一排，,可構(gòu)成一個方陣a1a2a3a4a5a6a7a8a9,給定一個方陣b1b2b3b4b5b6b7b8b9,也唯一確定一排b1b2b3b4b5b6b7b8b9,因此這兩

8、種站位方式的方案數(shù)一樣多，都是9!,1.2 一一對應(yīng),16,例1.6：求n2個人站成一排和站成n排（方陣）的方案數(shù)，并比較兩種方案數(shù)的大??？,9個人站成方陣的方案數(shù)為：,C(9,3)3!C(6,3)3!C(3,3)3!,1.2 一一對應(yīng),17,定理1.1 n個有標(biāo)號1,2,…,n的頂點的樹的數(shù)目等于nn-2。（n>=2）,1,2,5,3,4,,,,,設(shè)一棵樹的頂點集為A 1、從中找到編號最小的葉子結(jié)點，去掉該葉子結(jié)點a1及

9、其鄰接邊(a1,b1)。 2、重復(fù)以上過程。只到剩一條邊為止。,(1,2),(4,3),(3,2),這棵樹對應(yīng)序列（2，3，2）,一個棵對應(yīng)序列B=b1b2b3…bn-2而且是唯一的,1.2 一一對應(yīng),18,1,2,5,3,4,,,,,樹的頂點集合為12345,這棵樹對應(yīng)序列（2，3，2）,任給一個序列B{b1,b2,b3,…,bn-2} 1、從A找到最小的不屬于B的元素,設(shè)為a1,與b1連接，從A中去掉a1，從B中去掉b1.

10、 2、重復(fù)以上過程只到B為空，A中剩余兩個 3、連接剩余的兩個頂點。,1.2 一一對應(yīng),*,19,1.3：排列與組合,1、排列的定義：設(shè)A={a1,a2,…,an}是n個不同的元素的集合，任取A中r個元素按順序排成一列，稱為從A中取r個的一個排列，r滿足0≤r≤n。,從n個不同的球中取一個球放在第一個盒子中， 從余下的n-1個球中取一個球放在第二個盒子中， ………………………………… 從余下的n-(

11、r-1)個球中取一個放在第r個盒子中。,根據(jù)乘法法則： P(n,r)=n(n-1)…(n-r+1)=n!／(n-r)!,20,全排列:P(n,n)=n(n-1)…2×1=n!,1.3：排列與組合,2、組合的定義：當(dāng)從n個不同元素中取出r個而不考慮它的順序時,稱為從n中取r個的組合,其數(shù)目記為C(n,r)。,公式：從n中取r的組合數(shù)記作C(n,r) 從n中取r的排列數(shù)是P(n,r)。,C(n,r

12、)=P(n,r)/r! =n!/[r!(n-r)!],二者之間的關(guān)系:,21,第一章：排列與組合,排列可以看作n個不同的元素取r個放進(jìn)r個不同的盒子的放法.,組合可以看作n個不同的元素取r個放進(jìn)r個相同的盒子的放法.,公式1：C(n,r)=C(n,n-r),22,從5個元素中取3個進(jìn)行排列的算法： int a[5]={1,2,3,4,5},b[3]； for(i=0;i<5;i++)

13、 {b[0]=a[i]; for(j=0;j<5;j++) {if (j==i) continue; else b[1]=a[j]; for(k=0;k<5;k++) {if(k==i||k==j) continue; else b[2]=a[k]

14、; 打印b[]}}},1.3：排列與組合,23,例1.7:由5種顏色的星狀物,20種不同的花共25個元素中任取5個排成如下圖案：兩邊是星狀物,中間是3朵花，問共有多少種這樣的圖案？,解1：5×20×19×18×4=136800,20種不同的花取3種排列的排列數(shù)為：P(20,3)=20!/17!=20*19*18=6840,根據(jù)乘法法則，共有圖案數(shù)為：6840

15、*20=136800,解2：5種顏色的星狀物取兩個排列的排列數(shù)為 P(5,2)=5!/3!=5*4=20,★,?,?,?,★,1.3：排列與組合,24,1.8 隨機地選擇n個人，求n個人至少有兩人生日相同的概率(不考慮潤年),解:,n個人生日不同的方案數(shù)是:,365*364*…*(365-n+1)=P(365,n),n個人生日的總方案數(shù)是:,365n,至少有兩人生日相同的概率: 1-P(365,n)/365n,1.3

16、：排列與組合,25,1.8 隨機地選擇n個人，求n個人至少有兩人生日相同的概率(不考慮潤年),解:,思路：任選兩人，使其生日相同，其它任選。,至少有兩人生日相同的概率: C(365,1)×C(n,2)×365n-2/365n,1.3：排列與組合,*,對還是錯？,26,1.4：圓周排列,定義：在排列中，如果我們不橫排而是將各元素排列在一個圓周上，那么我們稱這種排列方式為圓周排列。,在排列中1234,2341

17、,3412,4123為四個不同的排列，而在圓排列中這些排列是一個.,規(guī)定相對位置不變算一個排列。,27,將從n中取r個作圓排列的排列數(shù)記作Q(n,r)。,從n中取r個作排列，與圓排列相比，重復(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)!,28,例1.19：5顆不同的紅色珠子，3顆不同的藍(lán)色珠子裝在圓板的四周

18、,試問有多少種方案？若藍(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×3,1.4：圓周排列,****,29,例1.20：5對夫婦出席一宴會

19、，圍一圓桌而坐，試問有幾種不同的方案？若要求每對夫妻相鄰又有多少種方案?,解： 1）座位無限制 Q(10,10)=P(10,10)/10=10!/10=9!=362880 共有362880種方式。,2）夫婦相鄰而坐 首先可以將一對夫婦作為一個元素來看待，共有Q(5,5)=P(5,5)/5=24。,但夫婦可以交換坐位，5對夫婦共有25種方式。,根據(jù)乘法法則：若夫妻相鄰而坐，共有 24×

20、25=24×32=768種方式。,1.4：圓周排列,*,30,第一章：排列與組合,多重集的排列,設(shè)S是一個多重集，有K個不同類型的元素，各元素的重復(fù)分別為n1,n2,…,nk,n=n1+n2+…+nk,則S的排列數(shù)為:,31,第一章：排列與組合,證明：給定多重集S，有k種類型的元素，比如說a1,a2,a3,…,ak,且分別有重數(shù)n1,n2,…nk,元素的總個數(shù)n=n1+n2+…+nk,,現(xiàn)在存在n個位置,我們要在n個位置放S的

21、一個元素,首先要確定哪些位置放a1的元素,共有,剩下n-n1個位置, a2的元素,共有,……………………….,剩下n-n1-…-nk-1個位置, ak的元素,共有,32,第一章：排列與組合,根據(jù)剩法法則:,S的排列的總數(shù),33,練習(xí)題,1、求1040和2030的公因數(shù)的數(shù)目。,解：1040=240540，2030=260530,C(41,1)*C(31,1),34,2、試證n2的整除數(shù)的數(shù)目是奇數(shù)。,練習(xí)題,35,1.13、有n個不同的

22、整數(shù)，從中取出兩組來，要求第1組的最小數(shù)大于另一組的最大數(shù)。,設(shè)取的第一組數(shù)有a個,第二組有b個,,要求第一組數(shù)中最小數(shù)大于第二組中最大的，,即只要取出一組m個數(shù)(設(shè)m=a+b),從大到小取a個作為第一組,剩余的為第二組。,此時方案數(shù)為C(n,m)。,從m個數(shù)中取第一組數(shù)共有m-1中取法。,(m-1)C(n,m),練習(xí)題,36,練習(xí)題,****,37,第1章：游戲中碰到的題目：1、中國象棋將帥問題2、一摞烙餅的排序3、買書問題4

23、、快速找出故障機器5、飲料供貨6、光影切割問題7、小飛的電梯調(diào)度算法8、高效率地安排見面會9、雙線程高效下載..................,《編程之美--微軟技術(shù)面試心得》,38,《編程之美--微軟技術(shù)面試心得》,第2章：數(shù)字之魅1、求二進(jìn)制數(shù)中1的個數(shù)2、不要被階乘嚇倒3、尋找發(fā)帖“水王”4、1的數(shù)目5、尋找最大的K個數(shù)6、最大公約數(shù)問題7、找符合條件的整數(shù)8、斐波那契（Fibonacci）數(shù)列..

24、..............,39,《編程之美--微軟技術(shù)面試心得》,第3章結(jié)構(gòu)之法1、字符串移位包含的問題2、電話號碼對應(yīng)英語單詞3、計算字符串的相似度4、從無頭單鏈表中刪除節(jié)點5、最短摘要的生成................8、求二叉樹中節(jié)點的最大距離9、重建二叉樹10、分層遍歷二叉樹,40,《編程之美--微軟技術(shù)面試心得》,第4章數(shù)學(xué)之趣1、金剛坐飛機問題2、瓷磚覆蓋地板3、買票找零4、點是否在三角形內(nèi)