chap1-1排列組合

1、組合數(shù)學(xué),,錢(qián) 江,計(jì)算數(shù)學(xué)與應(yīng)用軟件教研室,Email: jqian104@gmail.com,北京郵電大學(xué)理學(xué)院,序1,1666年萊布尼茲所著《組合學(xué)論文》一書(shū)問(wèn)世，這是組合數(shù)學(xué)的第一部專(zhuān)著。書(shū)中首次使用了組合論（Combinatorics）一詞。,序2,組合數(shù)學(xué)就是按照一定的規(guī)則來(lái)安排一些離散個(gè)體的有關(guān)問(wèn)題。其內(nèi)容包括：,1、計(jì)數(shù)與枚舉,2、容斥原理和鴿巢原理,3、組合設(shè)計(jì),4、組合算法和組合優(yōu)化,5、圖論,序3,組合數(shù)學(xué)經(jīng)

2、常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時(shí)的合理分類(lèi)和組合模型的轉(zhuǎn)換。 一個(gè)技巧是從小規(guī)模的問(wèn)題出發(fā)，找到規(guī)律，再推廣到一般。,第一章排列組合,1.1 加法法則與乘法法則1.2 一一對(duì)應(yīng)1.3 排列1.4 圓周排列1.5 組合1.6 排列的生成算法1.7 組合的生成算法1.8 允許重復(fù)的組合與不相鄰的組合1.9 組合意義的解釋1.10 應(yīng)用舉例,

3、1.1 加法法則與乘法法則,加法法則 設(shè)事件A有m種產(chǎn)生方式，事件件B有n種產(chǎn)生方式，則事件A或B之一有m+n種產(chǎn)生方式。,若 |A| = m , |B| = n , A∩B = ? , 則 |A∪B| = m + n 。,集合論語(yǔ)言：,基本假設(shè)：事件A和事件B是無(wú)關(guān)的兩類(lèi)。,1.1 加法法則與乘法法則,例1 某班選修企業(yè)管理的有 18 人，不選的有 10 人，則該班共有 18 + 10

4、= 28 人。,例2 北京每天直達(dá)上海的客車(chē)有 5 次，飛機(jī)有 3 次，火車(chē)有 5 次， 則每天由北京直達(dá)上海的旅行方式有 5 + 3 + 5 = 13 種。,,乘法法則 設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式則事件A與B有m · n種產(chǎn)生方式。,若 |A| = m , |B| = n , A?B = {(a,b) | a ?A,b ? B}, 則 |A ? B| = m 

5、3; n 。,1.1 加法法則與乘法法則,集合論語(yǔ)言：,1.1 加法法則與乘法法則,例3 某種字符串由兩個(gè)字符組成，第一個(gè)字符可選自{a，b，c，d，e}，第二個(gè)字符可選自{1，2，3}，則這種字符串共有5?3 = 15 個(gè)。,例4 從A到B有三條道路，從B到C有兩條道路，則從A經(jīng)B到C有3?2=6 條道路。,加法：得到事件通過(guò)兩種不同的方法。,乘法：得到事件通過(guò)兩個(gè)步驟。,1.1 加法法則與乘法法則,例5 某種樣式的運(yùn)動(dòng)服

6、的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有4?2 = 8種著色方案。,若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話(huà)，則方案數(shù)就不是4 ? 4 = 16， 而只有 4 ? 3 = 12 種。,1.1 加法法則與乘法法則,例6 (1)求小于10000的含1的正整數(shù)的個(gè)數(shù); (2)求小于10000的含0的正整數(shù)的個(gè)數(shù).,(1) 小于10000的不含1的正整數(shù)可看做4位數(shù),但

7、 0000除外. 故有9×9×9×9－1＝6560個(gè). 含1的有：9999－6560=3439個(gè).,(2)“含0”和“含1”不可直接套用。0019含1但不含0。 在組合的習(xí)題中有許多類(lèi)似的隱含的規(guī)定，要特別留神。,9999－7380=2619.,1.1 加法法則與乘法法則,不含0小于10000的正整數(shù)有,含0小于10000的正整數(shù)有,1.1 加法法則與乘法法則,例7,(1)4

