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

關(guān)于組合數(shù)學(xué)第一張排列與組合12.04.20241第1章

排列與組合第2頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.20243組合數(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.IntroductoryCombinatorics

組合數(shù)學(xué)機(jī)械工業(yè)出版社

2.

孫淑玲許胤龍.組合數(shù)學(xué)引論中國(guó)科學(xué)技術(shù)大學(xué)出版社第3頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202441.1基本計(jì)數(shù)法則1.1基本計(jì)數(shù)法則加法法則：設(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種不同的選課方式。第4頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202451.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)生方式。第5頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.20246

例1.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ù)法則第6頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.20247例1.4

求長(zhǎng)度為n的二元碼的數(shù)目。

解長(zhǎng)度為n的二元碼的形式為

由乘法法則，長(zhǎng)度為n的二元碼的數(shù)目為1.1基本計(jì)數(shù)法則第7頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.20248例1.6

求布爾函數(shù)的數(shù)目。解自變量可能取值的個(gè)數(shù)為設(shè)取值為則n個(gè)變?cè)牟紶柡瘮?shù)有

個(gè)。1.1基本計(jì)數(shù)法則第8頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202491.1基本計(jì)數(shù)法則例1.8

，求能整除n的正整數(shù)的個(gè)數(shù)。解能整除n的正整數(shù)可以寫為如下形式：故能整除n的正整數(shù)的個(gè)數(shù)為

第9頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202410例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ù)法則第10頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202411例設(shè)某地的街道把城市分割成矩形方格，每個(gè)方格叫做它的塊。某甲從家中出發(fā)上班，向東要走過(guò)m塊，向北要走過(guò)n塊，問(wèn)某甲上班的路徑有多少條？解問(wèn)題可劃為求右圖從點(diǎn)

(0,0)到(m,n)的路徑數(shù):

每一條從點(diǎn)(0,0)到(m,n)的路徑與一個(gè)由m個(gè)x和n個(gè)y的排列相對(duì)應(yīng)

所求路徑數(shù)為：

1.2

一一對(duì)應(yīng)

(0,0)

(m,n)xy第11頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202412定理（Cayley）n個(gè)有標(biāo)號(hào)的頂點(diǎn)的樹(shù)的數(shù)目等于。例1.12

給定下列樹(shù)可得序列:3,1,5,5,1。反之從序列3,1,5,5,1也可以構(gòu)造出上述樹(shù)。1.2一一對(duì)應(yīng)2375461第12頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202413定義：從n個(gè)不同的元素中，取出r個(gè)按次序排成一列，稱為從這n個(gè)元素中取r個(gè)的一個(gè)排列，其排列數(shù)記為.由定義顯然有

(1)

(2)

當(dāng)r=n時(shí)有,

1.3

排列第13頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202414例1.13

由5種顏色的星狀物，20種不同的花排成如下的圖案：兩邊是星狀物，中間是3朵花，問(wèn)共有多少種這樣的圖案？解圖案的形狀為★〇〇〇★共有種圖案。1.3

排列第14頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202415例1.14A單位有7位代表，B單位有3位代表，排在一列合影，要求B單位的人排在一起，問(wèn)有多少種不同的排列方案？解B單位的某一排列作為一個(gè)元素參加單位A進(jìn)行排列，可得種排列。

B單位的3人共有個(gè)排列，故共有排列方案。1.3

排列第15頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202416例1.15

若例1.14中A單位的兩人排在兩端，B單位的3人不能相鄰，問(wèn)有多少種不同的排列方案？解共有種方案。1.3

排列第16頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202417例1.16

求20000到70000之間的偶數(shù)中由不同的數(shù)字所組成的5位數(shù)的個(gè)數(shù)。解設(shè)所求的數(shù)的形式為其中

(1)若，這時(shí)e有4種選擇，有

(2)若，這時(shí)e有5種選擇，有共有個(gè)。1.3

