組合數(shù)學(xué)課件-第一章第三節(jié)組合意義的解釋(共27張)

第一章：排列與組合1.1基本計(jì)數(shù)法則1.2一一對(duì)應(yīng):1.3排列與組合1.4圓周排列1.5排列的生成算法1.6允許重復(fù)的組合與不相鄰的組合1.7組合意義的解釋1.8應(yīng)用舉例1.9*Stirling公式1例如：從{1,2,3}中取兩個(gè)數(shù)的組合，原來是{1，2}，{1，3}，{2，3}，

如果允許重復(fù)，多了{(lán)1，1}，{2，2}，{3，3}。1.6.1允許重復(fù)的組合1.6允許重復(fù)的組合與不相鄰的組合組合模型:是兩個(gè)無標(biāo)志的球放進(jìn)三個(gè)有區(qū)別的盒子的情況，一個(gè)盒子中可放一個(gè)，也可以放多個(gè)。組合模型是r個(gè)無標(biāo)志的球放進(jìn)n個(gè)有區(qū)別的盒子的情況:一個(gè)盒子中可放一個(gè)，也可以放多個(gè)。2定理1.2在n個(gè)不同的元素中取r個(gè)進(jìn)行組合，若允許重復(fù)，則組合數(shù)為C(n+r-1,r)。證明：只要證明n取r可重復(fù)組合，與從n+r-1中取r個(gè)的不允許重復(fù)的組合一一對(duì)應(yīng)即可。設(shè)n個(gè)元素分別為1,2,3,…,n。從中取r個(gè)作允許重復(fù)的組合a1,a2,…,ar。(假設(shè)這r個(gè)我們按順序給出)由于允許重復(fù)，因此有a1≤a2≤…≤ar。首先證明每個(gè)n取r可重復(fù)組合，都對(duì)應(yīng)著不同的從n+r-1中取r個(gè)的不允許重復(fù)的組合。從{a1,a2,…,ar}構(gòu)造序列{a1,a2+1,a3+2…,ar+(r-1)}1.6允許重復(fù)的組合與不相鄰的組合3(ai+i-1)-(ai-1+i-2)=(ai-ai-1)+1>0，從n個(gè)不同元素中取r個(gè)作允許重復(fù)的組合C(n+r-1,r)并且ar+(r-1)≤n+r-1,因此ak+(k-1)是1到n+r-1中的元素。1.6允許重復(fù)的組合與不相鄰的組合4顯然br-r+1≤n,bk-k+1是1到n中的元素，而且(bk-k+1)-[bk-1-(k-1)+1]=bk-bk-1-1≥0b1≤b2-1≤…≤br-r+1因此，又得到從n+r-1中取r個(gè)作不重復(fù)的組合對(duì)應(yīng)于從n個(gè)元素中取r個(gè)作允許重復(fù)的組合。構(gòu)造序列b1,b2-1,…,br-r+1,反過來，要證明從(1,2,…,n+r-1)中取r個(gè)作不允許重復(fù)的組合(b1,b2,…,br),不妨設(shè)b1<b2<…<br≤n+r-1。對(duì)應(yīng)于從n個(gè)元素中取r個(gè)作允許重復(fù)的組合1.6允許重復(fù)的組合與不相鄰的組合51.6.2不相鄰的組合例如：從{1,2,3,4}中取2個(gè)的組合如下：{1,3},{1,4},{2,4},{1,2},{2,3},{3,4}。從{1,2,3,4}中取2個(gè)不相鄰的組合如下：{1,3},{1,4},{2,4}。1.6允許重復(fù)的組合與不相鄰的組合定理1.4從{1,2,…,n}中取r個(gè)作不相鄰的組合，其組合數(shù)為C(n-r+1,r)。61.6.3線性方程的整數(shù)解的個(gè)數(shù)問題:x1+x2+…+xn=b,n和b都是非負(fù)整數(shù);求方程的非負(fù)整數(shù)的解的個(gè)數(shù).允許重復(fù)的組合模型是r個(gè)無標(biāo)志的球放進(jìn)n個(gè)有區(qū)別的盒子的情況:方程的非負(fù)整數(shù)的個(gè)數(shù)與b個(gè)無標(biāo)志的球放進(jìn)n個(gè)有區(qū)別的盒子的情況一一對(duì)應(yīng).C(n+b-1,b)71.7組合的解釋1、路徑數(shù)問題：如圖從(0,0)點(diǎn)出發(fā)沿x軸或y軸的正方向每步走一個(gè)單位，最終走到(m,n)點(diǎn)，問有多少條路徑；