8、×3×5＝60,(2)6×3＝18,例8 在1000和9999之間有多少每位上的數(shù)字均不同的奇數(shù)？,個(gè)位數(shù)有5種取法，千位數(shù)有8種取法，百位，十位各有8，7種取法。5×8×8×7＝2240。,1.1 加法法則與乘法法則,例9 由a,b,c,d,e這5個(gè)字符，從中取6個(gè)構(gòu)成字符串，要求：（1）第1，6必為子音字符b，c，d；（2）每個(gè)字符串必有兩個(gè)母音字符a或e，

9、且兩個(gè)母音字符不相鄰；（3）相鄰的兩個(gè)子音字符必不相同。求字符串的個(gè)數(shù)。,由條件（1），兩個(gè)母音字符的位置不能在1，6，又由條件（2），位置只能是（2,4）,（2,5）和（3,5）之一。對(duì)每種格式，母音2×2，相鄰子音3×2，其他兩個(gè)子音3×3，因此答案為 3×（2×2×3×2×3×3）=648,1.2 一一對(duì)應(yīng),“一

10、一對(duì)應(yīng)”概念是一個(gè)在計(jì)數(shù)中極為基本的概念。一一對(duì)應(yīng)既是單射又是滿(mǎn)射。,如我們說(shuō)A集合有n個(gè)元素 |A|=n，無(wú)非是建立了將A中元與[1,n]元一一對(duì)應(yīng)的關(guān)系。,在組合計(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)。,1.2 一一對(duì)應(yīng),例1 在64名選手之間進(jìn)行淘汰賽(即一場(chǎng)的比賽結(jié)果，失敗者退出比賽),最后產(chǎn)生一名冠軍，問(wèn)要舉行幾場(chǎng)比賽？,一種

11、常見(jiàn)的思路是按輪計(jì)場(chǎng)，費(fèi)事。另一種思路是淘汰的選手與比賽(按場(chǎng)計(jì))集一一對(duì)應(yīng)。63場(chǎng)比賽。,1.2 一一對(duì)應(yīng),例2 設(shè)凸n邊形的任意三條對(duì)角線不共點(diǎn)，求對(duì)角線在多邊形內(nèi)交點(diǎn)的個(gè)數(shù)。,可以先計(jì)算對(duì)角線的個(gè)數(shù)，然后計(jì)算交點(diǎn)，但是存在在多邊形內(nèi)無(wú)交點(diǎn)的情形，比較復(fù)雜。,可以考慮對(duì)應(yīng)關(guān)系：多邊形內(nèi)交點(diǎn)to多邊形四個(gè)頂點(diǎn)。,可以證明這是一一映射（映射，單且滿(mǎn)）。,1.3 排列,定義 從n個(gè)不同的元素中，取r個(gè)不重復(fù)的元素，按次

12、序排列，稱(chēng)為從n個(gè)中取r個(gè)的無(wú)重排列。排列的個(gè)數(shù)用P(n,r)表示。當(dāng)r = n 時(shí)稱(chēng)為全排列。,從n個(gè)中取r個(gè)的排列的典型例子是(取球模型):從n個(gè)不同的球中,取出r個(gè),放入r個(gè)不同的盒子里,每盒1個(gè).第1個(gè)盒子有n種選擇,第2個(gè)有n-1種選擇，······，第r個(gè)有n-r+1種選擇。,1.3 排列,例1 由5種顏色的星狀物，20種不同的花排列成如下圖案：兩邊是星狀物

13、，中間是3朵花，問(wèn)共有多少種這樣的圖案？,故由乘法法則有,P(n,r)=n(n-1)······(n-r+1) =n!/(n-r)!,P(n,n)=n!,1.3 排列,兩邊是星狀物，從五種顏色的星狀物中取兩個(gè)的排列的排列數(shù)是 P(5,2)=20,根據(jù)乘法法則得圖案數(shù)為,20種不同的花取3種排列的排列數(shù)是,P(20,3)=20 × 19 × 18

