組合數(shù)學(xué)第一張排列和組合

1、關(guān)于組合數(shù)學(xué)第一張排列與組合11.08.20221第一張，PPT共九十二頁，創(chuàng)作于2022年6月第1章排列與組合第二張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.20223組合數(shù)學(xué)組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計(jì)數(shù)、分析和優(yōu)化的一門學(xué)科。應(yīng)用領(lǐng)域: 計(jì)算機(jī)科學(xué)、概率論、社會(huì)科學(xué)、生物科學(xué)、信息論等。參考書： 1. R.A.Rrualdi. Introductory Combinatorics 組合數(shù)學(xué) 機(jī)械工業(yè)出版社 2. 孫淑玲 許胤龍. 組合數(shù)學(xué)引論 中國科學(xué)技術(shù)大學(xué)出版社第三張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202241.1基本計(jì)數(shù)法則1.1 基本計(jì)數(shù)法則加法

2、法則：設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A或事件B”有m+n種產(chǎn)生方式。例. 一位學(xué)生想選修一門數(shù)學(xué)課程或一門生物課程。若有4門數(shù)學(xué)課程和3門生物課程，則該學(xué)生有4+3=7種不同的選課方式。第四張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202251.1基本計(jì)數(shù)法則乘法法則：設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A與事件B”有mn種產(chǎn)生方式。例1.1 設(shè)一個(gè)符號(hào)由兩個(gè)字符組成，第1個(gè)字符由a,b,c,d,e組成，第2個(gè)字符由1,2,3組成，則由乘法法則，該符號(hào)有 種產(chǎn)生方式。第五張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.20226 例1

3、.3 求比10000小的正整數(shù)中含有數(shù)字1的數(shù)的個(gè)數(shù)。 解 比10000小的正整數(shù)可以寫為 的形式。 共有104-1=9999個(gè) 其中不含1的正整數(shù)有 94-1=6560個(gè) 所求正整數(shù)的個(gè)數(shù)為 9999-6560=3439個(gè)。1.1 基本計(jì)數(shù)法則第六張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.20227例1.4 求長度為n的二元碼的數(shù)目。 解 長度為n的二元碼的形式為 由乘法法則，長度為n的二元碼的數(shù)目為 1.1 基本計(jì)數(shù)法則第七張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.20228例1.6 求布爾函數(shù) 的數(shù)目。 解 自變量 可能取值的個(gè)數(shù)為 設(shè)取值為 則n個(gè)變元的布爾函數(shù)

4、有 個(gè)。 1.1 基本計(jì)數(shù)法則第八張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202291.1 基本計(jì)數(shù)法則例 1.8 ，求能整除n的正整數(shù)的個(gè)數(shù)。 解 能整除n的正整數(shù)可以寫為如下形式： 故能整除n的正整數(shù)的個(gè)數(shù)為 第九張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202210例1.9 求從a,b,c,d,e這5個(gè)字母中取6個(gè)所組成的字符串個(gè)數(shù)。要求(1)第1個(gè)和第6個(gè)字符必為子音字符；(2)每一字符串必有兩個(gè)母音字符，且兩個(gè)母音字母不相鄰；(3) 相鄰的兩個(gè)子音字符必不相同。 解 符合要求的字符串有以下幾種模式： 所求的字符串個(gè)數(shù)為： 個(gè)。 1.1 基本計(jì)數(shù)法則第十張，P

5、PT共九十二頁，創(chuàng)作于2022年6月11.08.202211例 設(shè)某地的街道把城市分割成矩形方格，每個(gè)方格叫做它的塊。某甲從家中出發(fā)上班，向東要走過m塊，向北要走過n塊，問某甲上班的路徑有多少條？ 解 問題可劃為求右圖從點(diǎn) (0,0)到(m,n)的路徑數(shù): 每一條從點(diǎn)(0,0)到(m,n)的路徑與 一個(gè)由m個(gè)x和n個(gè)y的排列相對應(yīng) 所求路徑數(shù)為： 1.2 一一對應(yīng) (0,0) (m,n)xy第十一張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202212定理（Cayley）n個(gè)有標(biāo)號(hào)的頂點(diǎn)的樹的數(shù)目等于 。 例1.12 給定下列樹 可得序列: 3,1,5,5,1。反之從序列3,1,5,

