组合数学课件-第一章第三节组合意义的解释(共27张)

第一章：排列与组合1.1基本计数法则1.2一一对应:1.3排列与组合1.4圆周排列1.5排列的生成算法1.6允许重复的组合与不相邻的组合1.7组合意义的解释1.8应用举例1.9*Stirling公式1例如：从{1,2,3}中取两个数的组合，原来是{1，2}，{1，3}，{2，3}，

如果允许重复，多了{1，1}，{2，2}，{3，3}。1.6.1允许重复的组合1.6允许重复的组合与不相邻的组合组合模型:是两个无标志的球放进三个有区别的盒子的情况，一个盒子中可放一个，也可以放多个。组合模型是r个无标志的球放进n个有区别的盒子的情况:一个盒子中可放一个，也可以放多个。2定理1.2在n个不同的元素中取r个进行组合，若允许重复，则组合数为C(n+r-1,r)。证明：只要证明n取r可重复组合，与从n+r-1中取r个的不允许重复的组合一一对应即可。设n个元素分别为1,2,3,…,n。从中取r个作允许重复的组合a1,a2,…,ar。(假设这r个我们按顺序给出)由于允许重复，因此有a1≤a2≤…≤ar。首先证明每个n取r可重复组合，都对应着不同的从n+r-1中取r个的不允许重复的组合。从{a1,a2,…,ar}构造序列{a1,a2+1,a3+2…,ar+(r-1)}1.6允许重复的组合与不相邻的组合3(ai+i-1)-(ai-1+i-2)=(ai-ai-1)+1>0，从n个不同元素中取r个作允许重复的组合C(n+r-1,r)并且ar+(r-1)≤n+r-1,因此ak+(k-1)是1到n+r-1中的元素。1.6允许重复的组合与不相邻的组合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个作不重复的组合对应于从n个元素中取r个作允许重复的组合。构造序列b1,b2-1,…,br-r+1,反过来，要证明从(1,2,…,n+r-1)中取r个作不允许重复的组合(b1,b2,…,br),不妨设b1<b2<…<br≤n+r-1。对应于从n个元素中取r个作允许重复的组合1.6允许重复的组合与不相邻的组合51.6.2不相邻的组合例如：从{1,2,3,4}中取2个的组合如下：{1,3},{1,4},{2,4},{1,2},{2,3},{3,4}。从{1,2,3,4}中取2个不相邻的组合如下：{1,3},{1,4},{2,4}。1.6允许重复的组合与不相邻的组合定理1.4从{1,2,…,n}中取r个作不相邻的组合，其组合数为C(n-r+1,r)。61.6.3线性方程的整数解的个数问题:x1+x2+…+xn=b,n和b都是非负整数;求方程的非负整数的解的个数.允许重复的组合模型是r个无标志的球放进n个有区别的盒子的情况:方程的非负整数的个数与b个无标志的球放进n个有区别的盒子的情况一一对应.C(n+b-1,b)71.7组合的解释1、路径数问题：如图从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，问有多少条路径；

无论怎样走法，在x方向上总共走m步，在y方向上总共走n步，若用一个字母x表示x方向上的一步，一个字母y表示y方向上的一步；则(0,0)→(m,n)的每一条路径可表示为m个x与n个y的一个多重排列；8(m+n)!/(m!n!)=C(m+n,m)=C(m+n,n)1.7组合的解释91.22(P64)求图中从O到P的路径数(a)必须经过A点；(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）只有一个0，C（m,1）只有二个0，C（m,2）……………….M个全是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)点到(m,0)和(0,m)上点的路径总数是2m(1,m-1)1.7组合的解释141.35C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m二项式定理：设m是一个正整数，则对于所有的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：应用举例

等同于：某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干把钥匙。当且仅当４人到场，所备钥匙才能开锁。

例1-41:7位科学工作者从事一项机密的研究技术，他们的实验室装有“电子锁”，每位参加该项工作的人都有一把打开“电子锁”用的钥匙，为了安全起见，当且仅当有4人到场方可打开实验室的门，试问该“电子锁”必须具备多少特征？每位科学工作者的“钥匙”应具有多少这些特征？问①至少有多少把不同的钥匙？②每人至少持几把钥匙？16