14、=6840,20 ×6840=136800,1.3排列—舉例,例2 A單位有7名代表，B單位有3位代表，排成一列合影要求B單位的3人排在一起，問(wèn)有多少種不同的排列方案。,接上例，若A單位的2人排在隊(duì)伍兩端，B單位的3人不能相鄰，問(wèn)有多少種不同的排列方案？,B單位3人按一個(gè)元素參加排列，P(8,8)×P(3,3),A單位的人排法固定后A*A*A*A*A*A*A，B單位第一人有6種選擇，第二人有5種，第三人有4種

15、，因此答案為P(7,7)×6×5×4,1.3排列—舉例,于是我們只需要計(jì)算Si即可。,例3 試求由{1,3,5,7}組成的不重復(fù)出現(xiàn)的整數(shù)的總和,解：這樣的整數(shù)可以是1位數(shù),2位數(shù),3位數(shù),4位數(shù),若設(shè),是i位數(shù)的總和，則,S=S1+S2+S3+S4,,S1=1+3+5+7=16,,1.3排列—舉例,S2=3(1+3+5+7)10+3(1+3+5+7)= 480+48=528,S4=6(1+3+5+7

16、)1000+6(1+3+5+7)100+6(1+3+5+7)10 +6(1+3+5+7)=96000+9600+960+96=106656,S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7) =9600+960+96=10656,S=16+528+10656+106656=117856,1.4 組合,定義 從 n 個(gè)不同元素中取 r 個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱(chēng)為從n

17、個(gè)中取r個(gè)的無(wú)重組合。,組合的個(gè)數(shù)用C(n,r)表示。 C(n,r)=0,若n < r,或者用 表示。,1.4 組合,從n個(gè)不同的球中,取出r個(gè),放入r個(gè)相同的盒子里,每盒1個(gè)，這是從n個(gè)中取r個(gè)的組合的模型。若放入盒子后再將盒子標(biāo)號(hào)區(qū)別，則又回到排列模型。每一個(gè)組合可有r!個(gè)標(biāo)號(hào)方案。,故有,C(n,r)·r!=P(n,r),,C(n,r)=P(n,r)/r!,1.4組合—舉例,例1 有

18、5本不同的日文書(shū)，7本不同的英文書(shū)， 10本不同的中文書(shū)。 1)取2本不同文字的書(shū)； 2)取2本相同文字的書(shū)； 3)任取兩本書(shū),2) C(5,2)+C(7,2)+C(10,2)=10+21+45=76,1) 5×7+5×10+7×10=155,3) 155+76=231=C(5+7+10,2),1.4組合—舉例,例2 甲和乙兩單位共11個(gè)成員，其中甲單位7人， 乙單位4人，

19、擬從中組成一個(gè)5人小組： 1，要求包含乙單位恰好2人； 2，要求至少包含乙單位2人； 3，要求乙單位某一人與甲單位特定一人不能同 時(shí)在這個(gè)小組。 試求各有多少種方案。,1.4組合—舉例,C(4,2)×C(7,3)C(4,2)×C(7,3)+C(4,3)×C(7,2)+C(4,4)×C(7,1)3）C(10,5)+C(9,4)，或C(11,5)-C(9,3)，,解:,1

20、.5組合—舉例,例3 從[1,300]中取3個(gè)不同的數(shù)，使這3個(gè)數(shù)的和能被3整除，有多少種方案？,解：將[1,300]分成3類(lèi)：,A={i|i≡1(mod 3)}={1,4,7,…,298},B={i|i≡2(mod 3)}={2,5,8,…,299},C={i|i≡3(mod 3)}={3,6,9,…,300}.,1.5組合—舉例,要滿(mǎn)足條件，有四種情形：,1)3個(gè)數(shù)同屬于A; 2)3個(gè)數(shù)同屬于B3)3個(gè)數(shù)同屬于C;

