清华离散数学(第2版)：8.1-2

1第8章组合计数基础2第8章组合计数基础•引言组合问题的处理技巧•8.1基本计数规则•8.2排列与组合•8.3二项式定理与组合恒等式•8.4多项式定理3组合问题的处理技巧•一一对应•数学归纳法•上下界逼近4一一对应与上下界逼近例1在允许移动被切割的物体的情况下，最少用多少次切割可以将333的立方体切成27个单位边长的立方体？中间的小立方体的6个面都是切割产生的面，每次切割至多产生一个面，至少需要6次切割。存在一种切割方法恰好用6次切割。例2100个选手淘汰赛，为产生冠军至少需要多少轮比赛？方法1：50+25+12+6+3+2+1=99方法2：比赛次数与淘汰人数之间存在一一对应，总计淘汰99人，因此至少需要99场比赛.58.1基本计数规则•8.1.1加法法则•8.1.2乘法法则•8.1.3分类处理与分步处理6加法法则加法法则：事件A有m种产生方式，事件B有n种产生方式，则“事件A或B”有m+n种产生方式.使用条件：事件A与B产生方式不重叠适用问题：分类选取推广：事件A1有p1种产生方式，事件A2有p2种产生方式，…,事件Ak有pk种产生的方式，则“事件A1或A2或…Ak”有p1+p2+…+pk种产生的方式.7乘法法则乘法法则：事件A有m种产生方式，事件B有n种产生方式，则“事件A与B”有mn种产生方式.使用条件：事件A与B产生方式彼此独立适用问题：分步选取推广：事件A1有p1种产生方式，事件A2有p2种产生方式，…,事件Ak有pk种产生的方式，则“事件A1与A2与…Ak”有p1p2…pk种产生的方式.8分类处理与分步处理分类处理：对产生方式的集合进行划分，分别计数，然后使用加法法则分步处理：一种产生方式分解为若干独立步骤，对每步分别进行计数，然后使用乘法法则分类与分步结合使用：先分类，每类内部分步先分步，每步又分类9应用实例例3设A,B,C是3个城市，从A到B有3条道路，从B到C有2条道路，从A直接到C有4条道路，问从A到C有多少种不同的方式？解：N=32+4=10例4求1400的不同的正因子个数1400=23527解：正因子为：2i5j7k，其中0i3,0j2,0k1N=(3+1)(2+1)(1+1)=24108.2排列与组合•引言选取问题•8.2.1集合的排列与组合•8.2.2多重集的排列与组合11选取问题--组合计数模型1设n元集合S，从S中选取r个元素.根据是否有序，是否允许重复可以将该问题分为四个子类型不重复选取重复选取有序选取集合的排列多重集的排列无序选取集合的组合多重集的组合12集合的排列定义从n元集S中有序、不重复选取的r个元素称为S的一个r排列，S的所有r排列的数目记作P(n,r)定理8.1证明使用乘法法则推论S的环排列数=rnrnrnnrnP0)!(!),(rrnP),(13集合的组合rnrnrrnPrnC0!),(),(定义从n元集S中无序、不重复选取的r个元素称为S的一个r组合，S的所有r组合的数目记作C(n,r)定理8.2)11,rC(nrn推论设n,r为正整数，则(1)C(n,r)=(2)C(n,r)=C(n,nr)(3)C(n,r)=C(n1,r1)+C(n1,r))11,rC(nrn14证明方法方法1：公式代入并化简方法2：组合证明实例：证明C(n,r)=C(n,nr)证设S={1,2,…,n}是n元集合，对于S的任意r-组合A={a1,a2,…,ar}，都存在一个S的nr组合SA与之对应.显然不同的r组合对应了不同的nr组合，反之也对，因此S的r组合数恰好与S的(nr)组合数相等.C(n,r)=C(n1,r1)+C(n1,r)称为Pascal公式，也对应了杨辉三角形，两种证明方法都适用.15杨辉三角16基本计数公式的应用解分类选取A={1,4,…,298}B={2,5,…,299}C={3,6,…,300}分别取自A,B,C:各C(100,3)A,B,C各取1个（分步处理）：C(100,1)3N=C(100,3)+1003=1485100例1从1—300中任取3个数使得其和能被3整除有多少种方法？17基本计数公式的应用(续)解:1000!=1000999998…21将上面的每个因子分解，若分解式中共有i个5,j个2，那么min(i,j)就是0的个数.1,…,1000中有500个是2的倍数，j500;200个是5的倍数，40个是25的倍数（多加40个5），8个是125的倍数（再多加8个5），1个是625的倍数（再多加1个5）i=200+40+8+1=249.min(i,j)=249.例2求1000！的末尾有多少个0？18基本计数公式的应用(续)例3设A为n元集，问(1)A上的自反关系有多少个？(2)A上的反自反关系有多少个？(3)A上的对称关系有多少个？(4)A上的反对称关系有多少个？(5)A上既不对称也不是反对称的关系有多少个？nn22nn222222222nnnnn2232nnnnnnnnnn)(232222222219多重集的排列定理8.3多重集S={n1a1,n2a2,…,nkak}，0ni+∞(1)全排列r=n,n1+n2+…+nk=n证明：分步选取.先放a1,有C(n,n1)种方法；再放a2,有C(nn1,n2)种方法,...,放ak,有C(nn1n2…nk1,nk)种方法(2)若rni时，每个位置都有k种选法，得kr.kknnnn...nnnnN...!!!!2121!!!!!0!)!...(...)!(!)!()!(!!2111212111121211kkkkk...nnnnnnnnnnnnnnnnnn),nn...nn)...C(n,nn)C(nC(n,nN20多重集的组合定理8.4多重集S={n1a1,n2a2,…,nkak}，0ni+∞当rni,S的r组合数为N=C(k+r1,r),证明一个r组合为{x1a1,x2a2,…,xkak}，其中x1+x2+…+xk=r,xi为非负整数.这个不定方程的非负整数解对应于下述排列1…101…101…10……01…1x1个x2个x3个xk个r个1，k1个0的全排列数为),1()!1(!)!1(rrkCkrkrN21实例例5排列26个字母，使得a与b之间恰有7个字母，求方法数.解：设盒子的球数依次记为x1,x2,…,xn,则满足x1+x2+…+xn=r，x1,x2,…,xn为非负整数N=C(n+r1,r)例4r个相同的球放到n个不同的盒子里，每个盒子球数不限，求放球方法数.解：固定a和b,中间选7个字母，有2P(24,7)种方法，将它看作大字母与其余17个字母全排列有18！种，共N=2P(24,7)18!22实例(续)例6(1)10个男孩，5个女孩站成一排，若没有女孩相邻，有多少种方法？(2)如果站成一个圆圈，有多少种方法？解:(1)P(10,10)P(11,5)(2)P(10,10)P(10,5)/10解：相当于2n不同的球放到n个相同的盒子，每个盒子2个，放法为!2)!(22!0!2...2)!42()!22(22)!(2!2!1(2,2)...2,2)(2,2)(2!1nnnnnnnCnCnnNn例7把2n个人分成n组，每组2人，有多少分法？23实例(续)解使用一一对应的思想求解这个问题.a1,a2,…,ak：k个不相邻的数,属于集合{1,2,…,n}b1,b2,…,bk：k个允许相邻的数,属于集合{1,…,n(k1)}对应规则是bi=ai(i1).i=1,2,…,k因此N=C(nk+1,k)例8从S={1,2,…,n}中选择k个不相邻的数，有多少种方法？