《《組合數(shù)學(xué)講》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《組合數(shù)學(xué)講》PPT課件.ppt（59頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、前言,組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說(shuō)，大禹在4000多年前就觀察到神龜背上的幻方.,幻方可以看作是一個(gè) 3階方陣，其元素是1 到9的正整數(shù)，每行、 每列以及兩條對(duì)角線 的和都是15。,5,1,9,3,7,2,4,8,6,前言,1666年萊布尼茲所著組合學(xué)論文一書問(wèn)世，這是組合數(shù)學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。 組合數(shù)學(xué)的蓬勃發(fā)展則是在計(jì)算機(jī)問(wèn)世和普遍應(yīng)用之后。由于組合數(shù)學(xué)涉及面廣，內(nèi)容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個(gè)統(tǒng)一而有效的理論體系。這與數(shù)學(xué)分析形成了對(duì)照。 組合數(shù)學(xué)研究的中心問(wèn)題是按一定規(guī)則將一些事物安排成各式各樣模式的問(wèn)
2、題。包括安排的存在問(wèn)題、計(jì)數(shù)問(wèn)題、構(gòu)造問(wèn)題以及給出了優(yōu)化標(biāo)準(zhǔn)后如何求出最優(yōu)安排問(wèn)題。,前言,組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時(shí)的合理分類和組合模型的轉(zhuǎn)換。 但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要 一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。,第一章排列與組合,1.1 加法法則與乘法法則. 加法法則 設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件A或B之一有m+n種產(chǎn)生方式。,集合論語(yǔ)言： 若 |A| = m , |B| = n , AB = , 則 |AB| = m + n 。,第一章排列與組合, 例 某班選修企業(yè)管理的有 18 人，不選的有 10 人，則該班共有 18 +
3、10 = 28 人。, 例 北京每天直達(dá)上海的客車有 5 次，客機(jī)有 3 次， 則每天由北京直達(dá)上海的旅行方式有 5 + 3 = 8 種。,第一章排列與組合, 乘法法則 設(shè)事件A有m種產(chǎn)生式，事件B有n種產(chǎn)生方式，則事件A與B有 m n種產(chǎn)生方式。,集合論語(yǔ)言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 則 |A B| = m n 。,第一章排列與組合,例 某種字符串由兩個(gè)字符組成，第一個(gè)字符可選自a，b，c，d，e，第二個(gè)字符可選自1，2，3，則這種字符串共有5 3 = 15 個(gè)。,例 從A到B有三條道路，從B到C有兩條道路，則從A經(jīng)B到C有32
4、=6 條道路。,第一章排列與組合,例 某種樣式的運(yùn)動(dòng)服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42 = 8種著色方案。 若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則方案數(shù)就不是4 4 = 16， 而只有 4 3 = 12 種。 在乘法法則中要注意事件 A 和 事件 B 的相互相容性。,第一章排列與組合,例 1)求小于10000的含1的正整數(shù)的個(gè)數(shù) 2)求小于10000的含0的正整數(shù)的個(gè)數(shù),1)小于10000的不含1的正整數(shù)可看做4位數(shù),但0000除外. 故有999916560個(gè). 含1的有：99996560=3439個(gè),另: 全部4位數(shù)有10
5、4 個(gè),不含1的四位數(shù)有94個(gè),含1的4位數(shù)為兩個(gè)的差: 10494 = 3439個(gè),第一章排列與組合,2)“含0”和“含1”不可直接套用。0019 含1但不含0。 在組合的習(xí)題中有許多類似的隱含的 規(guī)定，要特別留神。,不含0的1位數(shù)有9個(gè)，2位數(shù)有92個(gè)，3位數(shù)有93個(gè)，4位數(shù)有94個(gè),不含0小于10000的正整數(shù)有 9+92+93+94=(951)/(91)=7380個(gè),含0小于10000的正整數(shù)有 99997380=2619個(gè),第一章排列與組合,1.2排列與組合,定義：從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次序排列，稱為從n個(gè)中取r個(gè)的排列。其排列的個(gè)數(shù)記為P(n,r)表示。,第一章
6、排列與組合,規(guī)定：,從n個(gè)不同元中取n個(gè)的排列稱為n的全排列,第一章排列與組合,我們有下列排列與組合的計(jì)數(shù)公式：,特別地，對(duì)于全排列有P(n, n)=n!。,第一章排列與組合,從n個(gè)中取r個(gè)的排列的典型例子是從n個(gè)不同的球中,取出r個(gè),放入r個(gè)不同的盒子里,每盒1個(gè)。第1個(gè)盒子有n種選擇，第2個(gè)有n-1種選擇，第r個(gè)有n-r+1種選擇。 故有P(n,r)=n(n-1) (n-r+1) 有時(shí)也用nr記P(n,r),第一章排列與組合,若球不同，盒子相同，則是從n個(gè)中取r個(gè)的組合的模型。若放入盒子后再將盒子標(biāo)號(hào)區(qū)別，則又回到排列模型。每一個(gè)組合可有r!個(gè)標(biāo)號(hào)方案。,故有 C(n,r)r!=P(n,r
7、),第一章排列與組合,例 有5本不同的日文書，7本不同的英文書，10本不同的中文書。 1)取2本不同文字的書； 2)取2本相同文字的書； 3)任取兩本書 請(qǐng)問(wèn)有多少種不同的取法？,解：1)57+510+710=155; 2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;,第一章排列與組合,例 從1,300中取3個(gè)不同的數(shù)，使這3個(gè)數(shù)的和能被3整除，有多少種方案？,解：將1,300分成3類： A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要滿足條件，有四種解法： 1)3個(gè)
8、數(shù)同屬于A; 2)3個(gè)數(shù)同屬于B 3)3個(gè)數(shù)同屬于C; 4)A,B,C各取一數(shù).,故共有3C(100,3)+1003 =1485100,第一章排列與組合,定義：從n個(gè)不同元素中允許重復(fù)地取r個(gè)元素作排列，稱為n元可重r-排列，其排列數(shù)為nr 例：由數(shù)字1，2，3可組成多少個(gè)兩位數(shù)？并寫出這些兩位數(shù)。 解：這是三元可重2-排列問(wèn)題。其排列數(shù)為32=9。這些兩位數(shù)為11,12,13,21,22,23,31,32,33。,n1個(gè)a1,n2個(gè)a2,nk個(gè)ak的全排列的個(gè)數(shù)為:,第一章排列與組合,定義：從n 個(gè)不同元素中取r個(gè)元素圍成一圈，稱為從n個(gè)不同元中取r個(gè)元的圓排列，其排列數(shù)記為K(n,r)。我
9、們有：,這是因?yàn)閞個(gè)不同的線排列（即一般的排列）對(duì)應(yīng)于一個(gè)圓排列。,第一章排列與組合,例：4個(gè)女生和4個(gè)男生圍圓桌相間而坐，試問(wèn)有多少種不同的入座方式？ 解：先讓女生入座，這是一個(gè)4的圓排列問(wèn)題。有K（4，4）4!=4！/44!=3！4!。 例:由四種顏色的珠子各一顆，可以做成多少種不同的項(xiàng)鏈？ 解：注意項(xiàng)鏈可以翻轉(zhuǎn)。,第一章排列與組合,定義：從n個(gè)不同元中允許重復(fù)地取r個(gè)元的組合，稱為n元可重r-組合，其組合數(shù)記為F(n,r)。用集合描述為：重集a1, a2 ,an的r-組合數(shù)為F(n,r)。,結(jié)論：F(n,r)=C(n+r-1,r)，其中n,r均為正整數(shù)。,證明要點(diǎn)：設(shè)a1, a2 ,ar
10、是從1,2,n中任取的一個(gè)可重r-組合，不妨設(shè)： 1a1 a2 ar n 從而有： 1a1 a2+1 a3+2 ar+r-1 n+r-1,第一章排列與組合,例:某車站有6個(gè)入口處，每個(gè)入口處每次只能進(jìn)一人，一組9個(gè)人進(jìn)站的方案有多少？,解一進(jìn)站方案表示成：00011001010100 其中“0”表示人，“1”表示門框，其中“0”是不同元，“1”是相同元。給“1”n個(gè)門只用n-1個(gè)門框。任意進(jìn)站方案可表示成上面14個(gè)元素的一個(gè)排列。,第一章排列與組合,解法1標(biāo)號(hào)可產(chǎn)生5!個(gè)14個(gè)元的全排列。 故若設(shè)x為所求方案，則 x5!=14! x=14!/5!=726485760,解法2在14個(gè)元的排列中先
11、確定“1”的位置，有C(14,5)種選擇，在確定人的位置，有9！種選擇。 故C(14,5)9!即所求,第一章排列與組合,解法3把全部選擇分解成若干步，使每步宜于計(jì)算。不妨設(shè)9個(gè)人編成1至9號(hào)。1號(hào)有6種選擇；2號(hào)除可有1號(hào)的所有選擇外，還可（也必須）選擇當(dāng)與1號(hào)同一門時(shí)在1號(hào)的前面還是后面，故2號(hào)有7種選擇；3號(hào)的選擇方法同2號(hào)，故共有8種。 以此類推，9號(hào)有14種選擇。 故所求方案為67 814種。,第一章排列與組合,1.3模型轉(zhuǎn)換,“一一對(duì)應(yīng)”概念是一個(gè)在計(jì)數(shù)中極為基本的概念。一一對(duì)應(yīng)既是單射又是滿射。 如我們說(shuō)A集合有n個(gè)元素 |A|=n，無(wú)非是建立了將A中元與1,n元一一對(duì)應(yīng)的關(guān)系.
12、在組合計(jì)數(shù)時(shí)往往借助于一一對(duì)應(yīng)實(shí)現(xiàn)模型轉(zhuǎn)換。 比如要對(duì)A集合計(jì)數(shù)，但直接計(jì)數(shù)有困難,于是可設(shè)法構(gòu)造一易于計(jì)數(shù)的B，使得A與B一一對(duì)應(yīng)。,第一章排列與組合,例 在100名選手之間進(jìn)行淘汰賽(即一場(chǎng)的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問(wèn)要舉行幾場(chǎng)比賽？ 解 一種常見的思路是按輪計(jì)場(chǎng)，費(fèi)事。另一種思路是淘汰的選手與比賽(按場(chǎng)計(jì))集一一對(duì)應(yīng)。99場(chǎng)比賽。,第一章排列與組合,例,第一章排列與組合,無(wú)論怎樣走法，在x方向上總共走m步，在y方向上總共走n步。若用一個(gè)x表示x方向上的一步，一個(gè)字母y表示y方向上的一步。 則(0,0)(m,n)的每一條路徑可表示為m 個(gè)x與n個(gè)y的一個(gè)有重排列。將每
13、一個(gè)有重排列的x與y分別編號(hào)，可得m!n!個(gè)m+n元的無(wú)重全排列。,第一章排列與組合,設(shè)所求方案數(shù)為P(m+n；m，n) 則P(m+n；m，n)m!n!=(m+n)! 故P(m+n;m,n)= = ( ) =( )=C(m+n,m),(m+n)! m!n!,m+n n,m+n m,第一章排列與組合,例：在上例的基礎(chǔ)上若設(shè)mn，求(0,1)點(diǎn)到(m,n)點(diǎn)不接觸對(duì)角線x=y的格路的數(shù)目(“接觸”包括“穿過(guò)”) 從(0,1)點(diǎn)到(m,n)點(diǎn)的格路，有的接觸x=y，有的不接觸。 對(duì)每一條接觸x=y的格路，做(0,1)點(diǎn)到第一個(gè)接觸點(diǎn)部分關(guān)于x=y的對(duì)稱格路，這樣得到一條從(1,0)到(m,n)的格路
14、。,第一章排列與組合,容易看出從(0,1)到(m,n)接觸x=y的格路與 (1,0)到(m,n)的格路(必穿過(guò)x=y)一一對(duì)應(yīng),第一章排列與組合,若條件改為可接觸但不可穿過(guò)，則限制線要向下或向右移一格，得xy=1，(0,0)關(guān)于xy=1的對(duì)稱點(diǎn)為(1,-1).,格路也是一種常用模型,第一章排列與組合,例 CnH2n+2是碳?xì)浠衔?隨著n的不同有下列不同的枝鏈：,H | H C H | H,H | H C H | H C H | H,H | H C H | H C H | H C H | H,n=1甲烷 n=2 乙烷 n=3 丙烷,第一章排列與組合,H | H C H | H C H | H
15、C H | H C H | H,H | H H C H | | H C C H | | H C H | H H,n=4 丁烷 n=4異丁烷,這說(shuō)明對(duì)應(yīng)CnH2n+2的 枝鏈?zhǔn)怯?n+2個(gè)頂點(diǎn)的一棵樹，其中n個(gè)頂點(diǎn)與之關(guān)聯(lián)的邊數(shù)為4；其它2n+2個(gè)頂點(diǎn)是葉子。對(duì)于這樣結(jié)構(gòu)的每一棵樹，就對(duì)應(yīng)有一種特定的化,合物。從而可以通過(guò)研究具有上述性質(zhì)的樹找到不同的碳?xì)浠衔顲nH2n+2.,第一章排列與組合,1.4全排列的生成算法,就是對(duì)于給定的字符集，用有效的方法將所有可能的全排列無(wú)重復(fù)無(wú)遺漏地枚舉出來(lái)。,全排列的生成算法有許多種，我們僅介紹其中一種-序數(shù)法,第一章排列與組合,1.4.1全排列的生成-序數(shù)
16、法,任一自然數(shù)n都可以唯一確定一個(gè)p進(jìn)制數(shù),反之也然。,類似地，有,第一章排列與組合,同理,所以,即,第一章排列與組合,不難證明，從0到n!-1的任一個(gè)整數(shù)m都可唯一地表示為：,所以從0到n!-1的n!個(gè)整數(shù)與滿足上式的序列(an-1,an-2,a2,a1)一一對(duì)應(yīng)。 然后我們?cè)購(gòu)?an-1,an-2,a2,a1)建立與全排列的一一對(duì)應(yīng)關(guān)系。,第一章排列與組合,例 ：m4000，即n14000,第一章排列與組合,現(xiàn)從序列 (an-1,an-2,a2,a1)得到生成排列，為 了方便起見,不妨今n個(gè)對(duì)象分別是1,2, n.,建立起對(duì)應(yīng)的規(guī)則如下： 設(shè)序列(an-1,an-2,a2,a1) 對(duì)應(yīng)某個(gè)
17、排列(p)=p1 p2,pn， 其中ai可以看作是排列(p)中數(shù)i+1所在位置后 面比i+1小的數(shù)的個(gè)數(shù)， 也就是排列(p)中從數(shù)i+1開始向右統(tǒng)計(jì)小于 或等于i的數(shù)的個(gè)數(shù)。,第一章排列與組合,以排列4213為例， 4后面比它小的數(shù)的個(gè)數(shù)(即a3)為3; 3后面比它小的數(shù)的個(gè)數(shù)(即a2)等于0; 2后面比它小的數(shù)的個(gè)數(shù)(即a1)為1； 排列中比1小的數(shù)是沒有的 故得(p)=(4213) (a3a2a1)(301),我們稱a3a2a1為中介數(shù)。,第一章排列與組合,1.5組合的生成算法,組合的生成不如排列生成困難 今以從1、2、3、4、5、6取3個(gè)的組合為例: (1)123， (2) 124， (
18、3)125， (4)126， (5)134， (6)135， (7)136， (8)145， (9)146， (10)156， (11)234， (12) 235， (13)236， (14)245， (15)246， (16) 256， (17)345， (18)346， (19) 356，(20)456,第一章排列與組合,從中可得規(guī)律： （1）最后一位數(shù)最大可達(dá)n，倒數(shù)第2位最 大可達(dá)n-1，依此類推倒數(shù)第k位(k r) 不得超過(guò)n-k+1若r個(gè)元素的組合用 c1c2cr來(lái)表示，不妨假定c1c2cr 其中 ck n-r+k ， k1,2,r。,(2)當(dāng)存在cjn-r+j時(shí)，其中下標(biāo)的最大者
19、 設(shè)為i，即imaxj| cj n-r+j，則作cici+1。與之相應(yīng)地作ci+1ci+1， ci+2ci+1+1， crcr-1+1,第一章排列與組合,于是我們可得到一般的算法： (1)求滿足不等式cin-r+i的最大的下標(biāo)i，即 imaxj|cjn-r+j， (2) cici+1。 (3)從i+1位開始途徑修改： cjcj-1+1，j=i+1,i+2,r,大家可以思考，從n個(gè)不同元中選r個(gè)的可 重組合的生成？,第一章排列與組合,1.6若干等式及其組合意義,組合意義或組合證明: 含意強(qiáng)弱的不同。承認(rèn)組合證明與其他證 明有相同的“合法性”。,1. C(n,r)=C(n,n-r) (1.6.1)
20、 從1,n去掉一個(gè)r子集，剩下一個(gè)(n-r)子集。由此建立C(n,r)與C(n,n-r)的一個(gè)一一對(duì)應(yīng)。,第一章排列與組合,2. C(n,r)=C(n-1,r)+C(n-1,r-1) (1.6.2) 從1,n取a1,a2,ar.設(shè)1a1a2arn,對(duì)取法分類： a1=1,有C(n-1,r-1)種方案 a11,有C(n-1,r)種方案 共有C(n-1,r)+C(n-1,r-1)中方案，,第一章排列與組合,3.( )+( )+( )+( )=( ) (1.6.3),n n+1 n+2 n+r n+r+1 n n n n r, ,也可看做按含1不含1，含2不含2, 含r不含r的不斷分類,1可從(6.
21、2)推論，也可做一下組合證明 從1,n+r+1取a1a2an an +1，設(shè)a1a2an an+1，可按a1的取值分類： a1=1,2,3,r,r+1.,第一章排列與組合,選政治局,再選常委,n個(gè)中央委員選出l名政治局委員,再?gòu)钠渲羞x出r名常委 選常委,再選非常委政治局委員 兩種選法都無(wú)遺漏,無(wú)重復(fù)地給出可能的方案，應(yīng)該相等。,第一章排列與組合,組合證 1,m的所有方案.每一元素都可取或不取兩種狀態(tài)，由乘法原理可知所有狀態(tài)數(shù)為2m. 而這些可分解為從m個(gè)元素中分別取0個(gè),1個(gè)，2個(gè)，m個(gè)組合的總和。,第一章排列與組合,例某保密裝置須同時(shí)使用若干把不同的鑰匙才能打開?，F(xiàn)有人，每人持若干鑰匙。須人
22、到場(chǎng)，所備鑰匙才能開鎖。問(wèn) 至少有多少把不同的鑰匙？ 每人至少持幾把鑰匙？ 解 每人至少缺把鑰匙，且每人所缺鑰匙不同。故至少共有( )=35把不同的鑰匙。,7 3,任一人對(duì)于其他人中的每人，都至少有把鑰匙與之相配才能開鎖。故每人至少持()20把不同的鑰匙。, ,一般地,某保密裝置安裝了一個(gè)電子鎖. 須同時(shí)使用若干把不同的鑰匙才能打開。現(xiàn)有n人，每人有一把鑰匙。必須m人(mn)到場(chǎng)，才能用鑰匙開鎖。問(wèn)怎么分配鎖的特征和每個(gè)的鑰匙上的特征?,既然鎖比任意m-1把鑰匙多一個(gè)特征，而任意兩個(gè)m-1把鑰匙組合缺少的特征不同，所以鎖的特征至少為C(n,m-1)個(gè)。,同樣道理，對(duì)于m把鑰匙中的一把a(bǔ)，加入任
23、意m-1把鑰匙必能打開鎖，也即剩下的n-1把鑰匙中任意m-1把鑰匙必然缺少a中的某項(xiàng)特征，所以每把鑰匙的特征數(shù)至少為C(n-1, m-1)個(gè)。,每個(gè)鎖的特征在鑰匙中出現(xiàn)的次數(shù),鎖的特征數(shù),上式實(shí)際說(shuō)明了一個(gè)構(gòu)造鎖及磁卡的方法。,鑰匙特征滿足最低要求,以n=5, m=3為為例，在MATLAB輸入以下指令：,n=5;m=3; v=nchoosek(1:5,n-m+1) v = 1 1 1 1 1 1 2 2 2 3 2 2 2 3 3 4 3 3 4 4 3 4 5 4 5 5 4 5 5 5,1 2 3,1 2 4,1 2 5,1 3 4,1 3 5,1 4 5,2 3 5,2 3 4,2 4
24、5,3 4 5,第一章排列與組合,例設(shè)n位長(zhǎng)能糾r個(gè)錯(cuò)的碼字的個(gè)數(shù)為M，則,n位長(zhǎng)的0-1字符串共有2n個(gè)。但不能每個(gè)串都設(shè)為碼字，否則失去糾錯(cuò)能力。,第一章排列與組合,Hamming距離:設(shè)a=a1a2an，b=b1b2bn是 n位串。則a,b的Hamming距離為,即對(duì)應(yīng)位不同的位的個(gè)數(shù)。它有如下性質(zhì)： d(a,b) 0 (當(dāng)且僅當(dāng)a=b時(shí)，等號(hào)成立)； d(a,b)=d(b,a); d(a,b)+d(b,c) d(a,c),第一章排列與組合,右圖表示以a為球心,r位半徑的球體中的 串都作為a處理。若規(guī)定a是碼字，收到a有d(a,a)r 即將a當(dāng)作a發(fā)生最多r個(gè)錯(cuò)誤。此時(shí)兩個(gè)碼字a,b應(yīng)滿足 d(a,b)2r+1。當(dāng)作a處理的串的個(gè)數(shù)為,故,第一章排列與組合,另一方面任一串與最近的碼字的距離不大于2r，否則此串本身可作為一新的碼字，即以2r位半徑的各碼字為球心，應(yīng)當(dāng)使任一串落入某球內(nèi)，故,故所以結(jié)論成立。,
《組合數(shù)學(xué)講》PPT課件.ppt