排列第17頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202418從n個(gè)對(duì)象中取r個(gè)沿一圓周排列的排列數(shù)用表示，則有

abcd,dabc,cdab,bcda特別地，

1.4

圓周排列abcd第18頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202419例1.195顆紅色的珠子，3顆藍(lán)色的珠子裝在圓板的四周，試問(wèn)有多少種排列方案？若藍(lán)色的珠子不相鄰又有多少種排列方案？藍(lán)色珠子在一起又如何？解(1)有種；

(2)有種；

(3)有種。1.4

圓周排列第19頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202420例1.205對(duì)夫妻出席一宴會(huì)，圍一圓桌坐下，問(wèn)有幾種方案？若要求每對(duì)夫妻相鄰又有多少種方案？解(1)

種方案；

(2)

種方案。1.4

圓周排列第20頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202421定義從n個(gè)不同的元素中，取出r個(gè)而不考慮其次序，稱為從這n個(gè)元素中取r個(gè)組合，其組合數(shù)記為。

1.5

組合第21頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202422例1.21從1～300之間任取3個(gè)不同的數(shù)，使得這3個(gè)數(shù)的和正好被3除盡，問(wèn)共有幾種方案？

解將這300個(gè)數(shù)按照其被3除所得的余數(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

組合第22頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202423例1.22

甲和乙兩單位共11個(gè)成員，其中甲單位7人，乙單位4人，擬從中組成一個(gè)5人小組；

(1)

若要求必須包含乙單位2人；

(2)

若要求至少包含乙單位2人；

(3)

若要求乙單位某一人與甲單位某一人不能同時(shí)在這個(gè)小組；試分別求各有多少種方案。

解(1)(2)(3)1.5

組合第23頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202424例1.23假定有8位成員，兩兩配對(duì)分成4組，問(wèn)有多少種分配方案？解方法1：將8位成員排列，共有8!個(gè)排列，每個(gè)排列兩兩劃分，分成4組，其重復(fù)數(shù)為24.4!，所求分配方案數(shù)為

1.5

組合第24頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202425

方法2：將8個(gè)人分為4組，第1組有種選擇，第2組有種選擇，第3組有種選擇，第4組有種選擇，但由于各組與順序無(wú)關(guān)，故所求分配方案數(shù)為：1.5

組合第25頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202426例1.24某廣場(chǎng)有6個(gè)入口處，每個(gè)入口處每次只能通過(guò)一輛汽車，有9輛汽車要開(kāi)進(jìn)廣場(chǎng)，問(wèn)有多少種入場(chǎng)方案？解方法1：

9輛汽車和5個(gè)標(biāo)志的一個(gè)排列可表示一種入場(chǎng)方案，其重復(fù)數(shù)為5!，所求方案數(shù)為

1.5

組合第26頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202427方法2：在9輛汽車和5個(gè)標(biāo)志共14個(gè)位置中，首先選擇5個(gè)作為標(biāo)志的位置，這有種選擇，對(duì)每一種選擇，將9輛汽車依次填入剩余的位置，這有種填入方式，故所求方案數(shù)為1.5

組合第27頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202428例1.25

求5位數(shù)中至少出現(xiàn)一個(gè)6，而被3整除的數(shù)的個(gè)數(shù)。正整數(shù)n能夠被3整除的的充要條件是n的各個(gè)數(shù)字之和能夠被3整除。設(shè)

因?yàn)椋杂谑?/p>

iff1.5

組合第28頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024295位數(shù)共有90000個(gè)被3整除的有30000個(gè)在這30000個(gè)數(shù)中不包含6的數(shù)有個(gè)所求個(gè)數(shù)為

30000-17496=125041.5

組合第29頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202430定理在n!中，質(zhì)數(shù)p的最高冪其中。

1.5

組合第30頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202431例6．求1000!的末尾有幾個(gè)0

