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

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

2、基本計(jì)數(shù)法則n1.1 基本計(jì)數(shù)法則基本計(jì)數(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例例. 一位學(xué)生想選修一門(mén)數(shù)學(xué)課程或一門(mén)生物一位學(xué)生想選修一門(mén)數(shù)學(xué)課程或一門(mén)生物課程。若有課程。若有4門(mén)數(shù)學(xué)課程和門(mén)數(shù)學(xué)課程和3門(mén)生物課程，則該門(mén)生物課程，則該學(xué)生有學(xué)生有4+3=7種不同的選課方式。種不同的選課方式。2022-7-841.1基本計(jì)數(shù)法則基本計(jì)數(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è)一個(gè)符號(hào)由兩個(gè)字符組成，第設(shè)一個(gè)符號(hào)由兩個(gè)字符組成，第1個(gè)字符個(gè)字符由由a,b,c,d,e組成，第組成，第2個(gè)字符由個(gè)字符由1,2,3組成，則由組成，則由乘法法則，該符號(hào)有乘法法則，該符號(hào)有 種產(chǎn)生方式種產(chǎn)生方式。1535 2022-7-85 例例1.3 求求比比10000小的正整數(shù)中含有數(shù)字小的正整數(shù)中含有數(shù)字1的數(shù)的的數(shù)的個(gè)數(shù)。個(gè)數(shù)。 解解 比比10000小的正整數(shù)可以寫(xiě)為小的正整數(shù)可以寫(xiě)為 的形式。的形式。l 共有共有104-1=9999個(gè)個(gè)l 其中不含其中不含1的正整數(shù)有的正整數(shù)有 94-1=6560個(gè)個(gè)l 所求正

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

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

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

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

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

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

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

11、0000到到70000之間的偶數(shù)中由不同的數(shù)之間的偶數(shù)中由不同的數(shù)字所組成的字所組成的5位數(shù)的個(gè)數(shù)。位數(shù)的個(gè)數(shù)。 解解 設(shè)所求的數(shù)的形式為設(shè)所求的數(shù)的形式為 其中其中 (1)若若 ，這時(shí)，這時(shí)e有有4種選擇，有種選擇，有 (2)若若 ，這時(shí)，這時(shí)e有有5種選擇，有種選擇，有 共有共有 個(gè)。個(gè)。 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個(gè)對(duì)象中取個(gè)對(duì)象中取r個(gè)沿一圓周排列的排列數(shù)用個(gè)沿一圓周排列的排列數(shù)用 表示，則

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

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

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

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

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位成員，兩兩配對(duì)分成位成員，兩兩配對(duì)分成4組，問(wèn)有組，問(wèn)有多少種分配方案？多少種分配方案？解解 方法方法1： 將將8位成員排列，共有位成員排列，共有8!個(gè)排列，每個(gè)排列兩個(gè)排列，每個(gè)排列兩兩劃分，分成兩劃分，分成4組，其重復(fù)數(shù)為組，其重復(fù)數(shù)為24.4!，所求分配方，所求分配方案數(shù)為案數(shù)為 1.5 組合組合 105! 42! 84

17、 2022-7-824 方法方法2 2： 將將8 8個(gè)人分為個(gè)人分為4 4組，第組，第1 1組有組有 種選擇，第種選擇，第2 2組有組有 種選擇，第種選擇，第3 3組有組有 種選擇，第種選擇，第4 4組有組有 種選擇，但由于各組與順序無(wú)關(guān)，種選擇，但由于各組與順序無(wú)關(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某廣場(chǎng)有某廣場(chǎng)有6個(gè)入口處，每個(gè)入口處每次只能個(gè)入口處，每個(gè)入口處每

18、次只能通過(guò)一輛汽車(chē)，有通過(guò)一輛汽車(chē)，有9輛汽車(chē)要開(kāi)進(jìn)廣場(chǎng)，問(wèn)有多輛汽車(chē)要開(kāi)進(jìn)廣場(chǎng)，問(wèn)有多少種入場(chǎng)方案？少種入場(chǎng)方案？解解 方法方法1： 9輛汽車(chē)和輛汽車(chē)和5個(gè)標(biāo)志的一個(gè)排列可表示一種入場(chǎng)方個(gè)標(biāo)志的一個(gè)排列可表示一種入場(chǎng)方案，其重復(fù)數(shù)為案，其重復(fù)數(shù)為5!，所求方案數(shù)為，所求方案數(shù)為 1.5 組合組合9 8 7 6 5 4 3 2 1 ! 5!142022-7-826方法方法2： 在在9輛汽車(chē)和輛汽車(chē)和5個(gè)標(biāo)志共個(gè)標(biāo)志共14個(gè)位置中，首先選擇個(gè)位置中，首先選擇5個(gè)個(gè)作為標(biāo)志的位置，這有作為標(biāo)志的位置，這有 種選擇，對(duì)每一種選擇，對(duì)每一種選擇，將種選擇，將9輛汽車(chē)依次填入剩余的位置，這有輛汽車(chē)依次填

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

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

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

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

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

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

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

26、球放進(jìn)3個(gè)有標(biāo)志的盒子，個(gè)有標(biāo)志的盒子，而每盒放的球可多于一個(gè)，故共有而每盒放的球可多于一個(gè)，故共有 項(xiàng)項(xiàng): :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 個(gè)作不相鄰的組合有：個(gè)作不相鄰的組合有：1,3,5, 1,3,6, 1,4,6, 2,4,6n定理定理1.4 從從A=1,2,n中取中取r個(gè)作不相鄰的的組合，個(gè)作不相鄰的的組合，其組合數(shù)為其組

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

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

29、素1,2,3的的2- -子集與子集與1- -子集一一對(duì)應(yīng)。子集一一對(duì)應(yīng)。 1.9 組合的解釋組合的解釋),(),(rnnCrnC ,132231321),(rnC),(rnnC 2022-7-842(2) n組合意義：從這組合意義：從這n個(gè)元素中任取一個(gè)元素個(gè)元素中任取一個(gè)元素a， 個(gè)個(gè)組合可以如下分為兩類(lèi)：組合可以如下分為兩類(lèi)：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個(gè)元素個(gè)元素 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個(gè)元素中個(gè)元素中取取 個(gè)組合，然后對(duì)每一個(gè)個(gè)組合，然后對(duì)每一個(gè) 組合，從中再取組合，從中再取r個(gè)個(gè)元素的組合。這相當(dāng)于直接從元素的組合。這相當(dāng)于直接從n個(gè)元素中取個(gè)元素中取r個(gè)元素個(gè)元素的組合，但每個(gè)的組合，但每個(gè)r組合重復(fù)了組合重復(fù)了 次。次。1.9 組合的解釋組合的解釋 lnrnll2022-7-8491.9 組合的解釋組合的解釋n(5) n組合意義：用兩種不同的方式計(jì)算組合意義：用兩

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

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

35、 。 顯然這是奇組合與偶組合之間的一一對(duì)應(yīng)關(guān)系。故顯然這是奇組合與偶組合之間的一一對(duì)應(yīng)關(guān)系。故等式成立。等式成立。1.91.9 組合的解釋組合的解釋S ,Sa S aS Sa S aS 2022-7-852n例例 考慮四個(gè)元素的集合考慮四個(gè)元素的集合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個(gè)有標(biāo)志的球中取個(gè)有標(biāo)志的球中取r個(gè)，這個(gè)，這m+n個(gè)球中有個(gè)球中有m個(gè)是紅的，有個(gè)是紅的，有n個(gè)是藍(lán)的，所有的個(gè)是藍(lán)的，所有的r組合組合不外乎以下幾種可能：不外乎以下幾種可能：l 0個(gè)紅球，個(gè)紅球，r個(gè)籃球個(gè)籃球: :l 1個(gè)紅球，個(gè)紅球，r-1個(gè)籃球個(gè)籃球: : l r個(gè)紅球，個(gè)紅球，0個(gè)籃球個(gè)籃球: :1.9 組合的解釋組合的解釋 rnm0 11rnm 0nrm2022-7-855n(8) 證證 在等

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

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

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

40、從事一項(xiàng)機(jī)密研究，實(shí)驗(yàn)室裝有“電子鎖電子鎖”，每位科學(xué)家都有一把打開(kāi)，每位科學(xué)家都有一把打開(kāi)“電子鎖電子鎖”的鑰匙。為了安全起見(jiàn)，必須有的鑰匙。為了安全起見(jiàn)，必須有4 4位到場(chǎng)方可打開(kāi)位到場(chǎng)方可打開(kāi)“電子鎖電子鎖”。試問(wèn)該。試問(wèn)該“電子鎖電子鎖”必須具備多少特征？必須具備多少特征？每位科學(xué)家的每位科學(xué)家的“鑰匙鑰匙” ” 應(yīng)具有多少這些特征？應(yīng)具有多少這些特征？ 解解 因?yàn)槿我馊齻€(gè)人在一起，至少缺少電子鎖的因?yàn)槿我馊齻€(gè)人在一起，至少缺少電子鎖的 一種特征，而且對(duì)于兩個(gè)不同的三人組，必至少缺一種特征，而且對(duì)于兩個(gè)不同的三人組，必至少缺少兩種特征，故電子鎖至少應(yīng)具備少兩種特征，故電子鎖至少應(yīng)具備

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

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