解：设有A,B,C,D,E,F,G共7人;

如果有两个3人小组所缺钥匙相同，例如{A,B,C}与{A,B,D}所缺钥匙相同,①每３人至少缺１把钥匙，故至少共有C(7,3)=35把不同的钥匙。每３人所缺钥匙是否相同？将这两组合并{A,B,C}与{A,B,D}合并，产生一个至少四个人的小组{A,B,C,D}，仍然缺一把钥匙，这与假设相矛盾;①至少有多少把不同的钥匙？：应用举例17

任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁；

存不存在有一人对于其他6人中的两组，都用一把钥匙这种情况呢？②每人至少持几把钥匙？

任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁。故每人至少持C(6,3)＝20把不同的钥匙。例如A对于{B,C,D}与{E,F,G}都用一把钥匙；不能是同一把钥匙；：应用举例18

为加深理解，举一个较简单的例子:４人中须３人到场，所求如上；

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

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

任一人对于其他3人中的每2人，都至少有１把钥匙与之相配才能开锁。故每人至少持C(3,2)＝3把不同的钥匙。：应用举例19例3若a和b是两个用n位二进制表达的码，设a=a1a2…an，b=b1b2…bn其中ai,bi=0,1,i=1,2,…,n，若ai≠bi的数目为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|：应用举例20(2)编码中的纠错功能编码中的纠错功能是这样处理的，如果收到

a

=a

1a

2…a

n假设a

与a的汉明距离小于或等于r,则认为a

是由a的错误引起的，将它作为a处理。可能存在a

与a和b的汉明距离都小于或等于r,怎么才能避免这种情况呢？对编码有什么要求呢？码b与码a之间的汉明距离要大于或等于2r+1.b与a的汉明距离大于或等于2r+1，如果存在a

与a的距离小于r,那么a

与b的距离大于r。：应用举例21解：先将1到999的整数都看作3位数,例如2就看作是002，这样从000到999。试求从1到1000的整数中，0出现的次数。求方程的非负整数的解的个数.因此不合法的0的个数为码b与码a之间的汉明距离要大于或等于2r+1.9*Stirling公式35C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m6允许重复的组合与不相邻的组合6允许重复的组合与不相邻的组合≥∑(|ai-bi+bi-ci|)=d(a,c)1、令c=c1c2…cn,ci=0,1,i=1,2,…,n.例：求小于10000的正整数中含有数字1的数的个数。任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁；组合模型是r个无标志的球放进n个有区别的盒子的情况:一个盒子中可放一个，也可以放多个。二项式定理：设m是一个正整数，则对于所有的x和y,有：{1,3},{1,4},{2,4},{1,2},{2,3},{3,4}。编码中的纠错功能是这样处理的，如果收到{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内的错，码字间的距离必须至少为2r+1.：应用举例22(3)两个n位码字a,b满足d(a,b)≥2r+1,与码字a的汉明距离小于或等于r的数，也就是当成a处理的字符串；

为了保证码字间的距离不小于2r+1,码字的数目m与码长n之间必须满足不等式；C(n,0)+C(n,1)+C(n,2)+…+C(n,r)当成a处理的字符串有多少？m[C(n,0)+C(n,1)+…+C(n,r)]≤2n：应用举例***231.9司特林（Stirling公式）***24例：求小于10000的正整数中含有数字1的数的个数。解：小于10000的正整数是1到9999，如果我们把不到4位的数前面补零，例如：2看作0002，22看作0022，222看作0222，那么小于10000的正整数的个数为104-1=9999个不包含1的个数为94-1=6560小于10000的正整数中含有数字1的数的个数为9999-6560=3449。1.9例题25方程的非负整数的个数与b个无标志的球放进n个有区别的盒子的情况一一对应.钥匙故每人至少持C(3,2)＝3把不同的钥匙。组合模型是r个无标志的球放进n个有区别的盒子的情况:一个盒子中可放一个，也可以放多个。35C(m,0)+C(m,1)+C(m,2)+…+C(m,m)=2m例：求小于10000的正整数中含有数字1的数的个数。6允许重复的组合与不相邻的组合存不存在有一人对于其他6人中的两组，都用一把钥匙这种情况呢？d(a’,b)≥d(a,b)-d(a’,a)