解1000!的末尾所含0的個(gè)數(shù)為1000!的因子分解中2和5的冪的最小者

1000!因子分解中5的冪為：

故1000!的末尾有249個(gè)01.5

組合第31頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202432習(xí)題1.21.41.51.81.9第32頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202433允許重復(fù)的排列定理多重集合的r排列數(shù)為例用26個(gè)英文字母可以構(gòu)造出多少個(gè)4個(gè)元音字母長(zhǎng)度為8的字符串?

解該問(wèn)題是要求的包含4個(gè)元音字母的8排列數(shù).

在長(zhǎng)度為8的字符串中,4個(gè)元音字母出現(xiàn)的位置有種每種元音出現(xiàn)的位置有個(gè)排列所求字符串的個(gè)數(shù)為第33頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202434定理多重集合的全排列數(shù)為其中證排列的個(gè)數(shù)為允許重復(fù)的排列第34頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202435例1.24某廣場(chǎng)有6個(gè)入口處，每個(gè)入口處每次只能通過(guò)一輛汽車，有9輛汽車要開(kāi)進(jìn)廣場(chǎng)，問(wèn)有多少種入場(chǎng)方案？解方法1：

9輛汽車和5個(gè)標(biāo)志的一個(gè)排列可表示一種入場(chǎng)方案，所求方案數(shù)為

允許重復(fù)的排列第35頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202436

例從{1,2,3}中取2個(gè)允許重復(fù)的組合為

{1,1},{1,2},{1,3},{2,2},{2,3},{3,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ù)的組合第36頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024371.8允許重復(fù)的組合反之給定一個(gè)上的不允許重復(fù)的r組合，我們可以如下得到一個(gè){1,2,…,n}上的一個(gè)允許重復(fù)的r組合。

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

