組合數(shù)學第一張排列與組合課件

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

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

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

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

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

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

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

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

9、,( nnnP!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 求求2

11、0000到到70000之間的偶數(shù)中由不同的數(shù)之間的偶數(shù)中由不同的數(shù)字所組成的字所組成的5位數(shù)的個數(shù)。位數(shù)的個數(shù)。 解解 設(shè)所求的數(shù)的形式為設(shè)所求的數(shù)的形式為 其中其中 (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個沿一圓周排列的排列數(shù)用個沿一圓周排列的排列數(shù)用 表示，則

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

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

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

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

16、 (1) (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組，其重復(fù)數(shù)為組，其重復(fù)數(shù)為24.4!，所求分配方，所求分配方案數(shù)為案數(shù)為 1.5 組合組合 105! 42! 84

17、 2022-7-824 方法方法2 2： 將將8 8個人分為個人分為4 4組，第組，第1 1組有組有 種選擇，第種選擇，第2 2組有組有 種選擇，第種選擇，第3 3組有組有 種選擇，第種選擇，第4 4組有組有 種選擇，但由于各組與順序無關(guān)，種選擇，但由于各組與順序無關(guān)，故所求分配方案數(shù)為：故所求分配方案數(shù)為：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個標志的一個排列可表示一種入場方個標志的一個排列可表示一種入場方案，其重復(fù)數(shù)為案，其重復(fù)數(shù)為5!，所求方案數(shù)為，所求方案數(shù)為 1.5 組合組合9 8 7 6 5 4 3 2 1 ! 5!142022-7-826方法方法2： 在在9輛汽車和輛汽車和5個標志共個標志共14個位置中，首先選擇個位置中，首先選擇5個個作為標志的位置，這有作為標志的位置，這有 種選擇，對每一種選擇，對每一種選擇，將種選擇，將9輛汽車依次填入剩余的位置，這有輛汽車依次填

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

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

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

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

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

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

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

26、球放進3個有標志的盒子，個有標志的盒子，而每盒放的球可多于一個，故共有而每盒放的球可多于一個，故共有 項項: :1.8 允許重復(fù)的組合允許重復(fù)的組合),(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個作不相鄰的的組合，個作不相鄰的的組合，其組合數(shù)為其組

27、合數(shù)為1.8.2 不相鄰組合不相鄰組合 rrn12022-7-839n證證 若若 是一個不相鄰的是一個不相鄰的r組合，不妨設(shè)組合，不妨設(shè) ，可構(gòu)造一個可構(gòu)造一個 上的上的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ù)的正整數(shù)的乘積能被個連續(xù)的正整數(shù)的乘積能被k!整除整

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

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

30、9 組合的解釋組合的解釋(3) 組合意義組合意義1：任取任取r個元素個元素 l 不包含不包含 ，其組合數(shù)為，其組合數(shù)為 l 包含包含 ，但不包含，但不包含 ，其組合數(shù)為，其組合數(shù)為l 包含包含 ，其組合數(shù)為，其組合數(shù)為 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代數(shù)證明：代數(shù)證明： )!( !)!(!)!( !)!( !rlrlnnrlrllnlnrlln n

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

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

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

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

36、明：考慮等式兩邊的系數(shù)便得兩邊的系數(shù)便得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)用組合方法證明用組合方法證明 和和 都是整數(shù)都是整數(shù). 證證 考慮將考慮將2n個有標志的球放入個有標志的球放入n個有區(qū)別的盒子個有區(qū)別的盒子中，每盒中，每盒2個球，其放法數(shù)為：個球，其放法數(shù)為： 1.9 組合的解釋組合的解釋nn22 )!(nnn323 )!(nnnnnnnn)()!() !(

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

39、時，其方法數(shù)為：個盒子無區(qū)別時，其方法數(shù)為： 1.9 組合的解釋組合的解釋12 nnn) !()!(nnnnnnnnnnnnnnn) !()!()(2222212 122 nnnnnnn) !()!() !( !)!(2022-7-8601.9 組合的解釋組合的解釋n例例 證明：證明： 其中其中k, n為非負整數(shù)。為非負整數(shù)。 證證 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位到場方可打開位到場方可打開“電子鎖電子鎖”。試問該。試問該“電子鎖電子鎖”必須具備多少特征？必須具備多少特征？每位科學家的每位科學家的“鑰匙鑰匙” ” 應(yīng)具有多少這些特征？應(yīng)具有多少這些特征？ 解解 因為任意三個人在一起，至少缺少電子鎖的因為任意三個人在一起，至少缺少電子鎖的 一種特征，而且對于兩個不同的三人組，必至少缺一種特征，而且對于兩個不同的三人組，必至少缺少兩種特征，故電子鎖至少應(yīng)具備少兩種特征，故電子鎖至少應(yīng)具備

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

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

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

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

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

46、一步必然是從(0,0)點到達點到達(0,1)點，問題點，問題等價于求從等價于求從(0,1)點到達點到達(m,n)的滿足條件的路徑數(shù)。的滿足條件的路徑數(shù)。所求路徑數(shù)為所求路徑數(shù)為1.10 應(yīng)用舉例應(yīng)用舉例)(!)!(!)!()!()!( !)!(mnnmnmnmnmnmnm 11111 111mnmmnm2022-7-8701.10 1.10 應(yīng)用舉例應(yīng)用舉例(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元的零錢，試問有多少種排隊的辦元的零錢，試問有多少種排隊的辦法使購票能順利進行，不出現(xiàn)找不出零錢的狀態(tài)。假法使購票能順利進行，不出現(xiàn)找不出零錢的狀態(tài)。假定每位顧客只限買一張，而且定每位顧客只限買一張，而且 。n解如圖所示，所求排隊的方法數(shù)為從點解如圖所示，所求排隊的方法數(shù)為從點 到到點點 ，且不越過直線，且不越過直線OC的路徑數(shù)。而這等于的路徑數(shù)。而這等于從點從點 到到 的路徑數(shù)減去從點的路徑數(shù)減去從點 到到 的到達的到達直線直線OC的路徑數(shù)。的路徑數(shù)。 1.10 應(yīng)用舉例應(yīng)用舉例nm ),( 00O)

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

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

50、1.10 應(yīng)用舉例應(yīng)用舉例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故不可接受序列的個數(shù)為故不可接受序列的個數(shù)為 1mnm021 kaaa2022-7-877n數(shù)字通訊中的一個重要問題是設(shè)計信道的編碼器數(shù)字通

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