6、5,1也可以構(gòu)造出上述樹。 1.2 一一對應(yīng)2375461第十二張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202213定義：從n個(gè)不同的元素中，取出r個(gè)按次序排成一列，稱為從這n個(gè)元素中取r個(gè)的一個(gè)排列，其排列數(shù)記為 . 由定義顯然有 (1) (2) 當(dāng)r=n時(shí)有, 1.3 排列第十三張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202214例1.13 由5種顏色的星狀物，20種不同的花排成如下的圖案：兩邊是星狀物，中間是3朵花，問共有多少種這樣的圖案？ 解 圖案的形狀為 共有 種圖案。 1.3 排列第十四張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202215例

7、1.14 A單位有7位代表，B單位有3位代表，排在一列合影，要求B單位的人排在一起，問有多少種不同的排列方案？解 B單位的某一排列作為一個(gè)元素參加單位A進(jìn)行排列，可得 種排列。 B單位的3人共有 個(gè)排列， 故共有 排列方案。1.3 排列第十五張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202216例1.15 若例1.14中A單位的兩人排在兩端，B單位的3人不能相鄰，問有多少種不同的排列方案？解 共有 種方案。 1.3 排列第十六張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202217例1.16 求20000到70000之間的偶數(shù)中由不同的數(shù)字所組成的5位數(shù)的個(gè)數(shù)。 解 設(shè)所

8、求的數(shù)的形式為 其中 (1)若 ，這時(shí)e有4種選擇，有 (2)若 ，這時(shí)e有5種選擇，有 共有 個(gè)。 1.3 排列第十七張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202218從n個(gè)對象中取r個(gè)沿一圓周排列的排列數(shù)用 表示，則有 abcd, dabc, cdab, bcda特別地， 1.4 圓周排列abcd第十八張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202219例1.19 5顆紅色的珠子，3顆藍(lán)色的珠子裝在圓板的四周，試問有多少種排列方案？若藍(lán)色的珠子不相鄰又有多少種排列方案？藍(lán)色珠子在一起又如何？ 解 (1)有 種； (2)有 種； (3)有 種。1.4 圓周排列第

9、十九張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202220例1.20 5對夫妻出席一宴會(huì)，圍一圓桌坐下，問有幾種方案？若要求每對夫妻相鄰又有多少種方案？ 解 (1) 種方案； (2) 種方案。1.4 圓周排列第二十張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202221定義 從n個(gè)不同的元素中，取出r個(gè)而不考慮其次序，稱為從這n個(gè)元素中取r個(gè)組合，其組合數(shù)記為 。 1.5 組合第二十一張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202222例1.21 從1300之間任取3個(gè)不同的數(shù)，使得這3個(gè)數(shù)的和正好被3除盡，問共有幾種方案？ 解 將這300個(gè)數(shù)按照其被3除所

10、得的余數(shù)分為三組： A=1,4,298，B=2,5,299，C=3,6,300 三個(gè)數(shù)取自集合A：有C(100,3)種方案； 三個(gè)數(shù)取自集合B：有C(100,3)種方案； 三個(gè)數(shù)取自集合C：有C(100,3)種方案； 三個(gè)數(shù)分別取自集合A、B、C：有1003種方案； 所求的方案數(shù)為：3C(100,3)+1003=1485100 1.5 組合第二十二張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202223例1.22 甲和乙兩單位共11個(gè)成員，其中甲單位7人，乙單位4人，擬從中組成一個(gè)5人小組； (1)若要求必須包含乙單位2人； (2)若要求至少包含乙單位2人； (3)若要求乙單位某一人

11、與甲單位某一人不能同時(shí)在這個(gè)小組； 試分別求各有多少種方案。 解 (1) (2) (3) 1.5 組合第二十三張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202224例1.23 假定有8位成員，兩兩配對分成4組，問有多少種分配方案？解 方法1： 將8位成員排列，共有8!個(gè)排列，每個(gè)排列兩兩劃分，分成4組，其重復(fù)數(shù)為24.4!，所求分配方案數(shù)為 1.5 組合第二十四張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202225 方法2： 將8個(gè)人分為4組，第1組有 種選擇，第2組有 種選擇，第3組有 種選擇，第4組有 種選擇，但由于各組與順序無關(guān)，故所求分配方案數(shù)為：1.5 組合第