21、 4)A,B,C各取一數(shù).,故共有,1.5組合—舉例,例4 假定有a1,a2,a3,a4,a5, a6, a7,a8這8位成員，兩兩配對(duì)分成4組，試問(wèn)有多少種方案？,解1：a1選擇其同伴有7種可能，選定后,余下6人中某一人選擇其同伴只有5種可能，余下4人，其中某1人有3種選擇可能，在余下的2人只好配成一對(duì)，無(wú)法選擇，故共有,N=7×5×3=105,1.5組合—舉例,解2：分成4組，第一組取法為C(8,2)，余下6人

22、，第二組取法為C(6,2)，第三組取法為C(4,2)，剩下為第四組。但4組的順序是重復(fù)的，因此答案為 C(8,2)×C(6,2)×C(4,2)/P(4,4)=105,解3：8人全排列有P(8,8)。分成4組，每組中2人交換是重復(fù)的，重復(fù)數(shù)為2×2×2×2，另外4組的順序也是重復(fù)的，重復(fù)數(shù)為P(4,4)，因此答案為 P(8,8)/(2×2×2

23、5;2×P(4,4))=105,1.5組合—舉例,例5 某廣場(chǎng)有6個(gè)入口，每個(gè)入口每次只能通過(guò)一輛汽車(chē)，現(xiàn)有9輛車(chē)要開(kāi)進(jìn)廣場(chǎng)，有多少種入場(chǎng)方案？,一個(gè)進(jìn)站方案可以表示成：00011001010100其中“0”表示車(chē)，“1”表示間隔，其中“0”是不同元，“1”是相同元。給“1”這6個(gè)入口只用5個(gè)間隔。任意進(jìn)站方案可表示成上面14個(gè)元素的一個(gè)排列。,1.5組合—舉例,解1 標(biāo)號(hào)可產(chǎn)生5!個(gè)14個(gè)元的全排列。故若設(shè)x為

24、所求方案，則 x ·5!=14! ∴x=14!/5!=726485760,解2 在14個(gè)元的排列中先確定“1”的位置，有C(14,5)種選擇，再確定人的位置，有9！種選擇?！　　」省(14,5)·9!　即所求,解3 實(shí)際上相當(dāng)于14個(gè)位置中選取9輛汽車(chē)的排列，即為P(14,9)。,例6 一個(gè)凸n邊形，它的任何3條對(duì)角線都不交于同一點(diǎn)，問(wèn)它的所有對(duì)角線在

25、凸n邊形內(nèi)部有多少個(gè)交點(diǎn)。,1.5組合—舉例,注意到，每個(gè)交點(diǎn)只有兩個(gè)對(duì)角線通過(guò)，對(duì)應(yīng)了4個(gè)頂點(diǎn)所組成的一個(gè)組合，不同的交點(diǎn)對(duì)應(yīng)的組合也不相同，故共有C(n,4)個(gè)交點(diǎn)。,1.5圓周排列,定義：從n個(gè)不同的數(shù)中不重復(fù)的取出取出r個(gè)沿一圓周排列，稱(chēng)為一個(gè)圓周排列，所有的r-圓周排列數(shù)記為 Q(n,r),注意圓周排列與排列的不同之處在于圓周排列首尾相鄰，如a、b、c、d的4種不同排列 abcd, dabc, cdab, b

26、cda,在圓周排列中都是一個(gè)排列。,1.5圓周排列,從n個(gè)中取r個(gè)的圓周排列的排列數(shù)為,以4個(gè)元素為例,Q(n,r)=P(n,r)/r , 2≤r≤nQ(n,n)=(n-1)!,1.5圓周排列--例子,例1 5顆紅珠子，3顆藍(lán)珠子裝在圓板的四周，試問(wèn)有多少種方案？若要求藍(lán)色珠子不相鄰，又有多少種排列方案？藍(lán)色珠子在一起呢？,若無(wú)要求，則為Q(8,8),若要求藍(lán)色珠子一起，則為Q(6,6)×P(3,3),若要求藍(lán)色