43、.10 應(yīng)用舉例應(yīng)用舉例2022-7-865n解解 總能量為總能量為4E0的四個(gè)質(zhì)點(diǎn)有以下的四個(gè)質(zhì)點(diǎn)有以下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能級(jí)的質(zhì)點(diǎn)可以有能級(jí)的質(zhì)點(diǎn)可以有1+k2種不同的狀態(tài)，種不同的狀態(tài)，故各能級(jí)的狀態(tài)為故各能級(jí)的狀態(tài)為1.10 應(yīng)用舉例應(yīng)用舉例k012342狀態(tài)數(shù)狀態(tài)數(shù)1710512022-7-866 對(duì)應(yīng)于對(duì)應(yīng)于(0, 0, 0, 4)有有 種圖象。種圖象。 對(duì)應(yīng)于對(duì)應(yīng)于(0, 0, 1, 3)有有 種圖象。種圖象。 對(duì)應(yīng)于對(duì)應(yīng)于(0, 0, 2, 2

44、)有有 對(duì)應(yīng)于對(duì)應(yīng)于(0, 1, 1, 2)有有 對(duì)應(yīng)于對(duì)應(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能級(jí)的質(zhì)點(diǎn)可以有能級(jí)的質(zhì)點(diǎn)可以有2(1+k2)種不同的狀種不同的狀態(tài)，故各能級(jí)的狀態(tài)為態(tài)，故各能級(jí)的狀態(tài)為 對(duì)應(yīng)于對(duì)應(yīng)于(0,0,0,4)有有 0 種圖象。種圖象。 對(duì)應(yīng)于對(duì)應(yīng)于(0,0,1,3)有有 種圖象。種圖象。 1.10 應(yīng)用舉例應(yīng)用

45、舉例k012344狀態(tài)數(shù)狀態(tài)數(shù)3420102801201422 ),(),(),(CCC2022-7-868 對(duì)應(yīng)于對(duì)應(yīng)于(0, 0, 2, 2)有有 對(duì)應(yīng)于對(duì)應(yīng)于(0, 1, 1, 2)有有 對(duì)應(yīng)于對(duì)應(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)點(diǎn)到達(dá)點(diǎn)到達(dá)(m,n)點(diǎn)點(diǎn)(ma，問(wèn)有多少條路徑？，問(wèn)有多少條路徑？n解解 路徑的第一步必然是從路徑的第

46、一步必然是從(0,0)點(diǎn)到達(dá)點(diǎn)到達(dá)(0,1)點(diǎn)，問(wèn)題點(diǎn)，問(wèn)題等價(jià)于求從等價(jià)于求從(0,1)點(diǎn)到達(dá)點(diǎn)到達(dá)(m,n)的滿(mǎn)足條件的路徑數(shù)。的滿(mǎn)足條件的路徑數(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 一場(chǎng)音樂(lè)會(huì)的票價(jià)為一場(chǎng)音樂(lè)會(huì)的票價(jià)為50元一張，排隊(duì)買(mǎi)票的元一張，排隊(duì)買(mǎi)票的顧客中有顧客中有m位持有位持有50

47、元的鈔票，元的鈔票，n位持有位持有100元的鈔票。元的鈔票。售票處沒(méi)有準(zhǔn)備售票處沒(méi)有準(zhǔn)備50元的零錢(qián)，試問(wèn)有多少種排隊(duì)的辦元的零錢(qián)，試問(wèn)有多少種排隊(duì)的辦法使購(gòu)票能順利進(jìn)行，不出現(xiàn)找不出零錢(qián)的狀態(tài)。假法使購(gòu)票能順利進(jìn)行，不出現(xiàn)找不出零錢(qián)的狀態(tài)。假定每位顧客只限買(mǎi)一張，而且定每位顧客只限買(mǎi)一張，而且 。n解如圖所示，所求排隊(duì)的方法數(shù)為從點(diǎn)解如圖所示，所求排隊(duì)的方法數(shù)為從點(diǎn) 到到點(diǎn)點(diǎn) ，且不越過(guò)直線(xiàn)，且不越過(guò)直線(xiàn)OC的路徑數(shù)。而這等于的路徑數(shù)。而這等于從點(diǎn)從點(diǎn) 到到 的路徑數(shù)減去從點(diǎn)的路徑數(shù)減去從點(diǎn) 到到 的到達(dá)的到達(dá)直線(xiàn)直線(xiàn)OC的路徑數(shù)。的路徑數(shù)。 1.10 應(yīng)用舉例應(yīng)用舉例nm ),( 00O)

48、,(nmM),( 01A), 1( nmM )1 , 0(A), 1( nmM 2022-7-872n而后者等于從點(diǎn)而后者等于從點(diǎn) 到點(diǎn)到點(diǎn) 的路徑數(shù)，的路徑數(shù)，故所求的排隊(duì)方法數(shù)為故所求的排隊(duì)方法數(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. .則問(wèn)則問(wèn)題成為證明由題成為證明由m個(gè)個(gè)1和和n個(gè)個(gè)-1構(gòu)成的構(gòu)成的m+n項(xiàng)項(xiàng) 其部分和滿(mǎn)足其部分和滿(mǎn)足 的數(shù)列的個(gè)數(shù)等于的數(shù)列的個(gè)數(shù)等于nmaaa ,21), 2 , 1( , 021nmkaaak 1mnmmnm2022-7-8751.10 應(yīng)用舉例應(yīng)用舉例n由由m個(gè)個(gè)1和和n個(gè)個(gè)-1構(gòu)成的構(gòu)成的m+n項(xiàng)的數(shù)列的個(gè)數(shù)等于項(xiàng)的數(shù)列的個(gè)數(shù)等于n考慮考慮m個(gè)個(gè)1和和n個(gè)個(gè)-1的不可接受的序列的不可接受的序列n因?yàn)樾蛄惺遣豢山邮艿囊驗(yàn)樾蛄惺遣豢山邮艿? ,所以存在一個(gè)最小的所以存在一個(gè)最小的k使得部分和使得部分和 mnmnmaaa ,21021 kaaa2022-7-8761.10

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

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