12、二十五張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202226例1.24某廣場有6個(gè)入口處，每個(gè)入口處每次只能通過一輛汽車，有9輛汽車要開進(jìn)廣場，問有多少種入場方案？解 方法1： 9輛汽車和5個(gè)標(biāo)志的一個(gè)排列可表示一種入場方案，其重復(fù)數(shù)為5!，所求方案數(shù)為 1.5 組合第二十六張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202227方法2： 在9輛汽車和5個(gè)標(biāo)志共14個(gè)位置中，首先選擇5個(gè)作為標(biāo)志的位置，這有 種選擇，對每一種選擇，將9輛汽車依次填入剩余的位置，這有 種填入方式，故所求方案數(shù)為 1.5 組合第二十七張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202

13、228例1.25 求5位數(shù)中至少出現(xiàn)一個(gè)6，而被3整除的數(shù)的個(gè)數(shù)。 正整數(shù)n能夠被3整除的的充要條件是n的各個(gè)數(shù)字之和能夠被3整除。 設(shè) 因?yàn)?，所以 于是 iff 1.5 組合第二十八張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022295位數(shù) 共有90000個(gè)被3整除的有30000個(gè)在這30000個(gè)數(shù)中不包含6的數(shù)有 個(gè)所求個(gè)數(shù)為 30000-17496=125041.5 組合第二十九張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202230定理 在n!中，質(zhì)數(shù)p的最高冪 其中 。 1.5 組合第三十張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202231例6

14、求1000!的末尾有幾個(gè)0 解 1000!的末尾所含0的個(gè)數(shù)為1000!的因子分解中2和5的冪的最小者 1000!因子分解中5的冪為： 故1000!的末尾有249個(gè)01.5 組合第三十一張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202232習(xí)題1.21.41.51.81.9第三十二張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202233允許重復(fù)的排列定理 多重集合 的r排列數(shù)為例 用26個(gè)英文字母可以構(gòu)造出多少個(gè)4個(gè)元音字母長度為8的字符串? 解 該問題是要求 的包含4個(gè)元音字母的8排列數(shù). 在長度為8的字符串中, 4個(gè)元音字母出現(xiàn)的位置有 種 每種元音出現(xiàn)的位置有 個(gè)排

15、列 所求字符串的個(gè)數(shù)為第三十三張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202234定理 多重集合 的全排列數(shù)為 其中證 排列的個(gè)數(shù)為允許重復(fù)的排列第三十四張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202235例1.24某廣場有6個(gè)入口處，每個(gè)入口處每次只能通過一輛汽車，有9輛汽車要開進(jìn)廣場，問有多少種入場方案？解 方法1： 9輛汽車和5個(gè)標(biāo)志的一個(gè)排列可表示一種入場方案，所求方案數(shù)為 允許重復(fù)的排列第三十五張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202236 例 從1,2,3中取2個(gè)允許重復(fù)的組合為 1,1, 1,2, 1,3, 2,2, 2,3, 3,

16、3定理1.2 在n個(gè)不同的元素中取r個(gè)進(jìn)行組合，若允許重復(fù)，則組合數(shù)為 證 設(shè)n個(gè)不同的元素為1,2,3,n 若 是一個(gè)允許重復(fù)的r組合，不妨設(shè) ，可構(gòu)造一個(gè) 上的不 允許重復(fù)的r組合1.8.1 允許重復(fù)的組合第三十六張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022371.8 允許重復(fù)的組合反之給定一個(gè) 上的不允許重復(fù)的r組合 ，我們可以如下得到一個(gè)1,2,n上的一個(gè)允許重復(fù)的r組合 。 故n個(gè)元素的允許重復(fù)的r組合與n+r-1個(gè)元素的不允許重復(fù)的組合之間有一一對應(yīng)關(guān)系，故它們的組合數(shù)相同，于是定理得證。第三十七張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202238定

17、理1.3 r個(gè)無區(qū)別的球放進(jìn)n個(gè)有標(biāo)志的盒子，而每盒放的球可多于一個(gè)，則共有 種方案例1.28 試問 有多少項(xiàng)？ 解 這相當(dāng)于將4個(gè)無區(qū)別的球放進(jìn)3個(gè)有標(biāo)志的盒子，而每盒放的球可多于一個(gè)，故共有 項(xiàng):1.8 允許重復(fù)的組合第三十八張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202239例 從 1,2,3,4,5,6 中取 3 個(gè)作不相鄰的組合有：1,3,5, 1,3,6, 1,4,6, 2,4,6定理1.4 從A=1,2,n中取r個(gè)作不相鄰的的組合，其組合數(shù)為1.8.2 不相鄰組合第三十九張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202240證 若 是一個(gè)不相鄰的r組合，

