chap1-1排列組合

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

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

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

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

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

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

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

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

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

10、一對應”概念是一個在計數中極為基本的概念。一一對應既是單射又是滿射。,如我們說A集合有n個元素 |A|=n，無非是建立了將A中元與[1,n]元一一對應的關系。,在組合計數時往往借助于一一對應實現(xiàn)模型轉換.,比如要對A集合計數，但直接計數有困難，于是可設法構造一易于計數的B，使得A與B一一對應。,1.2 一一對應,例1 在64名選手之間進行淘汰賽(即一場的比賽結果，失敗者退出比賽),最后產生一名冠軍，問要舉行幾場比賽？,一種

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

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

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

14、=6840,20 ×6840=136800,1.3排列—舉例,例2 A單位有7名代表，B單位有3位代表，排成一列合影要求B單位的3人排在一起，問有多少種不同的排列方案。,接上例，若A單位的2人排在隊伍兩端，B單位的3人不能相鄰，問有多少種不同的排列方案？,B單位3人按一個元素參加排列，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排列—舉例,于是我們只需要計算Si即可。,例3 試求由{1,3,5,7}組成的不重復出現(xiàn)的整數的總和,解：這樣的整數可以是1位數,2位數,3位數,4位數,若設,是i位數的總和，則,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 個不同元素中取 r 個不重復的元素組成一個子集，而不考慮其元素的順序，稱為從n

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

18、5本不同的日文書，7本不同的英文書， 10本不同的中文書。 1)取2本不同文字的書； 2)取2本相同文字的書； 3)任取兩本書,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個成員，其中甲單位7人， 乙單位4人，

19、擬從中組成一個5人小組： 1，要求包含乙單位恰好2人； 2，要求至少包含乙單位2人； 3，要求乙單位某一人與甲單位特定一人不能同 時在這個小組。 試求各有多少種方案。,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個不同的數，使這3個數的和能被3整除，有多少種方案？,解：將[1,300]分成3類：,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組合—舉例,要滿足條件，有四種情形：,1)3個數同屬于A; 2)3個數同屬于B3)3個數同屬于C;

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

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

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

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

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

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