《组合1排列组合.ppt》由会员分享，可在线阅读，更多相关《组合1排列组合.ppt（104页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、组合数学组合数学帅天平帅天平北京邮电大学数学系Email:第一章第一章排列组合排列组合1.1 加法法则与乘法法则1.2一一对应1.3排列与组合1.4圆周排列1.5排列的生成算法1.6允许重复的组合与不相邻的组合1.7组合意义的解释1.8应用举例1.1 1.1 加法法则与乘法法则加法法则与乘法法则1 1 加法法则加法法则 常规描述常规描述：如果完成一件事情有两个方案，而第一：如果完成一件事情有两个方案，而第一个方案有个方案有m种方法，第二个方案有种方法，第二个方案有n种方法可以实种方法可以实现。只要选择任何方案中的某一种方法，就可以完现。只要选择任何方案中的某一种方法，就可以完成这件事情，并且这
2、些方法两两互不相同。则完成成这件事情，并且这些方法两两互不相同。则完成这件事情共有这件事情共有mn种方法。种方法。概率角度描述概率角度描述：设事件：设事件A有有m种产生方式，事件种产生方式，事件B有有n种产生方式，则事件种产生方式，则事件A或或B之一有之一有m+n种产生方种产生方式。式。当然当然A与与B各自所含的基本事件是互相不同的。各自所含的基本事件是互相不同的。1.1 1.1 加法法则与乘法法则加法法则与乘法法则2 2集合描述：集合描述：设有限集合设有限集合A有有m个元素，个元素，B有有n个元素，个元素，且且A与与B不相交，则不相交，则A与与B的并共有的并共有mn个元素。个元素。若若|A|
3、=m,|B|=n,A B=,则则|A B|=m+n。集合论语言：集合论语言：例1 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18+10=28 人。1.1 1.1 加法法则与乘法法则加法法则与乘法法则3 3 例 2用一个小写英文字母或一个阿拉伯数字给一批机器编号，问总共可能编出多少种号码？解：英文字母共有26个，数字09共10个，由加法法则，总共可以编出26+10=36个号码。乘法法则乘法法则 常规描述：常规描述：如果完成一件事情需要两个步骤，而第如果完成一件事情需要两个步骤，而第一步有一步有m种方法、第二步有种方法、第二步有n种方法去实现。则完成种方法去实现。则完成该件事
4、情共有该件事情共有mn种方法。种方法。概率角度描述：概率角度描述：设事件设事件A有有m种产生方式，事件种产生方式，事件B有有n种产生方式种产生方式,则事件则事件A与与B同时产生有同时产生有 m n种产生种产生方式。方式。等价的说，等价的说，设离散型随机变量设离散型随机变量X有有m个取值，个取值，Y有有n个取值，则离散型随机向量（个取值，则离散型随机向量（X，Y）有）有m n种取值可能。种取值可能。若若|A|=m,|B|=n,A B=(a,b)|a A,b B,则则|A B|=m n。1.1 1.1 加法法则与乘法法则加法法则与乘法法则4 4集合论语言：例3给程序模块命名，需要用3个字符，其中首
5、字符要求用字母AG或UZ，后两个要求用数字19，问最多可以给多少种程序命名？解 首先，由加法法则，首字符共有7+6=13种选法。其次，再由乘法法则，最多可以产生 13*9*9=1053个不同的名称。例4 从A到B有5条道路，从B到C有3条道路，则从A经B到C有53=15 条道路。1.1 1.1 加法法则与乘法法则加法法则与乘法法则5 5例例5 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42 =8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4 4=16，而只有 4 3=12 种。在乘法法则中要注意事件 A
6、 和 事件 B 的相互独立性独立性1.1 .1 加法法则与乘法法则加法法则与乘法法则6 6 例例66 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数1)小于10000的不含1的正整数可看做4位数,但0000除外.故有 999916560个.含1的有：99996560=3439个另解:全部4位数有104个,不含1的四位数有94个,含1的4位数为两个的差:10494=3439个2)“含含0”和和“含含1”不可直接套用。不可直接套用。0019含含1但不含但不含0。在组合的习题中有许多类似的在组合的习题中有许多类似的隐含隐含的规定，要特的规定，要特别留神。别留神。9
7、9997380=2619个个 不含不含0的的1位数有位数有9个，个，2位数有位数有9 个，个，3位数位数有有9 个，个，4位数有位数有9 个个 234 9+9 +9 +9 =(9 1)/(91)=7380个个23451.1 1.1 加法法则与乘法法则加法法则与乘法法则7 7不含不含0小于小于10000的正整数有的正整数有含含0小于小于10000的正整数有的正整数有1.2 1.2 一一对应一一对应1 1“一一对应一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应的关系。在组合计数时往往借助于一一对应实现
8、模型转换.比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。1.2 1.2 一一对应一一对应2 2例例7 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？解解 一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一 对应。99场比赛。1.2 1.2 一一对应一一对应3 3例例 8 CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链：H|H C H|H H|H C H|H C H|H H|H C H|H C H|H C H|Hn=1甲烷 n=2 乙烷 n=3 丙烷1.2 1.2
9、 一一对应一一对应4 4 H|H C H|H C H|H C H|H C H|H H|HH C H|H C C H|H C H|H Hn=4 丁烷 n=4异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物.从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.1.2 1.2 一一对应一一对应5 5 例例9 (Cayley定理)n个有标号的顶点的树的数目等于nn-2。|41 2 5 3逐个摘去标号最小的叶子，叶子的相邻顶点相邻顶点(不是叶子，是内点)形成一个序列，
10、序列的长度为n-2证明前先看一个具体例子：给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)第一次摘掉，为相邻的顶点，得到序列的第一个数3以此类推，得到序列31551,长度为72=5这是由树形成序列的过程。1.2 1.2 一一对应一一对应6 6由序列形成树的过程：由序列31551得到一个新序列111233455567：生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序的序列1234567，序列的长度为5+2(即n+2)，然后将11355按照大小插入到序列1234567中，得到111233455567然后将两个序列排在一起 31
11、5511112334555671.2 1.2 一一对应一一对应7 7 31551111233455567 15511113455567 55111455567 51115567 11157 17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用蓝色蓝色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边()。依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。1.2 1.2 一一对应一一对应8 8上述对应操作的一般算法描述：给定序列b=(b1b2bn-2)设a=(123n-1 n)将b的各位插入a,得a,对()做操作。a是2n-2个元的可重非减序列
12、。ba操作是从a中去掉最小无重元，设为a1,再从b和a中各去掉一个b中的第一个元素，设为b1，则无序对(a1,b1)是一条边。重复这一操作，得n-2条边，最后a中还剩一条边，共 n-1条边，正好构成一个树。b中每去掉一个元，a中去掉2个元。1.21.2一一对应一一对应9 9由算法知由树T得b=(b1b2bn-2)，反之，由b可得T。即 f：Tb 是一一对应。由序列确定的长边过程是不会形成回路的。因任意长出的边(u,v)若属于某回路，此回路中必有一条最早生成的边，不妨就设为(u,v)，必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故
13、由()得到的边必构成一个n个顶点的树。ba1.2 1.2 一一对应一一对应1010定理证明:由一棵n个顶点的树可得到一个长度为n2的序列，且不同的树对应的序列不同*(*对n用归纳法可证)，因此 nn-2|T|所以|T|=nn-2#反之，由一个长度为n2的序列(每个元素为1 n 的一个整数)，可得到一棵树，且不同的序列对应的树是不同的，因此|T|nn-2。1.3 1.3 排列与组合排列与组合1 1定义定义1 1 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列无重排列。排列的全体组成的集合用(n,rn,r)表示。排列的个数用P(n,r)表示。当r=n 时称为全排列
14、全排列。从n个中取r个的排列的典型例子是(取球模型):从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个球.第1个盒子有n种选择,第2个有n-1种选择，第r个有n-r+1种选择。故有P(n,rP(n,r)=n(n-1)=n(n-1)(n-r+1)(n-r+1)有时也用 nnr r记n(n-n(n-1)1)(n-r+1)(n-r+1)1.3 1.3 排列与组合排列与组合2 2解解 两边是星状物，从5种颜色的星状物中取2个的排列的排列数是 P(5,2)=20 根据乘法法则得图案数为20种不同的花取3种的排列的排列数是P(20,3)=20 19 18=684020 6840=136800例例
15、10 由由5种颜色的星状物，种颜色的星状物，20种不同的花取出种不同的花取出5件件排列成如下图案：两边是星状物，中间是排列成如下图案：两边是星状物，中间是3朵花，朵花，问共有多少种这样的图案？问共有多少种这样的图案？1.3 1.3 排列与组合排列与组合3 3定义定义2 2 从 n 个不同元素中取 r 个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)表示。C(n,r)=0,若n r1.3 1.3 排列与组合排列与组合4 4从n个不同的球中,取出r个,放入r个相同的盒子里,每盒1个，这是从n个中
16、取r个的组合组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!1.31.3排列排列举举例例1 1例例11 A单位有7名代表，B单位有3位代表，排成一列合影要求B单位的3人排在一起，问有多少种不同的排列方案。接上例，若A单位的2人排在队伍两端，B单位的3人不能相邻，问有多少种不同的排列方案？解：先将B单位3位代表在一起，看成一个人，参与排列，有8！种，然后B单位内部人之间有一个排列，3！，故按乘法原理，共有：3！*8！种解：先将A单位7位代表排好，有7！种，然后B单位3人插入A
17、单位的两两代表之间或两头，有P(6,3)种，故按乘法原理，共有：7！*P(6,3)种.1.31.3排列排列举举例例2 2 于是我们只需要计算Si即可。例例12 试求由1,3,5,7组成的不重复出现的整数的总和解解：这样的整数可以是1位数,2位数,3位数,4位数,若设是i位数的总和，则S=S1+S2+S3+S4,S1=1+3+5+7=16,1.31.3排列排列举举例例3 3 S2=3(1+3+5+7)10+3(1+3+5+7)=480+48=528S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10 +6(1+3+5+7)=96000+9600+960+96=
18、106656S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=9600+960+96=10656从而 S=16+528+10656+106656=117856例例13 将八个“车”放在8*8的国际象棋棋盘上，如果 他们两两均不能互吃（不在同一行，同一列上），那么称8个车处于一个安全状态，问有多少种不同的安全状态。1.31.3排列排列举举例例4 4解：8！1.31.3组合组合举举例例1 1例例14 14 有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书2)C(5,2)+C(7,2)+C(10,
19、2)=10+21+45=761)57+510+710=1555+7+10 23)155+76=231=()解解1.31.3组合组合举举例例2 2例例15 甲和乙两单位共11个成员，其中甲单位7人，乙单位4人，拟从中组成一个5人小组：1，要求包含乙单位恰好2人；2，要求至少包含乙单位2人；3，要求乙单位某一人与甲单位特定一人不能同 时在这个小组。试求各有多少种方案。1)C(4,2)*C(7,3)2)C(4,2)*C(7,3)+C(4,3)*C(7,2)+C(4,4)*C(7,1)3)C(10,5)+C(9,4)解:1.31.3组合组合举举例例3 3例例1616 从1,300中取3个不同的数，使这
20、3个数的和能被3整除，有多少种方案？解解 将1,300分成3类：A=i|i1(mod 3)=1,4,7,298,B=i|i2(mod 3)=2,5,8,299,C=i|i3(mod 3)=3,6,9,300.要满足条件，有四种情形：3C(100,3)+100 =485100+1000000=148510031)3个数同属于A;2)3个数同属于B 3)3个数同属于C;4)A,B,C各取一数.故共有1.31.3组合组合举举例例4 4例例17 假定有a1,a2,a3,a4,a5,a6,a7,a8这8位成员,两两配对分成4组,试问有多少种方案?解：a1选择其同伴有7种可能，选定后,余下6人中某一人选择
21、其同伴只有5种可能，余下4人，其中某1人有3种选择可能，在余下的2人只好配成一对，无法选择，故共有N=7*5*3=1051.31.3组合组合举举例例5 5例例1818 某车站有某车站有6 6个入口处个入口处,每个入口处每次每个入口处每次只能进一人只能进一人,一组一组9 9个人进站的方案有多少个人进站的方案有多少?解进站方案可表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。1.31.3组合组合举举例例6 6解法1标号可产生5!个14个元的全排列。故若设x为所求方
22、案，则 x 5!=14!x=14!/5!=726485760解法2在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)9!即所求1.31.3组合组合举举例例7 7解法3 把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。故所求方案数为1.31.3组合组合举举例例8 8对于n位数a1a2a3an,它被3整除的充要条件是例例19 求5位数中至少出现一
23、个6.而且被3除尽的数 的个数。解解：首先我们证明如下事实.a1+a2+a3+an 0 (mod 3)1.31.3组合组合举举例例9 9因为由于所以1.31.3组合组合举举例例1010方法方法2：根据6所在位置和被3整除的性质，分别考虑，再应用加法原理即可。方法方法1：根据择一性，被3整除的数要么含6，要么不含6。含6且被3整除的数等于被3整除的数减去不含6且被3整除的数而后者较易计算。注意到：a1a2a3a4a5被3整除且不含6，则可以先确定a1a2a3a4,其方案数为8*9*9*9,再根据a1+a2+a3+a4被3除后的余数来确定a5的取值，此时a5有3种选择，故由乘法法则知，总数为8*9
24、*9*9*3所以含6且被3整除的数为30000-8*93*3例例20 一个凸n边形，它的任何3条对角线都不交于同一点，问它的所有对角线在凸n边形内部有多少个交点。1.31.3组合组合举举例例1111注意到，每个交点只有两个对角线通过，对应了4个顶点所组成的一个组合，不同的交点对应的组合也不相同，故共有C(n,4)个交点。1.41.4圆周排列圆周排列1 1定义定义3 3：从n个数中取出r个沿一圆周排列，称为一个圆周排列圆周排列，所有的r-圆周排列数记为 Q(n.rQ(n.r)注圆周排列与排列的不同之处在于圆周排列首尾相邻，如a、b、c、d的4种不同排列 abcd,dabc,cdab,bcda,在
25、圆周排列中都是一个排列。1.41.4圆周排列圆周排列2 2从n个中取r个的圆周排列的排列数为 12 4 3 1234 12 4 3 2341 12 4 3 3412 12 4 3 4123以4个元素为例Q(n,r)=P(n,r)/r,2rn1.41.4圆周排列圆周排列3 3 1 1 2 3 3 2项链排列项链排列就是说排列的方法和项链一样,在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。从n个中取r个的项链排列的排列数为例例21 下面两种方式实际上表示的都是3个元素的同 一种排列。P(n,r)/2r,3rn1.41.4圆周排列圆周排列-例子例子例例22 5颗红珠子，3颗蓝珠
26、子装在圆板的四周，试问有多少种方案？若要求蓝色珠子不相邻，又有多少种排列方案？蓝色珠子在一起呢？例例23 5对夫妇出席一个宴会，围一圆桌坐下，试问有几种不同的坐法？要求每对夫妇相邻又如何？解:(1):Q(8,8)=7!,(2):Q(5,5)*P(5,3),(3):Q(6,6)*3!解:(1):Q(10,10),(2):Q(5,5)*251.5排列的生成算法排列的生成算法 全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗无重复无遗漏漏地枚举出来。这里介绍一种种全排列算法：字典序法1.5字典序法对给定的字符集中的字符规定了一个先后关系，在此基础上规定两
27、个全排列的先后是从左到右逐个比较对应的字符的先后。例例 字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。一个全排列可看做一个字符串，字符串可有前缀前缀、后缀后缀。1.5字典序法1）生成给定全排列的下一个排列.所谓一个的一个的下一个下一个就是这一个这一个与下一个下一个之间没有其他的没有其他的。这就要求这一个与下一个有尽可能长长的共同前共同前缀缀，也即变化限制在尽可能短短的后缀后缀上。例例 839647521是1-9的排列。19的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了9876543
28、21，也就没有下一个了。否则找出第一次出现下降的位置。1.5字典序法求83964 47521的下一个排列7 5 2 1 747 42 2 41 1 在后缀7521中找出比4大的数7 5找出其中比4大的最小数 5 5 4、5 对换 8396 7 215 4后缀变为7421 将此后缀翻转 12 4 7接上前缀83965得到839651247 即839647521的下一个。例24为后缀大于4的用橙色表示小于4的用绿色表示 找出比右边数字小的第一个数41.5字典序法一般而言，设P是1,n的一个全排列。P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1PnP=P1P2Pj-1PkPnPk
29、+1PjPk-1Pj+1即P的下一个对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转，j=maxi|PiPj1.6 多重集的排列和组合多重集多重集元素可以多次出现的集合，即元素可以重复。我们把某个元素ai出现的次数ni(ni=0,1,2,)叫做该元素的重复数，通常把含有k种不同元素的多重集S记作选取的r个元素叫做S的一个r-(可重)排列。当 时也叫做S的一个排列.定义4 从一个多重集中有序1.6.1可重排列定理定理1 1 设多重集r-(可重)排列数是k kr r则S的例例25 求不多于4位数的二进制数的个数.解解：所求的标志数是多重集2红旗，3黄旗的排列数，故N=5!/(2!*3!)=1
30、0例例26 用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志?1.6.1可重排列总结总结4)若r n,则N=0;2)若r=n,则 N=3)若r n,则N=0;2)若r=n,则 N=13)若r n,且对所有的i,则N=C(k+r-1,r)4若r n,且存在i,则对N没有一般的求解公式，具体解法以后再说。1.6.2可重组合取r个无区别的球放进n个有标志的盒子，每个盒子中的球的数目不加限制,允许重复的组合数即其方案数。定理定理4 4 r个无区别的球放进n个有标志的盒子，每个盒子中的球的数目不限的方案数是C(n+r-1,r)种。典型模型1.6.3不相邻的组合不相邻的组合是指从n=1
31、,2,n中取r个，不允许重复且不存在i,i+1两个相邻的数同时出现于一个组合中的组合定理5 从n=1,2,n中取r个作不相邻的组合，其个数为C(n-r+1,r)1.6.3不相邻的组合以1结尾：r-1个10与n-1-2(r-1)个0的可重排列 r-1+n-1-2(r-1)=n-r其中不可含11解法解法1证明证明：用两种方法计算n的无重不相邻组合C(n,r)的计数问题这样的排列有1.6.3不相邻的组合以0结尾：r个10与n-2r个0的排列，r+n-2r=n-r。1.6.3不相邻的组合则 1b1 b2 br n-r+1,b1b2brC(n-r+1,r)解法解法1.6.4组合的生成12r的序号为0，n
32、-r+1 n-r+2n的序号为C(n,r)1设从1,n中取r元的组合全体为C(n,r).C1C2CrC(n,r).不妨设C1C2Cr,iCi(n-r+i),i=1,2,r令j=maxi|Cinr+i.则C1C2Cr的下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1)这等于给C(n,r)的元素建立了字典序字典序。1.6.4组合的生成 例27 在C(10,4)中 4679的序号是首位小于4的组合的个数；首位是4，第2位小于6的组合的个数；前2位是46，第3位小于7的组合的个数；前3位是467，第4位小于9的组合的个数之和。反之，也可以由序号求组合。从(0,0)点出发沿x轴或y轴
33、的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？1.7 组合意义的解释非降路径问题非降路径问题y x(m,n).0无论怎样走法,总有：在x方向上总共走m 步，在y方向上总共走n步。若用一个x表示x方向上的一步,一个字母y表示y方向上的一步。则(0,0)(m,n)的每一条路径可表示为m 个x与n个y的一个可重排列。设所求方案数为 P(m+n;m,n),则1.7 组合意义的解释1.7 组合意义的解释 (c,d)(a,b)故 P(m+n;m,n)=C(m+n,m)于是设ca,db,则由(a,b)到(c,d)的非降路径数为例例1 1 在上例的基础上若设m1,有C(n-1,r)种方案2.（递
34、推关系）（递推关系）C(n,r)=C(n-1,r)+C(n-1,r-1)(1.9.2)C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1)1.8 组合恒等式杨辉三角除了(0,0)点，都满足此递推式(0,0)(m,n)=(0,0)(m,n-1)(0,0)(m-1,n)a1=1,a2an+1取自2,n+r+1 有C(n+r,n)种取法 1.8 组合恒等式(1.9.3)1可从(9.2)推论,也可做一下组合证明,从1,n+r+1取a1a2anan+1,设a1a2an an+1,可按a1的取值分类：a1=1,2,3,r,r+1.a1=2,a2an+1取自3,n+r+1 有C(n+r-1,n)
35、种取法a1=r,a2an+1取自r+1,n+r+1 有C(n+1,n)种取法a1=r+1,a2an+1取自r+2,n+r+1 有C(n,n)种取法2从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上)r (n+1,r).(0,0)n n+11.8 组合恒等式故有3 可重组合.1.8 组合恒等式按不含1,含1个1,含2个1,含r个1分类.其个数相应为1,n+2中取r个的可重组合模型,记为选政治局,再选常委,n个中央委员选出k名政治局委员,再从其中选出r名常委选常委,再选非常委政治局委员1.8 组合恒等式两种选法都无遗漏无遗漏,无重复无重复地给出可能的方案，应该相等
36、。等式右边可以看作是m个男生n个女生，一男一女的组合数，易知为mm等式左端是从n+m个人中取2人的组合减去纯从女生中取2人的组合和纯从男生中取2人的组合，余下的即为一男一女的组合5.C(m+n,2)-C(m,2)-C(n,2)=mn (1.9.5)1.8组合恒等式右边即m的元素的所有选取方案.每一子集都可取k或不取.1.8 组合恒等式证证1 1组合证组合证1 1左边表示可以有0-子集(空集),1-子集,m-子集.这样有2m个方案组合证组合证2 2从(0,0)走m步有2m种走法,都落在直线x+y=m上,而到(m,0),(m-1,1),(m-2,2),(2,m-2),(1,m-1),(0,m)各点
37、的走法各有C(m,0),C(m,1),C(m,2),C(m,m-2),C(m,m-1),C(m,m)种1.8 组合恒等式7.C(m,0)-C(m,1)+C(m,m)=0 (1.9.7)1.8 组合恒等式证证1 1证证2 2 在n的所有组合中,含1的组合不含1的组合.有11对应关系。在任一含1组合及与之对应的不含1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数个元的组合做成另一集。此二集的元素个数相等。1.8 组合恒等式即Vandermonde恒等式证证1 从m个互异红球和n个互异蓝球中取r个球,按r个球中红球的个数分类.证证2:(0,0)到(m+n-r，r)
38、点的路径.(0,0)(m-r+k,r-k)(m+n-r,r)C(m,r-k)C(n,k)P(m-r,r)(m+n-r,r)(m-r+k,r-k)k=0,1,2,r Q(m,0)1.8 组合恒等式1.8 组合恒等式在8中令r=mn,再将换成即得例例1某保密装置须同时使用若干把不同的钥匙才能打开。现有人，每人持若干钥匙。须人到场，所备钥匙才能开锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？1.9 例题解解 每人至少缺把钥匙，且每人所缺钥匙不同。故至少共有C(7,3)=35把不同的钥匙。任一人对于其他人中的每人,都至少有把钥匙与之相配才能开锁.故每人至少持C(6,3)20把不同的钥匙。钥 匙 A
39、 人 B C D 1.9例题人中人到场，所求如上。共有C(4,2)=6把不同的钥匙,每人有C(3,2)=3把钥匙.（见下图）举一个较简单的例子：例例2 设n位长能纠r个错的码字的个数为M，则 1.9例题n位长的0-1字符串共有2n个。但不能每个串都设为码字，否则失去纠错能力。1.9例题设a=a1a2an，b=b1b2bn是n位数串。则a,b的Hamming距离为 Hamming距离距离即对应位不同的位的个数。1.9例题Hamming距离满足三角不等式:简证纠错处理:若设能纠正传输过程中产生的r个错.若规定a是码字，收到a有d(a,a)r 则将a当作a处理(发生最多r个错误)1.9例题ar右图表
40、示以a为球心,r位半径的球体中的串都作为a处理由汉明不等式,只要两个码字a,b满足 d(a,b)2r+1,则不至于产生一个码字b,使得它与ab的汉明距离都小于r,而无法判定是a还是b的错.由此,要保证能纠r个错,则各码字的r-邻域互不相交.1.9例题每一码字r邻域内的n位二进制数串的数目为于是,1.9例题另一方面任一串与最近的码字的距离不大于2r，否则此串本身可作为一新的码字，即以2r位半径的各码字为球心，应当使任一串落入某球内,故综合上两式,有例例3 从号码1,2,N中每次取出一个并登记，然后放回，连取n次，得到一个由n个数字组成的数列，问按这种方式能得到(1)多少个严格递增数列(n=N);
41、(2)多少个不减数列？解(1)C(N.n)(2)C(N+n-1,n)1.9 例题1.9 例题例例4 凸n边形没有3条对角线交于一点。计算各边及各对角线所组成的互不重叠的多边形区域的个数1.9 例题解 令Nk:区域中k边形的个数。从两种角度计算各区域的顶点数(包含重复计得的数目)首先可以如下计算其中m是最大多边形的边数。另一方面，每两条对角线决定一个内部多边形的顶点，因此(1)式中计算内部的多边形顶点数所得数值是4C(n,4)(每个内部顶点在(1)式中重复计算4次，因为总是4个区域共一个顶点)1.9 例题而(1)中凸多边形的每个顶点重复计数n-2次，故现在，再从两个角度来计算所有区域的内角和的总
42、和，首先，它显然是1.9 例题1021.9 1.9 例题例题 例例5 5 试求从试求从1 1到到10000001000000的整数中，的整数中，0 0出现的次数。出现的次数。解：先将解：先将1 1到到999999999999的整数都看作的整数都看作6 6位数位数,例如例如2 2就看就看作是作是000002000002，这样从，这样从000000000000到到999999999999。0 0出现了多少出现了多少次呢？次呢？6 610105 5，某一位取，某一位取0 0，其它各位任取。，其它各位任取。0 0出现在最前面的次数应该从中去掉出现在最前面的次数应该从中去掉000000000000到到9
43、99999999999中最左中最左1 1位的位的0 0出现了出现了10105 5次，次，000000000000到到099999099999中左数第中左数第2 2位的位的0 0出现了出现了10104 4次，次，000000000000到到009999009999左数第左数第3 3位的位的0 0出现了出现了10103 3次次,000000000000到到000999000999左数第左数第4 4位的位的0 0出现了出现了10102 2次次,000000000000到到000099000099左数第左数第5 5位的位的0 0出现了出现了1010次次,000000000000到到0000090000
44、09左数第左数第6 6位的位的0 0出现了出现了1 1次。次。1031.9 1.9 例题例题 因此不合法的因此不合法的0的个数为的个数为105+104+103+102+101+1=111111，不合法的应该去掉，再加整数不合法的应该去掉，再加整数1000000中的中的6个个0，这样，从，这样，从1到到1000000的整数中的整数中0出现的次数出现的次数为为6105-111111+6=488895。1047*1.9 1.9 例题例题例例6 6 试证任意试证任意r r个相邻数的连乘个相邻数的连乘 (n+1)(n+2).(n+1)(n+2).(n+rn+r)=()=(n+r)!/nn+r)!/n!被被r!r!除尽。除尽。证：从证：从n+rn+r个元素中取个元素中取r r个的组合数，个的组合数，C(n+r,rC(n+r,r)=()=(n+r)!/n!rn+r)!/n!r!