18、不妨設(shè) ，可構(gòu)造一個(gè) 上的r組合 。 反之，給定一個(gè) 上的r組合 可以如下得到一個(gè)1,2,n上的一個(gè)不相鄰 的r組合1.8.2 不相鄰組合第四十張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202241例 證明k個(gè)連續(xù)的正整數(shù)的乘積能被k!整除 。 證 不妨設(shè)k個(gè)連續(xù)的正整數(shù)為n，n+1，n+k-1。 考慮從n+k-1個(gè)元素中取k個(gè)的組合，其組合數(shù)為： 由于 是一個(gè)正整數(shù)，所以有 1.9 組合的解釋第四十一張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202242(1) 組合意義：n個(gè)元素的r-子集與n-r子集一一對應(yīng)，n個(gè)元素的r-子集的個(gè)數(shù)為 ，n-r子集的個(gè)數(shù)為 ，故等式

19、成立。例 3個(gè)元素1,2,3的2-子集與1-子集一一對應(yīng)。 1.9 組合的解釋第四十二張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202243(2) 組合意義：從這n個(gè)元素中任取一個(gè)元素a， 個(gè)組合可以如下分為兩類：不含有元素a的r組合，其組合數(shù)為 含元素a的r組合，其組合數(shù)為 1.9 組合的解釋第四十三張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022441.9 組合的解釋(3) 組合意義1：任取r個(gè)元素 不包含 ，其組合數(shù)為 包含 ，但不包含 ，其組合數(shù)為包含 ，其組合數(shù)為 第四十四張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202245組合意義2：1.9

20、組合的解釋(0,0)(n+1,r)(n,0)(n,r)第四十五張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022461.9 組合的解釋由等式(3)我們可以得到若干有用的公式：第四十六張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022471.9 組合的解釋第四十七張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022481.9 組合的解釋(4)代數(shù)證明： 第四十八張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202249組合意義：等式的左端可以看作是先從n個(gè)元素中取 個(gè)組合，然后對每一個(gè) 組合，從中再取r個(gè)元素的組合。這相當(dāng)于直接從n個(gè)元素中取r個(gè)元素的組

21、合，但每個(gè)r組合重復(fù)了 次。1.9 組合的解釋第四十九張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022501.9 組合的解釋(5) 組合意義：用兩種不同的方式計(jì)算n個(gè)元素的集合S的子集的個(gè)數(shù) S 的所有子集的個(gè)數(shù)為 另一方面，S有n個(gè)元素，在構(gòu)成S的子集時(shí)，S的每個(gè)元素都有兩種選擇，或在該子集中，或不在該子集中，由乘法法則知，S有 個(gè)子集。第五十張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202251(6) 代數(shù)證明：在等式 中令x=1, y=-1便得組合意義：在n個(gè)元素的集合S中取r組合，r為奇數(shù)的組合數(shù)目等于r為偶數(shù)的組合數(shù)目。 取定S中的一個(gè)元素a，對S的任一個(gè)奇

22、組合 若 則 對應(yīng)于偶組合 若 則 對應(yīng)于偶組合 1.9 組合的解釋第五十一張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202252反之，對S的任一個(gè)偶組合 若 則 應(yīng)于奇組合 若 ，則 對應(yīng)于奇組合 。 顯然這是奇組合與偶組合之間的一一對應(yīng)關(guān)系。故等式成立。1.9 組合的解釋第五十二張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202253例 考慮四個(gè)元素的集合a,b,c,d，其所有的奇數(shù)組合為 a, b, c, d, a,b,c, a,b,d, a,c,d, b,c,d 取元素a，其相應(yīng)的偶數(shù)組合有： ，a,b, a,c, a,d, b,c, b,d, c,d, a,b,

23、c,d。1.9 組合的解釋第五十三張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202254(7)代數(shù)證明：考慮等式兩邊的系數(shù)便得1.9 組合的解釋第五十四張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202255組合意義1：從m+n個(gè)有標(biāo)志的球中取r個(gè)，這m+n個(gè)球中有m個(gè)是紅的，有n個(gè)是藍(lán)的，所有的r組合不外乎以下幾種可能：0個(gè)紅球，r個(gè)籃球:1個(gè)紅球，r-1個(gè)籃球: r個(gè)紅球，0個(gè)籃球:1.9 組合的解釋第五十五張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202256(8) 證 在等式(7)中取r=m便得1.9 組合的解釋第五十六張，PPT共九十二頁，創(chuàng)作于20

