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

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

排列與組合第2頁,共92頁，2024年2月25日，星期天12.04.20243組合數(shù)學(xué)組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計數(shù)、分析和優(yōu)化的一門學(xué)科。應(yīng)用領(lǐng)域:計算機科學(xué)、概率論、社會科學(xué)、生物科學(xué)、信息論等。參考書：

1.R.A.Rrualdi.IntroductoryCombinatorics

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

2.

孫淑玲許胤龍.組合數(shù)學(xué)引論中國科學(xué)技術(shù)大學(xué)出版社第3頁,共92頁，2024年2月25日，星期天12.04.202441.1基本計數(shù)法則1.1基本計數(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頁,共92頁，2024年2月25日，星期天12.04.202451.1基本計數(shù)法則乘法法則：設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A與事件B”有mn種產(chǎn)生方式。例1.1設(shè)一個符號由兩個字符組成，第1個字符由a,b,c,d,e組成，第2個字符由1,2,3組成，則由乘法法則，該符號有

種產(chǎn)生方式。第5頁,共92頁，2024年2月25日，星期天12.04.20246

例1.3

求比10000小的正整數(shù)中含有數(shù)字1的數(shù)的個數(shù)。解比10000小的正整數(shù)可以寫為

的形式。

共有104-1=9999個其中不含1的正整數(shù)有94-1=6560個所求正整數(shù)的個數(shù)為9999-6560=3439個。1.1基本計數(shù)法則第6頁,共92頁，2024年2月25日，星期天12.04.20247例1.4

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

解長度為n的二元碼的形式為

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

求布爾函數(shù)的數(shù)目。解自變量可能取值的個數(shù)為設(shè)取值為則n個變元的布爾函數(shù)有

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

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

第9頁,共92頁，2024年2月25日，星期天12.04.202410例1.9

求從a,b,c,d,e這5個字母中取6個所組成的字符串個數(shù)。要求(1)第1個和第6個字符必為子音字符；(2)每一字符串必有兩個母音字符，且兩個母音字母不相鄰；(3)

相鄰的兩個子音字符必不相同。解符合要求的字符串有以下幾種模式：

所求的字符串個數(shù)為：個。1.1基本計數(shù)法則第10頁,共92頁，2024年2月25日，星期天12.04.202411例設(shè)某地的街道把城市分割成矩形方格，每個方格叫做它的塊。某甲從家中出發(fā)上班，向東要走過m塊，向北要走過n塊，問某甲上班的路徑有多少條？解問題可劃為求右圖從點

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

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

所求路徑數(shù)為：

1.2

一一對應(yīng)

(0,0)

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

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

(1)

(2)

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

1.3

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

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

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

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

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

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

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

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

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

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

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

abcd,dabc,cdab,bcda特別地，

1.4

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

(2)有種；

(3)有種。1.4

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

種方案；

(2)

種方案。1.4

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

1.5

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

解將這300個數(shù)按照其被3除所得的余數(shù)分為三組：

A={1,4,…,298}，B={2,5,…,299}，C={3,6,…,300}

①三個數(shù)取自集合A：有C(100,3)種方案；

②三個數(shù)取自集合B：有C(100,3)種方案；③三個數(shù)取自集合C：有C(100,3)種方案；④三個數(shù)分別取自集合A、B、C：有1003種方案；所求的方案數(shù)為：3C(100,3)+1003=1485100

1.5

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

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

(1)

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

(2)

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

(3)

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

解(1)(2)(3)1.5

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

1.5

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

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

組合第25頁,共92頁，2024年2月25日，星期天12.04.202426例1.24某廣場有6個入口處，每個入口處每次只能通過一輛汽車，有9輛汽車要開進廣場，問有多少種入場方案？解方法1：

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

1.5

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

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

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

因為，所以于是

iff1.5

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

30000-17496=125041.5

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

1.5

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

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

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

故1000!的末尾有249個01.5

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

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

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

9輛汽車和5個標志的一個排列可表示一種入場方案，所求方案數(shù)為

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

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

{1,1},{1,2},{1,3},{2,2},{2,3},{3,3}定理1.2

在n個不同的元素中取r個進行組合，若允許重復(fù)，則組合數(shù)為

證設(shè)n個不同的元素為1,2,3,…,n

若是一個允許重復(fù)的r組合，不妨設(shè)，可構(gòu)造一個上的不允許重復(fù)的r組合1.8.1

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

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

允許重復(fù)的組合第38頁,共92頁，2024年2月25日，星期天12.04.202439例從{1,2,3,4,5,6}

中取3個作不相鄰的組合有：{1,3,5},{1,3,6},{1,4,6},{2,4,6}定理1.4從A={1,2,…,n}中取r個作不相鄰的的組合，其組合數(shù)為1.8.2不相鄰組合第39頁,共92頁，2024年2月25日，星期天12.04.202440證若是一個不相鄰的r組合，不妨設(shè)，可構(gòu)造一個上的r組合。

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

的r組合1.8.2不相鄰組合第40頁,共92頁，2024年2月25日，星期天12.04.202441例證明k個連續(xù)的正整數(shù)的乘積能被k!整除。證不妨設(shè)k個連續(xù)的正整數(shù)為n，n+1，…，n+k-1。

考慮從n+k-1個元素中取k個的組合，其組合數(shù)為：由于是一個正整數(shù)，所以有1.9

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

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

1.9

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

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

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

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

組合的解釋(3)

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

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

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

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

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

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

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

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

次。1.9

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

組合的解釋(5)

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

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

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

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

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

{a},,{c},aagg2us,{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頁,共92頁，2024年2月25日，星期天12.04.202454(7)代數(shù)證明：考慮等式兩邊的系數(shù)便得1.9

組合的解釋第54頁,共92頁，2024年2月25日，星期天12.04.202455組合意義1：從m+n個有標志的球中取r個，這m+n個球中有m個是紅的，有n個是藍的，所有的r組合不外乎以下幾種可能：0個紅球，r個籃球:1個紅球，r-1個籃球:……r個紅球，0個籃球:1.9

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

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

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

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

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

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

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

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

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

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

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

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

應(yīng)用舉例第64頁,共92頁，2024年2月25日，星期天12.04.202465例1.314個全同的質(zhì)點，總能量為4E0，其中E0是常數(shù)。每個質(zhì)點的能級可能為kE0，k=0,1,2,3,4。

(a)

若質(zhì)點服從Bose-Einstein分布，即能級為kE0的質(zhì)點可以有k2+1種狀態(tài)，而且同能級的質(zhì)點可以處于相同的狀態(tài)，問有多少種不同的分布圖象？

(b)

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

應(yīng)用舉例第65頁,共92頁，2024年2月25日，星期天12.04.202466解總能量為4E0的四個質(zhì)點有以下5種可能的分布：

(0,0,0,4),(0,0,1,3),(0,0,2,2)，(0,1,1,2)，(1,1,1,1)

(a)

根據(jù)kE0能級的質(zhì)點可以有1+k2種不同的狀態(tài)，故各能級的狀態(tài)為1.10

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

①對應(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=721.10

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

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

種圖象。

②對應(yīng)于(0,0,1,3)有種圖象。1.10應(yīng)用舉例k012344狀態(tài)數(shù)3420102第68頁,共92頁，2024年2月25日，星期天12.04.202469③對應(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=2461.10應(yīng)用舉例第69頁,共92頁，2024年2月25日，星期天12.04.202470例1.33從(0,0)點到達(m,n)點(m<n)，要求中間所經(jīng)過的每一個格子點(a,b)恒滿足b>a，問有多少條路徑？解路徑的第一步必然是從(0,0)點到達(0,1)點，問題等價于求從(0,1)點到達(m,n)的滿足條件的路徑數(shù)。所求路徑數(shù)為1.10

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

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

1.10

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

1.10

應(yīng)用舉例第73頁,共92頁，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頁,共92頁，2024年2月25日，星期天12.04.2024751.10

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

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

其部分和滿足的數(shù)列的個數(shù)等于第75頁,共92頁，2024年2月25日，星期天12.04.2024761.10應(yīng)用舉例由m個1和n個-1構(gòu)成的m+n項的數(shù)列的個數(shù)等于考慮m個1和n個-1的不可接受的序列因為序列是不可接受的,所以存在一個最小的k使得部分和第76頁,共92頁，2024年2月25日，星期天12.04.2024771.10應(yīng)用舉例將前k個字符中的1，-1互換，則得到一個有m+1個1和n-1個-1的序列。反之，任給一個有m+1個1和n-1個-1組成的字符串，則存在最小的k，使得將前k個字符中的1，-1互換，則得到一個有m個1和n個-1的字符串，且該字符串不合乎要求。故不可接受序列的個數(shù)為第77頁,共92頁，2024年2月25日，星期天12.04.202478數(shù)字通訊中的一個重要問題是設(shè)計信道的編碼器－譯碼器對。而在設(shè)計編碼器－譯碼器時的一個關(guān)鍵問題是考慮所設(shè)計碼的糾錯能力。例編碼{00,01,10,11}無法查錯。編碼{00,11}可以查單錯，但無法糾錯。編碼{001,110}不但可以查單錯，也可以糾單錯。1.10應(yīng)用舉例第78頁,共92頁，2024年2月25日，星期天12.04.202479定義若，

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

Hamming距離。

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

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

定理一個編碼能糾r個錯的充要條