允許重復(fù)的組合第38頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202439例從{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不相鄰組合第39頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202440證若是一個(gè)不相鄰的r組合，不妨設(shè)，可構(gòu)造一個(gè)上的r組合。

反之，給定一個(gè)上的r組合可以如下得到一個(gè){1,2,…,n}上的一個(gè)不相鄰

的r組合1.8.2不相鄰組合第40頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202441例證明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

組合的解釋第41頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202442(1)

組合意義：n個(gè)元素的r-子集與n-r子集一一對(duì)應(yīng)，n個(gè)元素的r-子集的個(gè)數(shù)為，n-r子集的個(gè)數(shù)為，故等式成立。例3個(gè)元素1,2,3的2-子集與1-子集一一對(duì)應(yīng)。

1.9

組合的解釋第42頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202443(2)

組合意義：從這n個(gè)元素中任取一個(gè)元素a，個(gè)組合可以如下分為兩類：不含有元素a的r組合，其組合數(shù)為

含元素a的r組合，其組合數(shù)為1.9

組合的解釋第43頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024441.9

組合的解釋(3)

組合意義1：任取r個(gè)元素不包含，其組合數(shù)為

包含，但不包含，其組合數(shù)為包含，其組合數(shù)為

第44頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202445組合意義2：1.9

組合的解釋(0,0)(n+1,r)(n,0)(n,r)第45頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024461.9

組合的解釋由等式(3)我們可以得到若干有用的公式：第46頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024471.9

組合的解釋第47頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024481.9

組合的解釋(4)代數(shù)證明：

第48頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202449組合意義：等式的左端可以看作是先從n個(gè)元素中取個(gè)組合，然后對(duì)每一個(gè)組合，從中再取r個(gè)元素的組合。這相當(dāng)于直接從n個(gè)元素中取r個(gè)元素的組合，但每個(gè)r組合重復(fù)了

次。1.9

組合的解釋第49頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024501.9

組合的解釋(5)

組合意義：用兩種不同的方式計(jì)算n個(gè)元素的集合S的子集的個(gè)數(shù)

S的所有子集的個(gè)數(shù)為另一方面，S有n個(gè)元素，在構(gòu)成S的子集時(shí)，S的每個(gè)元素都有兩種選擇，或在該子集中，或不在該子集中，由乘法法則知，S有個(gè)子集。第50頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202451(6)

代數(shù)證明：在等式中令x=1,y=-1便得組合意義：在n個(gè)元素的集合S中取r組合，r為奇數(shù)的組合數(shù)目等于r為偶數(shù)的組合數(shù)目。取定S中的一個(gè)元素a，對(duì)S的任一個(gè)奇組合若則對(duì)應(yīng)于偶組合若則對(duì)應(yīng)于偶組合1.9

組合的解釋第51頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202452反之，對(duì)S的任一個(gè)偶組合若則應(yīng)于奇組合若，則對(duì)應(yīng)于奇組合。顯然這是奇組合與偶組合之間的一一對(duì)應(yīng)關(guān)系。故等式成立。1.9

組合的解釋第52頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202453例考慮四個(gè)元素的集合{a,b,c,d}，其所有的奇數(shù)組合為

{a},,{c},sucpboj,{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,c,d}。1.9

組合的解釋第53頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202454(7)代數(shù)證明：考慮等式兩邊的系數(shù)便得1.9

組合的解釋第54頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202455組合意義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

組合的解釋第55頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202456(8)

證在等式(7)中取r=m便得1.9

組合的解釋第56頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202457當(dāng)m=n時(shí)有1.9

組合的解釋第57頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202458例(a)用組合方法證明和都是整數(shù).

證考慮將2n個(gè)有標(biāo)志的球放入n個(gè)有區(qū)別的盒子中，每盒2個(gè)球，其放法數(shù)為：1.9

組合的解釋第58頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202459類似地考慮將3n個(gè)有標(biāo)志的球放入n個(gè)有區(qū)別的盒子中，每盒3個(gè)球，可得其放法數(shù)為：故為整數(shù)1.9

組合的解釋第59頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202460(b)證明是整數(shù)。證考慮將n2個(gè)有標(biāo)志的球放入n個(gè)有區(qū)別的盒子中，每盒n個(gè)球，其放法數(shù)為：當(dāng)n個(gè)盒子無(wú)區(qū)別時(shí)，其方法數(shù)為：1.9

組合的解釋第60頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024611.9

組合的解釋例證明：其中k,

n為非負(fù)整數(shù)。證第61頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024621.161.201.221.27習(xí)題第62頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202463例1.30

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

應(yīng)用舉例第63頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202464對(duì)于任一位科學(xué)家，其余6個(gè)人中任意三個(gè)人在場(chǎng)，至少缺少一個(gè)他所具有的特征而無(wú)法打開(kāi)大門，且對(duì)于兩個(gè)不同三人組，必至少缺少兩種特征，所以每個(gè)人的“鑰匙”至少應(yīng)有種特征。1.10

應(yīng)用舉例第64頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202465例1.314個(gè)全同的質(zhì)點(diǎn)，總能量為4E0，其中E0是常數(shù)。每個(gè)質(zhì)點(diǎn)的能級(jí)可能為kE0，k=0,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)，問(wèn)有多少種不同的分布圖象？

(b)

若質(zhì)點(diǎn)服從Fermi-Dirac分布，即能級(jí)為kE0的質(zhì)點(diǎn)可以有2(k2+1)種狀態(tài)，而且不允許同能級(jí)的兩個(gè)質(zhì)點(diǎn)有相同的狀態(tài)，問(wèn)有多少種不同的分布圖象？1.10

應(yīng)用舉例第65頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202466解總能量為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í)的質(zhì)點(diǎn)可以有1+k2種不同的狀態(tài)，故各能級(jí)的狀態(tài)為1.10

應(yīng)用舉例k012342狀態(tài)數(shù)171051第66頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202467