無論怎樣走法，在x方向上總共走m步，在y方向上總共走n步，若用一個(gè)字母x表示x方向上的一步，一個(gè)字母y表示y方向上的一步；則(0,0)→(m,n)的每一條路徑可表示為m個(gè)x與n個(gè)y的一個(gè)多重排列；8(m+n)!/(m!n!)=C(m+n,m)=C(m+n,n)1.7組合的解釋91.22(P64)求圖中從O到P的路徑數(shù)(a)必須經(jīng)過A點(diǎn)；(b)必須過道路AB(c)必須過A和C(d)道路AB封鎖CAB12345678OP解：(a)C(3+2,2)C(5+3,3)(b)C(3+2,2)C(4+3,3)(c)C(3+2,2)C(3+1,1)C(2+2,2)(d)C(8+5,5)-C(3+2,2)C(4+3,3)123451.7組合的解釋101.32C(n,r)=C(n-1,r)+C(n-1,r-1)(0,0)(n-r,r)(n-r-1,r)(n-r,r-1)1.7組合的解釋111.33C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0)(0,0)(n+1,r)(n,r)(n,0)1.7組合的解釋121.35C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m001…100123…m-2m-1m沒有0，C（m,0）只有一個(gè)0，C（m,1）只有二個(gè)0，C（m,2）……………….M個(gè)全是0，C（m,m）1.7組合的解釋131.35C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m(m,0)(0,m)從(0,0)點(diǎn)到(m,0)和(0,m)上點(diǎn)的路徑總數(shù)是2m(1,m-1)1.7組合的解釋141.35C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m二項(xiàng)式定理：設(shè)m是一個(gè)正整數(shù)，則對(duì)于所有的x和y,有：(x+y)m

=C(m,0)xm+x(m,1)xm-1y+C(m,2)xm-2y2+…+C(m,m-1)xym-1+C(m,m)xym1.7組合的解釋**15：應(yīng)用舉例

等同于：某保密裝置須同時(shí)使用若干把不同的鑰匙才能打開?，F(xiàn)有７人，每人持若干把鑰匙。當(dāng)且僅當(dāng)４人到場(chǎng)，所備鑰匙才能開鎖。

例1-41:7位科學(xué)工作者從事一項(xiàng)機(jī)密的研究技術(shù)，他們的實(shí)驗(yàn)室裝有“電子鎖”，每位參加該項(xiàng)工作的人都有一把打開“電子鎖”用的鑰匙，為了安全起見，當(dāng)且僅當(dāng)有4人到場(chǎng)方可打開實(shí)驗(yàn)室的門，試問該“電子鎖”必須具備多少特征？每位科學(xué)工作者的“鑰匙”應(yīng)具有多少這些特征？問①至少有多少把不同的鑰匙？②每人至少持幾把鑰匙？16

解：設(shè)有A,B,C,D,E,F,G共7人;

如果有兩個(gè)3人小組所缺鑰匙相同，例如{A,B,C}與{A,B,D}所缺鑰匙相同,①每３人至少缺１把鑰匙，故至少共有C(7,3)=35把不同的鑰匙。每３人所缺鑰匙是否相同？將這兩組合并{A,B,C}與{A,B,D}合并，產(chǎn)生一個(gè)至少四個(gè)人的小組{A,B,C,D}，仍然缺一把鑰匙，這與假設(shè)相矛盾;①至少有多少把不同的鑰匙？：應(yīng)用舉例17

任一人對(duì)于其他６人中的每３人，都至少有１把鑰匙與之相配才能開鎖；

存不存在有一人對(duì)于其他6人中的兩組，都用一把鑰匙這種情況呢？②每人至少持幾把鑰匙？

任一人對(duì)于其他６人中的每３人，都至少有１把鑰匙與之相配才能開鎖。故每人至少持C(6,3)＝20把不同的鑰匙。例如A對(duì)于{B,C,D}與{E,F,G}都用一把鑰匙；不能是同一把鑰匙；：應(yīng)用舉例18

為加深理解，舉一個(gè)較簡(jiǎn)單的例子:４人中須３人到場(chǎng)，所求如上；

鑰匙１２３４５６A√√√人B√√√C√√√D√√√

解：①每2人至少缺１把鑰匙，且每2人所缺鑰匙不同。故至少共有C(4,2)=6把不同的鑰匙；

任一人對(duì)于其他3人中的每2人，都至少有１把鑰匙與之相配才能開鎖。故每人至少持C(3,2)＝3把不同的鑰匙。：應(yīng)用舉例19例3若a和b是兩個(gè)用n位二進(jìn)制表達(dá)的碼，設(shè)a=a1a2…an，b=b1b2…bn其中ai,bi=0,1,i=1,2,…,n，若ai≠bi的數(shù)目為l,則用d(a,b)=d(b,a)=l稱l為a,b碼的漢明(Hamming)距離。1、令c=c1c2…cn,ci=0,1,i=1,2,…,n.證明三角不等式

