組合數學PPT第一章排列與組合

1、第第1章章排列與組合排列與組合2022-7-82組合數學組合數學n組合數學是研究離散結構的存在、計數、分析和組合數學是研究離散結構的存在、計數、分析和優(yōu)化的一門學科。優(yōu)化的一門學科。n應用領域應用領域: 計算機科學、概率論、社會科學、生計算機科學、概率論、社會科學、生物科學、信息論等。物科學、信息論等。n參考書：參考書： 1. R.A.Rrualdi. Introductory Combinatorics 組合數學組合數學 機械工業(yè)出版社機械工業(yè)出版社 2. 孫淑玲孫淑玲 許胤龍許胤龍. 組合數學引論組合數學引論 中國科學技術大中國科學技術大學出版社學出版社2022-7-831.1基本計數法則

2、基本計數法則n1.1 基本計數法則基本計數法則n加法法則：設事件加法法則：設事件A有有m種產生方式，事件種產生方式，事件B有有n種產生方式，則種產生方式，則“事件事件A或事件或事件B”有有m+n種種產生方式。產生方式。n例例. 一位學生想選修一門數學課程或一門生物一位學生想選修一門數學課程或一門生物課程。若有課程。若有4門數學課程和門數學課程和3門生物課程，則該門生物課程，則該學生有學生有4+3=7種不同的選課方式。種不同的選課方式。2022-7-841.1基本計數法則基本計數法則n乘法法則：設事件乘法法則：設事件A有有m種產生方式，事件種產生方式，事件B有有n種產生方式，則種產生方式，則“事

3、件事件A與事件與事件B”有有mn種產種產生方式。生方式。n例例1.1 設一個符號由兩個字符組成，第設一個符號由兩個字符組成，第1個字符個字符由由a,b,c,d,e組成，第組成，第2個字符由個字符由1,2,3組成，則由組成，則由乘法法則，該符號有乘法法則，該符號有 種方式種方式。1535 2022-7-85 例例1.3 求求比比10000小的正整數中含有數字小的正整數中含有數字1的數的的數的個數。個數。 解解 比比10000小的正整數可以寫為小的正整數可以寫為 的形式。的形式。l 共有共有104-1=9999個個l 其中不含其中不含1的正整數有的正整數有 94-1=6560個個l 所求正整數的個

4、數為所求正整數的個數為 9999-6560=3439個。個。1.1 基本計數法則基本計數法則90 ,4321 iaaaaa2022-7-86例例1.4 求長度為求長度為n的二元碼的數目。的二元碼的數目。 解解 長度為長度為n的二元碼的形式為的二元碼的形式為 由乘法法則，長度為由乘法法則，長度為n的二元碼的數目為的二元碼的數目為 1.1 基本計數法則基本計數法則niaaaain, 2 , 1,1 , 0,21 n22222 2022-7-87例例1.6 求布爾函數求布爾函數 的數目。的數目。 解解 自變量自變量 可能取值的個數為可能取值的個數為 設取值為設取值為 則則n n個變元的布爾函數有個變