①對(duì)應(yīng)于(0,0,0,4)有種圖象。②對(duì)應(yīng)于(0,0,1,3)有種圖象。③對(duì)應(yīng)于(0,0,2,2)有

④對(duì)應(yīng)于(0,1,1,2)有

⑤對(duì)應(yīng)于(1,1,1,1)有

所求圖象數(shù)為：N=17+20+15+15+5=721.10

應(yīng)用舉例第67頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202468(2)

根據(jù)kE0能級(jí)的質(zhì)點(diǎn)可以有2(1+k2)種不同的狀態(tài)，故各能級(jí)的狀態(tài)為①對(duì)應(yīng)于(0,0,0,4)有0

種圖象。

②對(duì)應(yīng)于(0,0,1,3)有種圖象。1.10應(yīng)用舉例k012344狀態(tài)數(shù)3420102第68頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202469③對(duì)應(yīng)于(0,0,2,2)有

④對(duì)應(yīng)于(0,1,1,2)有

⑤對(duì)應(yīng)于(1,1,1,1)有種圖象。故所求的圖象數(shù)為

N=0+80+45+120+1=2461.10應(yīng)用舉例第69頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202470例1.33從(0,0)點(diǎn)到達(dá)(m,n)點(diǎn)(m<n)，要求中間所經(jīng)過(guò)的每一個(gè)格子點(diǎn)(a,b)恒滿足b>a，問(wèn)有多少條路徑？解路徑的第一步必然是從(0,0)點(diǎn)到達(dá)(0,1)點(diǎn)，問(wèn)題等價(jià)于求從(0,1)點(diǎn)到達(dá)(m,n)的滿足條件的路徑數(shù)。所求路徑數(shù)為1.10

應(yīng)用舉例第70頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024711.10應(yīng)用舉例(0,0)(1,0)(0,1)y=x(m,n)第71頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202472例1.34

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

1.10

應(yīng)用舉例第72頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202473而后者等于從點(diǎn)到點(diǎn)的路徑數(shù)，故所求的排隊(duì)方法數(shù)為

1.10

應(yīng)用舉例第73頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024741.10

應(yīng)用舉例C(n,n)O(0,0)A(1,0)B(0,1)M’(m+1,n)M(m,n)第74頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024751.10

應(yīng)用舉例證2:

將50元和100元的鈔票分別記為1和-1.則問(wèn)題成為證明由m個(gè)1和n個(gè)-1構(gòu)成的m+n項(xiàng)

其部分和滿足的數(shù)列的個(gè)數(shù)等于第75頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024761.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使得部分和第76頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.2024771.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ù)為第77頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202478數(shù)字通訊中的一個(gè)重要問(wèn)題是設(shè)計(jì)信道的編碼器－譯碼器對(duì)。而在設(shè)計(jì)編碼器－譯碼器時(shí)的一個(gè)關(guān)鍵問(wèn)題是考慮所設(shè)計(jì)碼的糾錯(cuò)能力。例編碼{00,01,10,11}無(wú)法查錯(cuò)。編碼{00,11}可以查單錯(cuò)，但無(wú)法糾錯(cuò)。編碼{001,110}不但可以查單錯(cuò)，也可以糾單錯(cuò)。1.10應(yīng)用舉例第78頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202479定義若，

是兩個(gè)用n位二進(jìn)制數(shù)表示的碼，設(shè)，，若個(gè)數(shù)為，則記為，稱之為，碼的

Hamming距離。

定理對(duì)任意的碼下列三角不等式成立：

證設(shè)若，則，中至少有一個(gè)成立，故不等式成立。1.10應(yīng)用舉例第79頁(yè),共92頁(yè)，2024年2月25日，星期天12.04.202480最小距離譯碼準(zhǔn)則：給定碼C，設(shè)接受字為，將譯為C中與有最小Hamming距離的碼

定理一個(gè)編碼能糾r個(gè)錯(cuò)的充要條