d(a,b)+d(b,c)≥d(a,c)證明：d(a,b)=∑|ai-bi|,d(a,b)+d(b,c)=∑|ai-bi|+∑|bi-ci|

=∑(|ai-bi|+|bi-ci|)

≥∑(|ai-bi+bi-ci|)=d(a,c)d(b,c)=∑|bi-ci|：應(yīng)用舉例20(2)編碼中的糾錯(cuò)功能編碼中的糾錯(cuò)功能是這樣處理的，如果收到

a

=a

1a

2…a

n假設(shè)a

與a的漢明距離小于或等于r,則認(rèn)為a

是由a的錯(cuò)誤引起的，將它作為a處理?？赡艽嬖赼

與a和b的漢明距離都小于或等于r,怎么才能避免這種情況呢？對(duì)編碼有什么要求呢？碼b與碼a之間的漢明距離要大于或等于2r+1.b與a的漢明距離大于或等于2r+1，如果存在a

與a的距離小于r,那么a

與b的距離大于r。：應(yīng)用舉例21解：先將1到999的整數(shù)都看作3位數(shù),例如2就看作是002，這樣從000到999。試求從1到1000的整數(shù)中，0出現(xiàn)的次數(shù)。求方程的非負(fù)整數(shù)的解的個(gè)數(shù).因此不合法的0的個(gè)數(shù)為碼b與碼a之間的漢明距離要大于或等于2r+1.9*Stirling公式35C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m6允許重復(fù)的組合與不相鄰的組合6允許重復(fù)的組合與不相鄰的組合≥∑(|ai-bi+bi-ci|)=d(a,c)1、令c=c1c2…cn,ci=0,1,i=1,2,…,n.例：求小于10000的正整數(shù)中含有數(shù)字1的數(shù)的個(gè)數(shù)。任一人對(duì)于其他６人中的每３人，都至少有１把鑰匙與之相配才能開鎖；組合模型是r個(gè)無標(biāo)志的球放進(jìn)n個(gè)有區(qū)別的盒子的情況:一個(gè)盒子中可放一個(gè)，也可以放多個(gè)。二項(xiàng)式定理：設(shè)m是一個(gè)正整數(shù)，則對(duì)于所有的x和y,有：{1,3},{1,4},{2,4},{1,2},{2,3},{3,4}。編碼中的糾錯(cuò)功能是這樣處理的，如果收到{1，2}，{1，3}，{2，3}，碼b與碼a之間的漢明距離要大于或等于2r+1.如果存在a

與a的距離小于r,那么a

與b的距離大于r。證明：

d(a’,a)+d(a’,b)≥d(a,b)d(a’,b)≥d(a,b)-d(a’,a)≥2r+1-r因此：d(a’,b)≥r+1這說明：要保證能糾正距離為r內(nèi)的錯(cuò)，碼字間的距離必須至少為2r+1.：應(yīng)用舉例22(3)兩個(gè)n位碼字a,b滿足d(a,b)≥2r+1,與碼字a的漢明距離小于或等于r的數(shù)，也就是當(dāng)成a處理的字符串；

為了保證碼字間的距離不小于2r+1,碼字的數(shù)目m與碼長(zhǎng)n之間必須滿足不等式；C(n,0)+C(n,1)+C(n,2)+…+C(n,r)當(dāng)成a處理的字符串有多少？m[C(n,0)+C(n,1)+…+C(n,r)]≤2n：應(yīng)用舉例***231.9司特林（Stirling公式）***24例：求小于10000的正整數(shù)中含有數(shù)字1的數(shù)的個(gè)數(shù)。解：小于10000的正整數(shù)是1到9999，如果我們把不到4位的數(shù)前面補(bǔ)零，例如：2看作0002，22看作0022，222看作0222，那么小于10000的正整數(shù)的個(gè)數(shù)為104-1=9999個(gè)不包含1的個(gè)數(shù)為94-1=6560小于10000的正整數(shù)中含有數(shù)字1的數(shù)的個(gè)數(shù)為9999-6560=3449。1.9例題25方程的非負(fù)整數(shù)的個(gè)數(shù)與b個(gè)無標(biāo)志的球放進(jìn)n個(gè)有區(qū)別的盒子的情況一一對(duì)應(yīng).鑰匙故每人至少持C(3,2)＝3把不同的鑰匙。組合模型是r個(gè)無標(biāo)志的球放進(jìn)n個(gè)有區(qū)別的盒子的情況:一個(gè)盒子中可放一個(gè)，也可以放多個(gè)。35C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m例：求小于10000的正整數(shù)中含有數(shù)字1的數(shù)的個(gè)數(shù)。6允許重復(fù)的組合與不相鄰的組合存不存在有一人對(duì)于其他6人中的兩組，都用一把鑰匙這種情況呢？d(a’,b)≥d(a,b)-d(a’,a)