24、22年6月11.08.202257當(dāng)m=n時(shí)有1.9 組合的解釋第五十七張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202258例 (a)用組合方法證明 和 都是整數(shù). 證 考慮將2n個(gè)有標(biāo)志的球放入n個(gè)有區(qū)別的盒子中，每盒2個(gè)球，其放法數(shù)為： 1.9 組合的解釋第五十八張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202259類似地考慮將3n個(gè)有標(biāo)志的球放入n個(gè)有區(qū)別的盒子中，每盒3個(gè)球，可得其放法數(shù)為： 故 為整數(shù)1.9 組合的解釋第五十九張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202260(b)證明 是整數(shù)。 證考慮將n2個(gè)有標(biāo)志的球放入n個(gè)有區(qū)別的盒子中

25、，每盒n個(gè)球，其放法數(shù)為： 當(dāng)n個(gè)盒子無區(qū)別時(shí)，其方法數(shù)為： 1.9 組合的解釋第六十張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022611.9 組合的解釋例 證明： 其中k, n為非負(fù)整數(shù)。 證 第六十一張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022621.161.201.221.27習(xí)題第六十二張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202263例1.30 7位科學(xué)家從事一項(xiàng)機(jī)密研究，實(shí)驗(yàn)室裝有“電子鎖”，每位科學(xué)家都有一把打開“電子鎖”的鑰匙。為了安全起見，必須有4位到場方可打開“電子鎖”。試問該“電子鎖”必須具備多少特征？每位科學(xué)家的“鑰匙”

26、 應(yīng)具有多少這些特征？ 解 因?yàn)槿我馊齻€(gè)人在一起，至少缺少電子鎖的 一種特征，而且對于兩個(gè)不同的三人組，必至少缺少兩種特征，故電子鎖至少應(yīng)具備 特征。1.10 應(yīng)用舉例第六十三張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202264對于任一位科學(xué)家，其余6個(gè)人中任意三個(gè)人在場，至少缺少一個(gè)他所具有的特征而無法打開大門，且對于兩個(gè)不同三人組，必至少缺少兩種特征，所以每個(gè)人的“鑰匙” 至少應(yīng)有 種特征。1.10 應(yīng)用舉例第六十四張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202265例1.31 4個(gè)全同的質(zhì)點(diǎn)，總能量為4E0，其中E0是常數(shù)。每個(gè)質(zhì)點(diǎn)的能級(jí)可能為kE0，k=0,

27、1,2,3,4。 (a) 若質(zhì)點(diǎn)服從Bose-Einstein分布，即能級(jí)為kE0的質(zhì)點(diǎn)可以有k2+1種狀態(tài)，而且同能級(jí)的質(zhì)點(diǎn)可以處于相同的狀態(tài)，問有多少種不同的分布圖象？ (b) 若質(zhì)點(diǎn)服從Fermi-Dirac分布，即能級(jí)為kE0的質(zhì)點(diǎn)可以有2(k2+1)種狀態(tài)，而且不允許同能級(jí)的兩個(gè)質(zhì)點(diǎn)有相同的狀態(tài)，問有多少種不同的分布圖象？1.10 應(yīng)用舉例第六十五張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202266解 總能量為4E0的四個(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ù)kE0能級(jí)