5、元的布爾函數有 個。個。 1.1 基本計數法則基本計數法則),(21nxxxf),(21nxxxn2naa21,，naa21 n222 2 f2022-7-881.1 基本計數法則基本計數法則n例例 1.8 ，求能整除，求能整除n的正整數的正整數的個數。的個數。 解解 能整除能整除n的正整數可以寫為如下形式：的正整數可以寫為如下形式： 故能整除故能整除n的正整數的個數為的正整數的個數為 42313117 n40 , 20 , 30 aaaaaa60534 2022-7-89例例1.9 求從求從a,b,c,d,e這這5個字母中取個字母中取6個所組成的字符個所組成的字符串

6、個數。要求串個數。要求(1)第第1 1個和第個和第6個字符必為子音字符；個字符必為子音字符；(2)每一字符串必有兩個母音字符，且兩個母音字母每一字符串必有兩個母音字符，且兩個母音字母不相鄰；不相鄰；(3) 相鄰的兩個子音字符必不相同。相鄰的兩個子音字符必不相同。 解解 符合要求的字符串有以下幾種模式：符合要求的字符串有以下幾種模式： 所求的字符串個數為：所求的字符串個數為： 個。個。 1.1 基本計數法則基本計數法則 64832333 2022-7-810例例 設某地的街道把城市分割成矩形方格，每個設某地的街道把城市分割成矩形方格，每個方格叫做它的塊。某甲從家中出發(fā)上班，向東要方格叫做它的塊。

7、某甲從家中出發(fā)上班，向東要走過走過m塊，向北要走過塊，向北要走過n塊，問某甲上班的路徑有塊，問某甲上班的路徑有多少條？多少條？ 解解 問題可劃為求右圖從點問題可劃為求右圖從點 (0,0)到到(m,n)的路徑數的路徑數: : 每一條從點每一條從點(0,0)到到(m,n)的路徑與的路徑與 一個由一個由m個個x和和n個個y的排列相對應的排列相對應 所求路所求路徑數為：徑數為： 1.2 一一對應一一對應 (0 0,0 0) (m,n)xy),(mnmC 2022-7-811定理定理（Cayley）n個有標號的頂點的樹的數目等個有標號的頂點的樹的數目等于于 。 例例1.12 給定下列樹給定下列樹 可得序

8、列可得序列: 3,1,5,5,1。反之從序列。反之從序列3,1,5,5,1也可以也可以構造出上述樹。構造出上述樹。 1.2 1.2 一一對應一一對應2 nn23754612022-7-812n定義：從定義：從n個不同的元素中，取出個不同的元素中，取出r個按次序排成個按次序排成一列，稱為從這一列，稱為從這n個元素中取個元素中取r個的一個排列，其個的一個排列，其排列數記為排列數記為 . . n由定義顯然有由定義顯然有 (1) (2) 當當r=n時有時有, , 1.3 排列排列),(rnP10! ,)!(!)1()1(),( rnnrnnnrnP)( , 0),(nrrnP )1( ,)1 ,( n

9、nnP!12)1(),(nnnnnP 2022-7-813例例1.13 由由5種顏色的星狀物，種顏色的星狀物，20種不同的花排成種不同的花排成如下的圖案：兩邊是星狀物，中間是如下的圖案：兩邊是星狀物，中間是3朵花，問朵花，問共有多少種這樣的圖案？共有多少種這樣的圖案？ 解解 圖案的形狀為圖案的形狀為 共有共有 種圖案。種圖案。 1.3 排列排列136800)3 ,20()2 , 5()181920()45( PP2022-7-814例例1.14 A單位有單位有7位代表，位代表，B單位有單位有3位代表，排在位代表，排在一列合影，要求一列合影，要求B單位的人排在一起，問有多少單位的人排在一起，問有

10、多少種不同的排列方案？種不同的排列方案？解解 B單位的某一排列作為一個元素參加單位單位的某一排列作為一個元素參加單位A進進行排列，可得行排列，可得 種排列。種排列。 B單位的單位的3人共有人共有 個排列，個排列， 故共有故共有 排列方案。排列方案。1.3 排列排列! 8! 3! 38 2022-7-815例例1.15 若例若例1.14中中A單位的兩人排在兩端，單位的兩人排在兩端，B單位單位的的3人不能相鄰，問有多少種不同的排列方案？人不能相鄰，問有多少種不同的排列方案？解解 共有共有 種方案。種方案。 1.3 排列排列604800)456(!7 2022-7-816例例1.16 求求20000

11、到到70000之間的偶數中由不同的數之間的偶數中由不同的數字所組成的字所組成的5位數的個數。位數的個數。 解解 設所求的數的形式為設所求的數的形式為 其中其中 (1)若若 ，這時，這時e有有4種選擇，有種選擇，有 (2)若若 ，這時，這時e有有5種選擇，有種選擇，有 共有共有 個。個。 1.3 排列排列abcde8 , 6 , 4 , 2 , 0, 62 ea 6 , 4 , 2 a4032)3 , 8(43 P5 , 3 a3360)3 , 8(52 P739233604032 2022-7-817從從n個對象中取個對象中取r個沿一圓周排列的排列數用個沿一圓周排列的排列數用 表示，則有表示，

12、則有 abcd, dabc, cdab, bcda特別地特別地， 1.4 圓周排列圓周排列),(rnQrrnPrnQ),(),( )!1(!),(),( nnnnnnPnnQabcd2022-7-818例例1.19 5顆紅色的珠子，顆紅色的珠子，3顆藍色的珠子裝在圓板顆藍色的珠子裝在圓板的四周，試問有多少種排列方案？若藍色的珠子的四周，試問有多少種排列方案？若藍色的珠子不相鄰又有多少種排列方案？藍色珠子在一起又不相鄰又有多少種排列方案？藍色珠子在一起又如何？如何？ 解解 (1)有有 種；種； (2)有有 種；種； (3)有有 種。種。1.4 圓周排列圓周排列! 71440)345(! 4 !

13、35 2022-7-819例例1.20 5對夫妻出席一宴會，圍一圓桌坐下，問對夫妻出席一宴會，圍一圓桌坐下，問有幾種方案？若要求每對夫妻相鄰又有多少種方有幾種方案？若要求每對夫妻相鄰又有多少種方案？案？ 解解 (1) 種方案；種方案； (2) 種方案。種方案。1.4 圓周排列圓周排列! 97683224245 !2022-7-820定義定義 從從n個不同的元素中，取出個不同的元素中，取出r個而不考慮其個而不考慮其次序，稱為從這次序，稱為從這n個元素中取個元素中取r個組合，其組合數個組合，其組合數記為記為 。 1.5 組合組合),(rnC!),(),(rrnCrnP !),(),(rrnPrnC

14、 2022-7-821例例1.21 從從1300之間任取之間任取3個不同的數，使得這個不同的數，使得這3個數個數的和正好被的和正好被3除盡，問共有幾種方案？除盡，問共有幾種方案？ 解解 將這將這300個數按照其被個數按照其被3除所得的余數分為三組：除所得的余數分為三組： A=1,4,298，B=2,5,299，C=3,6,300 三個數取自集合三個數取自集合A：有：有C(100,3)種方案；種方案； 三個數取自集合三個數取自集合B：有：有C(100,3)種方案；種方案； 三個數取自集合三個數取自集合C：有：有C(100,3)種方案；種方案； 三個數分別取自集合三個數分別取自集合A、B、C：有：

15、有1003種方案；種方案； 所求的方案數為：所求的方案數為：3C(100,3)+1003=1485100 1.5 組合組合2022-7-822例例1.22 甲和乙兩單位共甲和乙兩單位共11個成員，其中甲單位個成員，其中甲單位7人，乙單位人，乙單位4人，擬從中組成一個人，擬從中組成一個5人小組；人小組； (1) 若要求必須包含乙單位若要求必須包含乙單位2人；人； (2) 若要求至少包含乙單位若要求至少包含乙單位2人；人； (3) 若要求乙單位某一人與甲單位某一人不能同時若要求乙單位某一人與甲單位某一人不能同時在這個小組；在這個小組； 試分別求各有多少種方案。試分別求各有多少種方案。 解解 (1)

16、 (2) (3) 1.5 組合組合)3 , 7()2 , 4(CC)1 , 7()4 , 4()2 , 7()3 , 4()3 , 7()2 , 4(CCCCCC 37884462)3 , 9()5 ,11( CC2022-7-823例例1.23 假定有假定有8位成員，兩兩配對分成位成員，兩兩配對分成4組，問有組，問有多少種分配方案？多少種分配方案？解解 方法方法1： 將將8位成員排列，共有位成員排列，共有8!個排列，每個排列兩個排列，每個排列兩兩劃分，分成兩劃分，分成4組，其重復數為組，其重復數為24.4!，所求分配方，所求分配方案數為案數為 1.5 組合組合 105! 42! 84 202

17、2-7-824 方法方法2 2： 將將8 8個人分為個人分為4 4組，第組，第1 1組有組有 種選擇，第種選擇，第2 2組有組有 種選擇，第種選擇，第3 3組有組有 種選擇，第種選擇，第4 4組有組有 種選擇，但由于各組與順序無關，種選擇，但由于各組與順序無關，故所求分配方案數為：故所求分配方案數為：1.51.5 組合組合 4 3 2 1 ,)2 , 8(C),( 26C)2 , 4(C),( 22C! 42! 8! 4)2 , 2()2 , 4()2 , 6()2 , 8(4 CCCC2022-7-825例例1.24某廣場有某廣場有6個入口處，每個入口處每次只能個入口處，每個入口處每次只能通

18、過一輛汽車，有通過一輛汽車，有9輛汽車要開進廣場，問有多輛汽車要開進廣場，問有多少種入場方案？少種入場方案？解解 方法方法1： 9輛汽車和輛汽車和5個標志的一個排列可表示一種入場方個標志的一個排列可表示一種入場方案，其重復數為案，其重復數為5!，所求方案數為，所求方案數為 1.5 組合組合9 8 7 6 5 4 3 2 1 ! 5!142022-7-826方法方法2： 在在9輛汽車和輛汽車和5個標志共個標志共14個位置中，首先選擇個位置中，首先選擇5個個作為標志的位置，這有作為標志的位置，這有 種選擇，對每一種選擇，對每一種選擇，將種選擇，將9輛汽車依次填入剩余的位置，這有輛汽車依次填入剩余的

19、位置，這有 種填入方式，故所求方案數為種填入方式，故所求方案數為 1.5 組合組合)5 ,14(C! 9! 5!14! 9)5 ,14( C2022-7-827例例1.25 求求5位數中至少出現一個位數中至少出現一個6，而被，而被3整除的整除的數的個數。數的個數。 正整數正整數n能夠被能夠被3整除的的充要條件是整除的的充要條件是n的各個數的各個數字之和能夠被字之和能夠被3整除。整除。 設設 因為因為 ，所以，所以 于是于是 iff 1.5 組合組合0111101010aaaankkkk )3(mod 110 3) (mod 1010100110111aaaaaaaankkkkkk 3) 0(m

20、od n3) (mod 0011 aaaakk2022-7-828l5位數位數 共有共有90000個個l被被3整除的有整除的有30000個個l在這在這30000個數中不包含個數中不包含6的數有的數有 個個l所求個數為所求個數為 30000-17496=125041.5 組合組合174963983 54321aaaaa2022-7-829定理定理 在在n!中，質數中，質數p的最高冪的最高冪 其中其中 。 1.5 組合組合 mpnpnpnnp2) !(1 mmpnp2022-7-830例例6求求1000!的末尾有幾個的末尾有幾個0 解解 1000!的末尾所含的末尾所含0的個數為的個數為1000!的

21、因子分解的因子分解中中2和和5的冪的最小者的冪的最小者 1000!因子分解中因子分解中5的冪為：的冪為： 故故1000!的末尾有的末尾有249個個01.5 組合組合249184020051000510005100051000432 2022-7-831習題習題n1.2n1.4n1.5n1.8n1.92022-7-832允許重復的排列允許重復的排列n定理定理 多重集合多重集合 的的r排列數為排列數為n例例 用用26個英文字母可以構造出多少個個英文字母可以構造出多少個4個元音字母長個元音字母長度為度為8的字符串的字符串? 解解 該問題是要求該問題是要求 的包含的包含4個元個元音字母的音字母的8排列

22、數排列數. 在長度為在長度為8的字符串中的字符串中, 4個元音字母出現的位置有個元音字母出現的位置有 種種 每種元音出現的位置有每種元音出現的位置有 個排列個排列 所求字符串的個數為所求字符串的個數為,21kaaaS rk,zbaM )4 , 8(C44215)4 , 8( C44215 2022-7-833n定理定理 多重集合多重集合 的全排列數為的全排列數為 其中其中n證證 排列的個數為排列的個數為允許重復的排列允許重復的排列,2211kkanananS nnnnk 21!21knnnn),(),(),(121211kknnnnnCnnnCnnC !21knnnn 2022-7-834n例

23、例1.24某廣場有某廣場有6個入口處，每個入口處每次只能個入口處，每個入口處每次只能通過一輛汽車，有通過一輛汽車，有9輛汽車要開進廣場，問有多少輛汽車要開進廣場，問有多少種入場方案？種入場方案？n解解 方法方法1： 9輛汽車和輛汽車和5個標志的一個排列可表示一種入場方個標志的一個排列可表示一種入場方案，所求方案數為案，所求方案數為 允許重復的排列允許重復的排列9 8 7 6 5 4 3 2 1 ! 5!142022-7-835n 例例 從從1,2,3中取中取2個允許重復的組合為個允許重復的組合為 1,1, 1,2, 1,3, 2,2, 2,3, 3,3n定理定理1.2 在在n個不同的元素中取個

24、不同的元素中取r個進行組合，若允個進行組合，若允許重復，則組合數為許重復，則組合數為 證證 設設n個不同的元素為個不同的元素為1,2,3,n 若若 是一個允許重復的是一個允許重復的r組合，不妨設組合，不妨設 ，可構造一個可構造一個 上的不上的不 允許重復的允許重復的r組合組合1.8.1 允許重復的組合允許重復的組合),(rrnC1 ,raaa21raaa 21,121 rn,1121 raaar2022-7-8361.8 1.8 允許重復的組合允許重復的組合n反之給定一個反之給定一個 上的不允許重復的上的不允許重復的r組組合合 ，我們可以如下得到一個我們可以如下得到一個1,2,n上的上的一個允

25、許重復的一個允許重復的r組合組合 。 故故n個元素的允許重復的個元素的允許重復的r組合與組合與n+r-1個元素的不允個元素的不允許重復的組合之間有一一對應關系，故它們的組合數許重復的組合之間有一一對應關系，故它們的組合數相同，于是定理得證。相同，于是定理得證。,121 rn,rbbb21,1121 rbbbr2022-7-837n定理定理1.3 r個無區(qū)別的球放進個無區(qū)別的球放進n個有標志的盒子，而每個有標志的盒子，而每盒放的球可多于一個，則共有盒放的球可多于一個，則共有 種方案種方案n例例1.28 試問試問 有多少項？有多少項？ 解解 這相當于將這相當于將4個無區(qū)別的球放進個無區(qū)別的球放進3

26、個有標志的盒子，個有標志的盒子，而每盒放的球可多于一個，故共有而每盒放的球可多于一個，故共有 項項: :1.8 允許重復的組合允許重復的組合),(rrnC1 4)(zyx )4 , 134( C)4 , 6(C 15)2 , 6( C322222334,xyzxyxyzxzxyxx44322223,zyzyzyxyzzxyxz2022-7-838n例例 從從 1,2,3,4,5,6 中取中取 3 個作不相鄰的組合有：個作不相鄰的組合有：1,3,5, 1,3,6, 1,4,6, 2,4,6n定理定理1.4 從從A=1,2,n中取中取r個作不相鄰的的組合，個作不相鄰的的組合，其組合數為其組合數為1

27、.8.2 不相鄰組合不相鄰組合 rrn12022-7-839n證證 若若 是一個不相鄰的是一個不相鄰的r組合，不妨設組合，不妨設 ，可構造一個可構造一個 上的上的r組組合合 。 反之，給定一個反之，給定一個 上的上的r組合組合 可以如下得到一個可以如下得到一個1,2,n上的一個上的一個不相鄰不相鄰 的的r組合組合1.8.2 1.8.2 不相鄰組合不相鄰組合,21raaaraaa 211, 2 , 1 rn1, 1,21 raaar1, 2 , 1 rn,21rbbb1, 1,21 rbbbr2022-7-840n例例 證明證明k個連續(xù)的正整數的乘積能被個連續(xù)的正整數的乘積能被k!整除整除 。

28、證證 不妨設不妨設k個連續(xù)的正整數為個連續(xù)的正整數為n，n+1，n+k-1。 考慮從考慮從n+k-1個元素中取個元素中取k個的組合，其組合數為：個的組合，其組合數為： 由于由于 是一個正整數，所以有是一個正整數，所以有 1.9 組合的解釋組合的解釋!)(),(knknknkknC211 nknknk)( | !21 ),(kknC1 2022-7-841n(1) 組合意義：組合意義：n個個元素的元素的r- -子集與子集與n-r子集一一對應，子集一一對應，n個元素的個元素的r- -子集的個數為子集的個數為 ，n-r子集的個數子集的個數為為 ，故等式成立。，故等式成立。n例例 3個元素個元素1,2

29、,3的的2- -子集與子集與1- -子集一一對應。子集一一對應。 1.9 組合的解釋組合的解釋),(),(rnnCrnC ,132231321),(rnC),(rnnC 2022-7-842(2) n組合意義：從這組合意義：從這n個元素中任取一個元素個元素中任取一個元素a， 個個組合可以如下分為兩類：組合可以如下分為兩類：l不含有元素不含有元素a的的r組合，其組合數為組合，其組合數為 l含元素含元素a的的r組合，其組合數為組合，其組合數為 1.91.9 組合的解釋組合的解釋),(),(),(111 rnCrnCrnC),(rnC1 ),(11 rnC),(rnC2022-7-8431.9 組合

30、的解釋組合的解釋(3) 組合意義組合意義1：任取任取r個元素個元素 l 不包含不包含 ，其組合數為，其組合數為 l 包含包含 ，但不包含，但不包含 ，其組合數為，其組合數為l 包含包含 ，其組合數為，其組合數為 0111nrrnrrnrrnraaa,211a),(rrnC 1a2a),(11 rrnCraaa,21),(),(001nCnC 2022-7-844n組合意義組合意義2：1.91.9 組合的解釋組合的解釋(0,0)(0,0)(n+1,r)(n,0)(n,0)(n,r)2022-7-8451.9 組合的解釋組合的解釋n由等式由等式(3)我們可以得到若干有用的公式：我們可以得到若干有用

31、的公式：nS 21121)n(n ),(),(),(),(1231201 nnCCCC),(),(2111 nCnnC),(),(),(),(1131211nCCCC 2022-7-8461.9 組合的解釋組合的解釋)(14332212 nnS),11C(C(4,2)C(3,1)2C(2,0) nn321312(2)(!)( nnnnnn),(),(),(),(212242232222 nCCCC),(),(322122 nCnnC2022-7-8471.9 組合的解釋組合的解釋(4)n代數證明：代數證明： )!( !)!(!)!( !)!( !rlrlnnrlrllnlnrlln nlrrl

32、rnrnrlln ,)!()!( !)!()!()!()!( !lnrlrnlnrlrnrnrnrlrnrn 2022-7-848組合意義：等式的左端可以看作是先從組合意義：等式的左端可以看作是先從n個元素中個元素中取取 個組合，然后對每一個個組合，然后對每一個 組合，從中再取組合，從中再取r個個元素的組合。這相當于直接從元素的組合。這相當于直接從n個元素中取個元素中取r個元素個元素的組合，但每個的組合，但每個r組合重復了組合重復了 次。次。1.9 組合的解釋組合的解釋 lnrnll2022-7-8491.9 組合的解釋組合的解釋n(5) n組合意義：用兩種不同的方式計算組合意義：用兩種不同的

33、方式計算n個元素的集合個元素的集合S的子集的個數的子集的個數 S 的所有子集的個數為的所有子集的個數為 另一方面，另一方面，S有有n個元素，在構成個元素，在構成S的子集時，的子集時，S的每的每個元素都有兩種選擇，或在該子集中，或不在該子個元素都有兩種選擇，或在該子集中，或不在該子集中，由乘法法則知，集中，由乘法法則知，S有有 個子集。個子集。),(),(),(),(nnCnCnCnC 210nnnCnCnCnC2210 ),(),(),(),(n22022-7-850n(6) n代數證明：在等式代數證明：在等式 中令中令x=1, y=- -1便得便得n組合意義：在組合意義：在n個元素的集合個元

34、素的集合S中取中取r組合，組合，r為奇數為奇數的組合數目等于的組合數目等于r為偶數的組合數目為偶數的組合數目。 取定取定S中的一個元素中的一個元素a，對，對S的任一個奇組合的任一個奇組合 若若 則則 對應于偶組合對應于偶組合 若若 則則 對應于偶組合對應于偶組合 1.9 組合的解釋組合的解釋0210 ),(),(),(),(nnCnCnCnCnnnnynnCyxnCxnCyx),(),(),()( 110S ,Sa aS S ,Sa aS S 2022-7-851n反之，對反之，對S的任一個偶組合的任一個偶組合 若若 則則 應于奇組合應于奇組合 若若 ，則，則 對應于奇組合對應于奇組合 。 顯

35、然這是奇組合與偶組合之間的一一對應關系。故顯然這是奇組合與偶組合之間的一一對應關系。故等式成立。等式成立。1.91.9 組合的解釋組合的解釋S ,Sa S aS Sa S aS 2022-7-852n例例 考慮四個元素的集合考慮四個元素的集合a,b,c,d，其所有的奇數組其所有的奇數組合為合為 a, b, c, d, a,b,c, a,b,d, a,c,d, b,c,d 取元素取元素a，其相應的偶數組合有：其相應的偶數組合有： ，a,b, a,c, a,d, b,c, b,d, c,d, a,b,c,d。1.9 組合的解釋組合的解釋2022-7-853n(7)n代數證明：考慮等式代數證明：考慮

36、等式兩邊的系數便得兩邊的系數便得1.9 組合的解釋組合的解釋 0110nrmrnmrnmrnmnmnmxxx)()()( 1112022-7-854n組合意義組合意義1：從：從m+n個有標志的球中取個有標志的球中取r個，這個，這m+n個球中有個球中有m個是紅的，有個是紅的，有n個是藍的，所有的個是藍的，所有的r組合組合不外乎以下幾種可能：不外乎以下幾種可能：l 0個紅球，個紅球，r個籃球個籃球: :l 1個紅球，個紅球，r-1個籃球個籃球: : l r個紅球，個紅球，0個籃球個籃球: :1.9 組合的解釋組合的解釋 rnm0 11rnm 0nrm2022-7-855n(8) 證證 在等式在等式

37、(7)中取中取r=m便得便得1.91.9 組合的解釋組合的解釋nmmnmmnmnmmnm 1100, 0011nmmnmmmnmm 0110nmmmnmmnmmnm2022-7-856n當當m=n時有時有1.9 組合的解釋組合的解釋22222102 nnnnnnn2022-7-857n例例 (a)用組合方法證明用組合方法證明 和和 都是整數都是整數. 證證 考慮將考慮將2n個有標志的球放入個有標志的球放入n個有區(qū)別的盒子個有區(qū)別的盒子中，每盒中，每盒2個球，其放法數為：個球，其放法數為： 1.9 組合的解釋組合的解釋nn22 )!(nnn323 )!(nnnnnnnn)()!() !()!(!

38、)(!)(2222212 23222 2122 2212222222222)(nnnnn2022-7-858n類似地考慮將類似地考慮將3n個有標志的球放入個有標志的球放入n個有區(qū)別的盒個有區(qū)別的盒子中，每盒子中，每盒3個球，可得其放法數為：個球，可得其放法數為： 故故 為整數為整數1.9 組合的解釋組合的解釋nnnnn32333)!() !()!( nnn323 )!(2022-7-859n(b)(b)證明證明 是整數。是整數。 n證考慮將證考慮將n2個有標志的球放入個有標志的球放入n個有區(qū)別的盒子中，個有區(qū)別的盒子中，每盒每盒n個球，其放法數為：個球，其放法數為： 當當n個盒子無區(qū)別時，其方

39、法數為：個盒子無區(qū)別時，其方法數為： 1.9 組合的解釋組合的解釋12 nnn) !()!(nnnnnnnnnnnnnnn) !()!()(2222212 122 nnnnnnn) !()!() !( !)!(2022-7-8601.9 組合的解釋組合的解釋n例例 證明：證明： 其中其中k, n為非負整數。為非負整數。 證證 11110 knknknkk knknkkknknkkkknknknknknkn110 11010 111 1112022-7-861 1.16 1.20 1.22 1.27習題習題2022-7-862 例例1.30 7位科學家從事一項機密研究，實驗室裝有位科學家從事一項

40、機密研究，實驗室裝有“電子鎖電子鎖”，每位科學家都有一把打開，每位科學家都有一把打開“電子鎖電子鎖”的鑰匙。為了安全起見，必須有的鑰匙。為了安全起見，必須有4 4位到場方可打開位到場方可打開“電子鎖電子鎖”。試問該。試問該“電子鎖電子鎖”必須具備多少特征？必須具備多少特征？每位科學家的每位科學家的“鑰匙鑰匙” ” 應具有多少這些特征？應具有多少這些特征？ 解解 因為任意三個人在一起，至少缺少電子鎖的因為任意三個人在一起，至少缺少電子鎖的 一種特征，而且對于兩個不同的三人組，必至少缺一種特征，而且對于兩個不同的三人組，必至少缺少兩種特征，故電子鎖至少應具備少兩種特征，故電子鎖至少應具備 特征。特

41、征。1.10 應用舉例應用舉例352356737 ),(C2022-7-863 對于任一位科學家，其余對于任一位科學家，其余6個人中任意三個人在場，個人中任意三個人在場，至少缺少一個他所具有的特征而無法打開大門，且至少缺少一個他所具有的特征而無法打開大門，且對于兩個不同三人組，必至少缺少兩種特征，所以對于兩個不同三人組，必至少缺少兩種特征，所以每個人的每個人的“鑰匙鑰匙” 至少應有至少應有 種特征。種特征。1.10 應用舉例應用舉例202345636 ),(C2022-7-864n例例1.31 4個全同的質點，總能量為個全同的質點，總能量為4E0，其中，其中E0是常數。是常數。每個質點的能級可

42、能為每個質點的能級可能為kE0，k=0,1,2,3,4。 (a) 若質點服從若質點服從Bose-Einstein分布，即能級為分布，即能級為kE0的的質點可以有質點可以有k2+1種狀態(tài)，而且同能級的質點可以處于種狀態(tài)，而且同能級的質點可以處于相同的狀態(tài)，問有多少種不同的分布圖象？相同的狀態(tài)，問有多少種不同的分布圖象？ (b) 若質點服從若質點服從Fermi-Dirac分布，即能級為分布，即能級為kE0的的質點可以有質點可以有2(k2+1)種狀態(tài)，而且不允許同能級的兩種狀態(tài)，而且不允許同能級的兩個質點有相同的狀態(tài)，問有多少種不同的分布圖象？個質點有相同的狀態(tài)，問有多少種不同的分布圖象？1.10

43、應用舉例應用舉例2022-7-865n解解 總能量為總能量為4E0的四個質點有以下的四個質點有以下5種可能的分布：種可能的分布： (0,0,0,4),(0,0,1,3),(0,0,2,2)，(0,1,1,2)，(1,1,1,1) (a) 根據根據kE0能級的質點可以有能級的質點可以有1+k2種不同的狀態(tài)，種不同的狀態(tài)，故各能級的狀態(tài)為故各能級的狀態(tài)為1.10 應用舉例應用舉例k012342狀態(tài)數狀態(tài)數1710512022-7-866 對應于對應于(0, 0, 0, 4)有有 種圖象。種圖象。 對應于對應于(0, 0, 1, 3)有有 種圖象。種圖象。 對應于對應于(0, 0, 2, 2)有有

44、對應于對應于(0, 1, 1, 2)有有 對應于對應于(1, 1, 1, 1)有有 所求圖象數為：所求圖象數為：N=17+20+15+15+5=72 1.10 應用舉例應用舉例17171 201021 154621251 ),(),(CC151521221 ),(),(CC5454142 ),(),(CC2022-7-867n(2) 根據根據kE0能級的質點可以有能級的質點可以有2(1+k2)種不同的狀種不同的狀態(tài)，故各能級的狀態(tài)為態(tài)，故各能級的狀態(tài)為 對應于對應于(0,0,0,4)有有 0 種圖象。種圖象。 對應于對應于(0,0,1,3)有有 種圖象。種圖象。 1.10 應用舉例應用舉例k0

45、12344狀態(tài)數狀態(tài)數3420102801201422 ),(),(),(CCC2022-7-868 對應于對應于(0, 0, 2, 2)有有 對應于對應于(0, 1, 1, 2)有有 對應于對應于(1, 1, 1, 1)有有 種圖象。種圖象。 故所求的圖象數為故所求的圖象數為 N=0+80+45+120+1=246 1.10 應用舉例應用舉例4521022 ),(),(CC1201102412 ),(),(),(CCC144 ),(C2022-7-869n例例1.33從從(0,0)點到達點到達(m,n)點點(ma，問有多少條路徑？，問有多少條路徑？n解解 路徑的第一步必然是從路徑的第一步必然

46、是從(0,0)點到達點到達(0,1)點，問題點，問題等價于求從等價于求從(0,1)點到達點到達(m,n)的滿足條件的路徑數。的滿足條件的路徑數。所求路徑數為所求路徑數為1.10 應用舉例應用舉例)(!)!(!)!()!()!( !)!(mnnmnmnmnmnmnm 11111 111mnmmnm2022-7-8701.10 1.10 應用舉例應用舉例(0,0)(0,0)(1,0)(1,0)(0,1)(0,1)y=xy=x(m,n(m,n) )2022-7-871n例例1.34 一場音樂會的票價為一場音樂會的票價為50元一張，排隊買票的元一張，排隊買票的顧客中有顧客中有m位持有位持有50元的鈔票

47、，元的鈔票，n位持有位持有100元的鈔票。元的鈔票。售票處沒有準備售票處沒有準備50元的零錢，試問有多少種排隊的辦元的零錢，試問有多少種排隊的辦法使購票能順利進行，不出現找不出零錢的狀態(tài)。假法使購票能順利進行，不出現找不出零錢的狀態(tài)。假定每位顧客只限買一張，而且定每位顧客只限買一張，而且 。n解如圖所示，所求排隊的方法數為從點解如圖所示，所求排隊的方法數為從點 到到點點 ，且不越過直線，且不越過直線OC的路徑數。而這等于的路徑數。而這等于從點從點 到到 的路徑數減去從點的路徑數減去從點 到到 的到達的到達直線直線OC的路徑數。的路徑數。 1.10 應用舉例應用舉例nm ),( 00O),(nm

48、M),( 01A), 1( nmM )1 , 0(B), 1( nmM 2022-7-872n而后者等于從點而后者等于從點 到點到點 的路徑數，的路徑數，故所求的排隊方法數為故所求的排隊方法數為 1.10 應用舉例應用舉例),( 10B),( nmM1 1mnmmnm 11)!()!()!(!)!( nmnmnmnm 11)!(!)!()(nmnmnm 2022-7-8731.10 應用舉例應用舉例C(n,n)O(0,0)A(1,0)B(0,1)M(m+1,n)M(m,n)2022-7-8741.10 應用舉例應用舉例n證證 2: 將將50元和元和100元的鈔票分別記為元的鈔票分別記為1和和-

49、1. .則問則問題成為證明由題成為證明由m個個1和和n個個-1構成的構成的m+n項項 其部分和滿足其部分和滿足 的數列的個數等于的數列的個數等于nmaaa ,21), 2 , 1( , 021nmkaaak 1mnmmnm2022-7-8751.10 應用舉例應用舉例n由由m個個1和和n個個-1構成的構成的m+n項的數列的個數等于項的數列的個數等于n考慮考慮m個個1和和n個個-1的不可接受的序列的不可接受的序列n因為序列是不可接受的因為序列是不可接受的, ,所以存在一個最小的所以存在一個最小的k使得部分和使得部分和 mnmnmaaa ,21021 kaaa2022-7-8761.10 1.10

50、 應用舉例應用舉例n將前將前k個字符中的個字符中的1，- -1互換，則得到一個有互換，則得到一個有m+1個個1和和n-1個個- -1的序列。的序列。n反之，任給一個有反之，任給一個有m+1個個1和和n-1個個- -1組成的字符組成的字符串，則存在最小的串，則存在最小的k，使得，使得 將將前前k個字符中的個字符中的1，- -1互換，則得到一個有互換，則得到一個有m個個1和和n個個- -1的字符串，且該的字符串，且該字符串不合乎要求字符串不合乎要求。n故不可接受序列的個數為故不可接受序列的個數為 1mnm021 kaaa2022-7-877n數字通訊中的一個重要問題是設計信道的編碼器數字通訊中的一

51、個重要問題是設計信道的編碼器譯碼器對。而在設計編碼器譯碼器時的一個關鍵譯碼器對。而在設計編碼器譯碼器時的一個關鍵問題是考慮所設計碼的糾錯能力。問題是考慮所設計碼的糾錯能力。n例例 編碼編碼00, 01, 10, 11無法查錯。無法查錯。 編碼編碼00, 11可以查單錯，但無法糾錯?？梢圆閱五e，但無法糾錯。 編碼編碼001, 110不但可以查單錯，也可以糾單錯。不但可以查單錯，也可以糾單錯。1.10 應用舉例應用舉例2022-7-878n定義定義 若若 ， 是兩個用是兩個用n位二進制數表示的碼，位二進制數表示的碼， 設設 ， ，若，若 個數為個數為 ，則記為則記為 ，稱之為，稱之為 ， 碼的碼的 Hamming距離。距離。 定理定理 對任意的碼對任意的碼 下列三角不等式成立：下列三角不等式成立： 證證 設設 若若 ，則，則 ， 中至少有一個成立，故不等式成立。中至少有一個成立，故不等式成立。 1.10 應用舉例應用舉例naaaa21 nbbbb21 abiiba llabdbad ),(),(ab,cba),(),(),(cadcbdbad ,21ncccc iica iiba iicb 2022-7-879n最小距離譯碼準則：給定碼最小距離譯碼準則：給定碼C，設接受字為，設接受字為 ，將，將 譯為譯為C中與中與 有最小有最小Ham