28、的質(zhì)點(diǎn)可以有1+k2種不同的狀態(tài)，故各能級(jí)的狀態(tài)為1.10 應(yīng)用舉例k012342狀態(tài)數(shù)171051第六十六張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202267 對應(yīng)于(0, 0, 0, 4)有 種圖象。 對應(yīng)于(0, 0, 1, 3)有 種圖象。 對應(yīng)于(0, 0, 2, 2)有 對應(yīng)于(0, 1, 1, 2)有 對應(yīng)于(1, 1, 1, 1)有 所求圖象數(shù)為：N=17+20+15+15+5=72 1.10 應(yīng)用舉例第六十七張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202268(2) 根據(jù)kE0能級(jí)的質(zhì)點(diǎn)可以有2(1+k2)種不同的狀態(tài)，故各能級(jí)的狀態(tài)為 對應(yīng)于(0

29、,0,0,4)有 0 種圖象。 對應(yīng)于(0,0,1,3)有 種圖象。 1.10 應(yīng)用舉例k012344狀態(tài)數(shù)3420102第六十八張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202269 對應(yīng)于(0, 0, 2, 2)有 對應(yīng)于(0, 1, 1, 2)有 對應(yīng)于(1, 1, 1, 1)有 種圖象。 故所求的圖象數(shù)為 N=0+80+45+120+1=246 1.10 應(yīng)用舉例第六十九張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202270例1.33從(0,0)點(diǎn)到達(dá)(m,n)點(diǎn)(ma，問有多少條路徑？解 路徑的第一步必然是從(0,0)點(diǎn)到達(dá)(0,1)點(diǎn)，問題等價(jià)于求從(0,1

30、)點(diǎn)到達(dá)(m,n)的滿足條件的路徑數(shù)。所求路徑數(shù)為1.10 應(yīng)用舉例第七十張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022711.10 應(yīng)用舉例(0,0)(1,0)(0,1)y=x(m,n)第七十一張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202272例1.34 一場音樂會(huì)的票價(jià)為50元一張，排隊(duì)買票的顧客中有m位持有50元的鈔票，n位持有100元的鈔票。售票處沒有準(zhǔn)備50元的零錢，試問有多少種排隊(duì)的辦法使購票能順利進(jìn)行，不出現(xiàn)找不出零錢的狀態(tài)。假定每位顧客只限買一張，而且 。解如圖所示，所求排隊(duì)的方法數(shù)為從點(diǎn) 到點(diǎn) ，且不越過直線OC的路徑數(shù)。而這等于從點(diǎn) 到 的路

31、徑數(shù)減去從點(diǎn) 到 的到達(dá)直線OC的路徑數(shù)。 1.10 應(yīng)用舉例第七十二張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202273而后者等于從點(diǎn) 到點(diǎn) 的路徑數(shù)，故所求的排隊(duì)方法數(shù)為 1.10 應(yīng)用舉例第七十三張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022741.10 應(yīng)用舉例C(n,n)O(0,0)A(1,0)B(0,1)M(m+1,n)M(m,n)第七十四張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022751.10 應(yīng)用舉例證 2: 將50元和100元的鈔票分別記為1和-1.則問題成為證明由m個(gè)1和n個(gè)-1構(gòu)成的m+n項(xiàng) 其部分和滿足 的數(shù)列的個(gè)數(shù)等于第

32、七十五張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022761.10 應(yīng)用舉例由m個(gè)1和n個(gè)-1構(gòu)成的m+n項(xiàng)的數(shù)列的個(gè)數(shù)等于考慮m個(gè)1和n個(gè)-1的不可接受的序列因?yàn)樾蛄惺遣豢山邮艿?所以存在一個(gè)最小的k使得部分和第七十六張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.2022771.10 應(yīng)用舉例將前k個(gè)字符中的1，-1互換，則得到一個(gè)有m+1個(gè)1和n-1個(gè)-1的序列。反之，任給一個(gè)有m+1個(gè)1和n-1個(gè)-1組成的字符串，則存在最小的k，使得 將前k個(gè)字符中的1，-1互換，則得到一個(gè)有m個(gè)1和n個(gè)-1的字符串，且該字符串不合乎要求。故不可接受序列的個(gè)數(shù)為第七十七張，PPT共

33、九十二頁，創(chuàng)作于2022年6月11.08.202278數(shù)字通訊中的一個(gè)重要問題是設(shè)計(jì)信道的編碼器譯碼器對。而在設(shè)計(jì)編碼器譯碼器時(shí)的一個(gè)關(guān)鍵問題是考慮所設(shè)計(jì)碼的糾錯(cuò)能力。例 編碼00, 01, 10, 11無法查錯(cuò)。 編碼00, 11可以查單錯(cuò)，但無法糾錯(cuò)。 編碼001, 110不但可以查單錯(cuò)，也可以糾單錯(cuò)。1.10 應(yīng)用舉例第七十八張，PPT共九十二頁，創(chuàng)作于2022年6月11.08.202279定義 若 ， 是兩個(gè)用n位二進(jìn)制數(shù)表示的碼， 設(shè) ， ，若 個(gè)數(shù)為 ，則記為 ，稱之為 ， 碼的 Hamming距離。 定理 對任意的碼 下列三角不等式成立： 證 設(shè) 若 ，則 ， 中至少有一個(gè)成立，故不等式成立。 1.10 應(yīng)用舉例第七十九張，PPT共九十二頁，創(chuàng)作于20